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).

Definição do Sistema de Steiner (SS) ou Sistema Triplo de Steiner (STS)

É 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}.

Figura 1: Rotacionando triângulos no grafo completo K₇.

Para ilustrar este último exemplo, considera-se o grafo completo K₇, 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 K₇.

De modo geral, tal como no exemplo anterior, pode-se visualizar um Sistema Triplo de Steiner de ordem v como um grafo completo K_v. 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:

Figura 2: Divisão do grafo completo K₇ em triângulos.

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)

A quantidade de triplas de um Sistema Triplo de Steiner de ordem v é: $/T/={\frac {v.(v-1)}{2}}$.

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 é: C_v,2 = ${\frac {v!}{2!(v-2)!}}$ =${\frac {v.(v-1)}{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 t₁, então (a,b) ∉ tripla t₂. 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 é C_v,2 = ${\frac {v!}{2!(v-2)!}}$. Daí, chega-se a 3/T/ = C_v,2 = ${\frac {v!}{2!(v-2)!}}$, o que implica que 3.$/T/={\frac {v.(v-1)}{2}}$, e então $/T/={\frac {v.(v-1)}{6}}$, é a quantidade de triplas de qualquer Sistema Triplo de Steiner de ordem v.

Teorema (Ordem de um STS)

Um 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.

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) $|T|={\frac {v.(v-1)}{6}}$,

$|T|={\frac {(6q+1)6q}{6}}=(6q+1)q$, que é um número exato de triplas.

b) $|T|={\frac {v.(v-1)}{6}}$,

$|T|={\frac {(6q+3)(6q+2)}{6}}=6q^{2}+5q+1$, que também gera um número exato de triplas.

Referências

http://www.portal.inf.ufg.br/mestrado/sites/www.inf.ufg.br.mestrado/files/uploads/Dissertacoes/EnioPerez.pdf

Matemática Discreta. L. Lovász, J. Pelikán e K. Vesztergombi. Ed. SBM

http://www.math.ist.utl.pt/~jventura/CTC/CTCnotas7.pdf