Sistema de Steiner
O Sistema de Steiner foi criado por Jakob Steiner em 1887. No estudo da Teoria dos Planejamentos Combinatórios, um Planejamento Combinatório é resumidamente e intuitivamente, uma forma padrão de selecionar subconjuntos que são chamados de blocos de um conjunto finito, satisfazendo algumas propriedades estabelecidas. Nesta teoria, o foco principal é a discussão das técnicas para construção de diferentes planejamentos em blocos. O que diferencia os diversos tipos de planejamentos combinatórios é a forma de estabelecer e padronizar essas propriedades de seleção de subconjuntos. Entre os vários tipos de planejamentos combinatórios, se destacam duas estruturas: PBBI (planejamento de blocos balanceados incompletos) e PBP (planejamento balanceado em pares). Um caso particular desta última estrutura é o Sistema de Steiner (SS),também chamado de Sistema Triplo de Steiner (STS), que é um tipo de PBP, em que todos os blocos têm o mesmo tamanho 3, sendo chamados de triplas.
De modo geral, um planejamento combinatório é definido formalmente como um sistema de conjuntos (S, B), em que o conjunto S será um conjunto de símbolos quaisquer e o conjunto B será formado por subconjuntos (blocos) do conjunto de símbolos, de acordo com as propriedades estabelecidas, caracterizando qual o tipo de planejamento combinatório que se trata. No caso dos Sistemas Triplos de Steiner, o sistema será (S, T) pois o conjunto de blocos será formado por subconjuntos de três elementos (triplas). [1]
Definição do Sistema de Steiner (SS) ou Sistema Triplo de Steiner (STS)
editarÉ um par ordenado (S, T), onde S é um conjunto finito de pontos ou símbolos, e T é um conjunto de subconjuntos de 3 elementos de S chamados triplas, em que cada par de elementos distintos de S ocorrem juntos em exatamente uma tripla de T. O tamanho do conjunto S, denotado por /S/ , é a ordem do STS.
Pela definição acima, um STS nada mais é do que um PBP em que B = T, ou seja, o conjunto de blocos é um conjunto de triplas (blocos de tamanho 3).
Exemplos de Sistemas Triplos de Steiner:
i) S = {⊗}, S é um conjunto unitário formado por 1 elemento qualquer, então não é possível formar nenhuma tripla,logo o conjunto T de triplas é vazio: T = ∅. Este é um exemplo obviamente trivial.
ii) S = {α, β, γ}, então existe uma única tripla formada pelos próprios elementos de S, logo T = {α, β, γ}.
iii) S = {1, 2, 3, 4, 5, 6, 7}, então temos o seguinte conjunto T formado pelas triplas:
{{1, 2, 4}, {2, 3, 5}, {3, 4, 6}, {4, 5, 7}, {5, 6 ,1}, {6, 7 , 2}, {7, 1, 3}.
Para ilustrar este último exemplo, considera-se o grafo completo K7, formado pelo seguinte conjunto de vértices: V = {1, 2, 3, 4, 5, 6, 7}. Nesse grafo, considera-se o triângulo ligando os vértices 1, 2 e 4, conforme representado na figura 1. Se rotacionarmos esse triângulo para a direita, obtém-se o triângulo 2, 3 e 5, que não possui aresta em comum com o primeiro triângulo. Se este procedimento for repetido por mais cinco rotações, tem-se todas as triplas de S descritas como triângulos de K7.
De modo geral, tal como no exemplo anterior, pode-se visualizar um Sistema Triplo de Steiner de ordem v como um grafo completo Kv. Para tal procedimento, basta associar as triplas do STS com triângulos do grafo completo, mantendo a seguinte propriedade: os triângulos deverão ser constituídos de modo que cada aresta do grafo completo pertença a um único triângulo, de modo análogo ao fato de que cada par de elementos distintos do conjunto S do STS pertencem a uma única tripla. Resumidamente, temos a seguinte correspondência:
Triplas do STS ⇔ Triângulos do grafo completo.
Pares de elementos distintos do conjunto S do STS ⇔ Arestas distintas do grafo completo.
A figura 2 mostra um exemplo de um grafo completo dividido em triângulos.
Nos exemplos preliminares que foram considerados até o momento, as ordens dos Sistemas Triplos de Steiner foram respectivamente: i) 1, ii) 3 e iii) 7. Baseado na definição de um Sistema Triplo de Steiner será que é possível construir um sistema de qualquer ordem, ou há alguma restrição de ordem? Para responder a tal indagação, deve-se concentrar no Lema e Teorema a seguir, que trazem resultados fundamentais e fornecem os subsídios os quais serão úteis para posterior aplicação nas construções dos Sistemas Triplos de Steiner.
Lema (Quantidade de triplas de um STS)
editarA quantidade de triplas de um Sistema Triplo de Steiner de ordem v é: .
Prova. Tem-se que (S, T) é um STS de ordem v. ∀ tripla {a, b, c} contém os três subconjuntos de dois elementos {a, b}, {b, c} e {a, c}. Como v é a ordem do STS, a quantidade de subconjuntos de dois elementos de S é: Cv,2 = = .
Pela definição de STS, cada par de elementos distintos de S ocorrem juntos em exatamente uma tripla de T, ou seja, se (a, b) ∈ tripla t1, então (a,b) ∉ tripla t2. Vê-se que 1 tripla contém 3 pares de elementos distintos, logo /T/ triplas contém 3/T/ pares de elementos distintos. Mas também, tem-se que a quantidade de subconjuntos de dois elementos (pares distintos) do conjunto S é Cv,2 = . Daí, chega-se a 3/T/ = Cv,2 = , o que implica que 3. , e então , é a quantidade de triplas de qualquer Sistema Triplo de Steiner de ordem v. [2]
Teorema (Ordem de um STS)
editarUm Sistema Triplo de Steiner (S, T) de ordem v existe se, e somente se, v ≡ 1 ou 3 (mod 6).
Prova. Primeiramente, ∀ x ∈ S, define-se um novo conjunto T(x), como segue:
T(x) = {t\{x}x∈t∈T}.
A descrição desse conjunto significa que T(x) definido tendo como parâmetro qualquer elemento x é formado pegando todas as triplas que contêm o elemento x em questão, e retirando o próprio elemento x. Essa operação transforma as triplas em pares (subconjuntos de dois elementos).
Nota-se que T(x) deve conter todos os elementos de S, com exceção do próprio elemento x, isto porque x está associado com todos os demais elementos de S formando triplas em T. Daí, T(x) particiona S\{x} em subconjuntos de dois elementos. [3]
Para elucidar este fato, considera-se o STS (S, T), conforme definido abaixo:
S = {1,2,3,4,5,6,7};
T = {{1,2,4},{2 ,3,5},{3,4,6},{4,5,7},{5,6,1},{6,7,2},{7,3,1} }.
Se aleatoriamente, for escolhido x = 5, então:
T(x) = T(5) = {{2,3},{4,7},{6,1}}, que é uma partição de S\{x}.
Como é possível particionar S\{x}em subconjuntos de dois elementos, conclui-se que a cardinalidade de S\{x}é par, o que significa que:
|S\{x}| = v - 1 é par.
De v - 1 par, tem-se diretamente que v (cardinalidade de S) é ímpar.
Uma vez que v é ímpar, verifica-se o efeito da aplicação de uma operação de divisão e também a propriedade de congruência, a fim de obter mais informações.
Deve-se fazer a divisão de v ímpar por 6. Então, v = 6q + r (onde q e r são inteiros e 0 < r < 6), isto é equivalente à seguinte congruência:
v ≡ r (mod 6).
Mas como v é ímpar, então o resto r também deve ser ímpar, o que resulta nos seguintes valores válidos para o resto: r = 1, 3, 5.
Daí, temos três possíveis situações:
a) v ≡ 1 (mod6) ⇒ v = 6q + 1
b) v ≡ 3 (mod6) ⇒ v = 6q + 3
c) v ≡ 5 (mod 6) ⇒ v = 6q + 5
Verifica-se para cada item se o número encontrado v é compatível com uma quantidade inteira de triplas, conforme expressão do Lema acima.
a) ,
, que é um número exato de triplas.
b) ,
, que também gera um número exato de triplas.
Referências
editarMatemática Discreta. L. Lovász, J. Pelikán e K. Vesztergombi. Ed. SBM
http://www.math.ist.utl.pt/~jventura/CTC/CTCnotas7.pdf
- ↑ ENIO PEREZ RODRIGUES BARBOSA. «Planejamentos Combinatórios Construindo Sistemas Triplos de Steiner» (PDF) line feed character character in
|título=
at position 28 (ajuda) - ↑ http://www.math.ist.utl.pt/~jventura/CTC/CTCnotas7.pdf
- ↑ Matemática Discreta. L. Lovász, J. Pelikán e K. Vesztergombi. Ed. SBM