# 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 ﬁnito, 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 ﬁnito 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 K$_7$, 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$_7$.
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:
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$_1$, então (a,b) ∉ tripla t$_2$. 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.