Planejamentos Combinatórios - inf.ufg.br fileENIO PEREZ RODRIGUES BARBOSA Planejamentos Combinatórios Construindo Sistemas Triplos de Steiner Dissertação defendida no Programa

UNIVERSIDADE FEDERAL DE GOIÁSINSTITUTO DE INFORMÁTICA

ENIO PEREZ RODRIGUES BARBOSA

Planejamentos CombinatóriosConstruindo Sistemas Triplos de Steiner

Goiânia2011



Dissertação apresentada ao Programa de Pós–Graduação doInstituto de Informática da Universidade Federal de Goiás,como requisito parcial para obtenção do título de Mestre emCiência da Computação.

Área de concentração: Ciência da Computação.

Orientador: Prof. Dr. Rommel Melgaço Barbosa

Goiânia2011



Dissertação defendida no Programa de Pós–Graduação do Instituto deInformática da Universidade Federal de Goiás como requisito parcialpara obtenção do título de Mestre em Ciência da Computação, aprovadaem 26 de Agosto de 2011, pela Banca Examinadora constituída pelosprofessores:

Prof. Dr. Rommel Melgaço BarbosaInstituto de Informática – UFG

Presidente da Banca

Profa. Dra. Telma Woerle de Lima SoaresInstituto de Informática – UFG

Prof. Dr. Clarimar José CoelhoDepartamento de Computação – PUC-GO

Todos os direitos reservados. É proibida a reprodução total ou parcial dotrabalho sem autorização da universidade, do autor e do orientador(a).

Enio Perez Rodrigues Barbosa

Graduou-se em Matemática pela UFG - Universidade Federal de Goiás.Durante o Mestrado em Ciência da Computação, na UFG - UniversidadeFederal de Goiás, obteve bolsa de formação da Fundação de Amparo àPesquisa do Estado de Goiás - FAPEG.

Dedico este trabalho à Deus, autor da minha vida.

Agradecimentos

Agradeço primeiramente à Deus, por me guiar e me conceder sabedoria, paciên-cia, perseverança, equilíbrio e discernimento.

À minha família: meus pais Vilmar e Divina e minha irmã Elisângela, que sempreme apoiaram nos momentos mais difíceis.

Ao prof. Rommel pelo direcionamento, atenção e paciência na orientação.Aos professores e colegas técnicos-administrativos do Instituto de Informática.

A pessoa que procura segurança no Deus Altíssimo e se abriga na sombraprotetora do Todo Poderoso pode dizer a ele: Ó SENHOR Deus, tu és o meudefensor e o meu protetor. Tu és o meu Deus; eu confio em Ti.

Bíblia Sagrada,Salmos 91:1 e 2 - Versão: Nova Tradução na Linguagem de Hoje.

Resumo

Barbosa, Enio Perez Rodrigues. Planejamentos Combinatórios. Goiânia, 2011.90p. Dissertação de Mestrado. Instituto de Informática, Universidade Federal deGoiás.

Intuitivamente, a idéia básica de um Planejamento Combinatório consiste em umamaneira de selecionar subconjuntos, também chamados de blocos, de um conjunto finito,de modo que algumas propriedades especificadas sejam satisfeitas. O caso mais geral sãoos planejamentos balanceados. Um PBD é um par ordenado (S,B), onde S é um conjuntofinito de símbolos, e B é uma coleção de subconjuntos de S chamados blocos, tais que cadapar de elementos distintos de S ocorrem juntos em exatamente um bloco de B. Um Sistema

Triplo de Steiner é um caso particular de um PBD, em que todos os blocos tem tamanhoúnico 3, sendo chamados de triplas. O foco principal está nas técnicas de construção dossistemas. Por meio da resolubilidade se discute quando um Sistema Triplo de Steiner éresolvível e quando não é resolvível. Esta teoria possui várias aplicações, por exemplo:imersões e até mesmo problemas relacionados à complexidade computacional.

Palavras–chave

Planejamentos Combinatórios, Blocos, Sistemas Triplos de Steiner, Grafos, Re-solubilidade, Imersões, NP-Completude.

Abstract

Barbosa, Enio Perez Rodrigues. Planejamentos Combinatórios. Goiânia, 2011.90p. MSc. Dissertation. Instituto de Informática, Universidade Federal de Goiás.

Intuitively, the basic idea of Design Theory consists of a way to select subsets, also calledblocks, of a finite set, so that some properties are satisfied. The more general case are theblocks designs. A PBD is an ordered pair (S,B), where S is a finite set of symbols, and B

is a collection of subsets of S called blocks, such that each pair of distinct elements of S

occur together in exactly one block of B. A Steiner Triple System is a particular case of aPBD, where every block has size only 3, being called triples. The main focus is in buildingtechnology systems. By resolvability is discussed as a Steiner Triple Systems is resolvable,and when it is not resolvable. This theory has several applications, eg, embeddings andeven problems related to computational complexity.

Keywords

Design Theory, Combinatorial Designs, Blocks, Steiner Triple Systems, Graphs,Resolvability, Embeddings, NP-Completeness.

Sumário

Lista de Figuras 10

Lista de Tabelas 12

Lista de Algoritmos 13

Lista de Abreviaturas 14

Lista de Símbolos 15

1 Introdução 17

2 Conceitos Básicos 212.1 Congruência 212.2 Grupos 222.3 Quadrados Latinos e Quasigrupos 24

2.3.1 Quadrados Latinos 242.3.2 Quasigrupos 25

2.4 Grafos 27

3 Planejamentos em Blocos 303.1 Planejamentos Balanceados 303.2 Sistemas Triplos de Steiner 313.3 A Construção de Bose 353.4 A Construção de Skolem 473.5 A Construção 6n + 5 563.6 A Construção de Wilson 64

4 Resolubilidade 724.1 Classes Paralelas e STS resolvíveis 724.2 Construíndo STS não-resolvíveis 74

5 Imersões 78

6 NP-Completude e Planejamentos Combinatórios 83

7 Conclusões 86

Referências Bibliográficas 88

Lista de Figuras

2.1 Exemplo de um quadrado latino de ordem 4 com as denominações decartas. 25

2.2 Exemplo de um quadrado latino de ordem 4 com os rótulos de cartas. 252.3 Exemplo de um grafo. 282.4 Um grafo completo K5. 28

3.1 Rotacionando triângulos no grafo completo K7. 323.2 Divisão do grafo completo K7 em triângulos. 323.3 Representação gráfica das triplas em um sistema de coordenadas (i,k). 363.4 STS(9): Representação gráfica das triplas do tipo 1. 393.5 STS(9): Representação gráfica das triplas do tipo 2 - subconjunto 1. 393.6 STS(9): Representação gráfica das triplas do tipo 2 - subconjunto 2. 403.7 STS(9): Representação gráfica das triplas do tipo 2 - subconjunto 3. 403.8 STS(15): Representação gráfica das triplas do tipo 1. 433.9 STS(15): Representação gráfica das triplas do tipo 2 - subconjunto 1. 433.10 STS(15): Representação gráfica das triplas do tipo 2 - subconjunto 2. 433.11 STS(15): Representação gráfica das triplas do tipo 2 - subconjunto 3. 443.12 STS(15): Representação gráfica das triplas do tipo 2 - subconjunto 4. 443.13 STS(15): Representação gráfica das triplas do tipo 2 - subconjunto 5. 453.14 STS(15): Representação gráfica das triplas do tipo 2 - subconjunto 6. 453.15 STS(15): Representação gráfica das triplas do tipo 2 - subconjunto 7. 463.16 STS(15): Representação gráfica das triplas do tipo 2 - subconjunto 8. 463.17 STS(15): Representação gráfica das triplas do tipo 2 - subconjunto 9. 473.18 STS(15): Representação gráfica das triplas do tipo 2 - subconjunto 10. 473.19 STS(13): Representação gráfica das triplas do tipo 1 513.20 STS(13): Representação gráfica das triplas do tipo 2 - subconjunto 1 a) 513.21 STS(13): Representação gráfica das triplas do tipo 2 - subconjunto 1 b) 513.22 STS(13): Representação gráfica das triplas do tipo 2 - subconjunto 1 c) 523.23 STS(13): Representação gráfica das triplas do tipo 2 - subconjunto 2 a) 523.24 STS(13): Representação gráfica das triplas do tipo 2 - subconjunto 2 b) 523.25 STS(13): Representação gráfica das triplas do tipo 2 - subconjunto 2 c) 533.26 STS(13): Representação gráfica das triplas do tipo 3 - subconjunto 1 533.27 STS(13): Representação gráfica das triplas do tipo 3 - subconjunto 2 543.28 STS(13): Representação gráfica das triplas do tipo 3 - subconjunto 3 543.29 STS(13): Representação gráfica das triplas do tipo 3 - subconjunto 4 553.30 STS(13): Representação gráfica das triplas do tipo 3 - subconjunto 5 553.31 STS(13): Representação gráfica das triplas do tipo 3 - subconjunto 6 563.32 PBD(17): Representação gráfica do bloco de tamanho 5 - tipo 1 59

3.33 PBD(17): Representação gráfica das triplas do tipo 2 603.34 PBD(17): Representação gráfica das triplas do tipo 3 - subconjunto 1 603.35 PBD(17): Representação gráfica das triplas do tipo 3 - subconjunto 2 603.36 PBD(17): Representação gráfica das triplas do tipo 3 - subconjunto 3 613.37 PBD(17): Representação gráfica das triplas do tipo 3 - subconjunto 4 613.38 PBD(17): Representação gráfica das triplas do tipo 3 - subconjunto 5 623.39 PBD(17): Representação gráfica das triplas do tipo 3 - subconjunto 6 623.40 PBD(17): Representação gráfica das triplas do tipo 3 - subconjunto 7 633.41 PBD(17): Representação gráfica das triplas do tipo 3 - subconjunto 8 633.42 PBD(17): Representação gráfica das triplas do tipo 3 - subconjunto 9 643.43 PBD(17): Representação gráfica das triplas do tipo 3 - subconjunto 10 643.44 Uma roda R com 4 vértices. 653.45 Uma biroda R sobre 12 vértices. 663.46 Uma biroda R sobre 10 vértices. 663.47 O grafo de deficiência de Z7. 69

4.1 1-fatoração do grafo completo K8. 75

5.1 Representação de um Sistema Triplo de Steiner parcial de ordem 9. 81

Lista de Tabelas

2.1 Tábua de Adição Módulo 7: (Z7,+). 232.2 Tábua de Adição Módulo 8: (Z8,+). 242.3 Quasigrupo comutativo idempotente de ordem 7: (Q,◦). 262.4 Quasigrupo comutativo semi-idempotente de ordem 8: (Q,◦) 27

3.1 Tábua de Adição Módulo 3: (Z3,+). 373.2 Quasigrupo comutativo idempotente de ordem 3: (Q,◦). 383.3 Tábua de Adição Módulo 5: (Z5,+). 413.4 Quasigrupo comutativo idempotente de ordem 5: (Q,◦). 413.5 Tábua de Adição Módulo 4: (Z4,+). 493.6 Quasigrupo comutativo semi-idempotente de ordem 4: (Q,◦). 493.7 1-fatoração da roda R. 653.8 1-fatoração da biroda R. 663.9 1-fatoração da biroda R. 673.10 1-fatoração do grafo de deficiência de Z7. 69

5.1 Quadrado latino T de ordem 5. 785.2 Retângulo latino incompleto R de dimensão 3 x 4. 795.3 Retângulo Latino incompleto R imerso no Quadrado latino T de ordem 5. 79

Lista de Algoritmos

3.1 1-fatoração do grafo de deficiência 67

Lista de Abreviaturas

Símbolo SignificadoBIBD Planejamento de Blocos Balanceado IncompletoPBD Planejamento Balanceado em ParesST S Sistema Triplo de Steiner

Lista de Símbolos

Símbolo SignificadoST S(v) Sistema Triplo de Steiner de ordem v

(S,T ) Estrutura de um Sistema Triplo de Steiner formado pelos conjuntos S e T

S Conjunto de símbolos de um Sistema Triplo de Steiner ou PBD

T Conjunto de triplas de um Sistema Triplo de Steinerv Ordem de um Sistema Triplo de Steiner|S| Cardinalidade do Conjunto S

Z Conjunto dos Números Inteirosa≡ b(mod m) Relação de Congruência: a é congruente a b módulo m

≡ Congruente(x,y) 7→ x∗ y Representação de uma operação em um grupo∗ Operação genérica em um grupo(G,∗) Grupo sobre o conjunto G e operação ∗(Z,+) Grupo aditivo dos inteiros (comutativo)(Q∗, ·) Grupo multiplicativo dos racionais (comutativo)∈ Pertence/∈ Não pertence⊆ Subconjunto∪ União de Conjuntos\ Diferença de Conjuntos= Igual< Menor> Maior≤ Menor ou igual≥ Maior ou igual−a Oposto de a

a−1 Inverso de a

Zm Conjunto dos inteiros módulo m

16

m+ Operação de Adição Módulo m

(Zm,+) Grupo Aditivo dos inteiros módulo m

n×n Matriz n por n

(Q,◦) Quasigrupo formado pelo conjunto Q e operação binária ◦(i, j) Células i e j de um quasigrupoG = (V,E) Grafo sobre o conjunto de vértices V e arestas E

|G| Ordem de um grafo G

‖G‖ Número de arestas de um grafo G

Kn Grafo Completo de ordem n

(S,B) Estrutura de um PBD, formado pelos conjuntos S e B

B Conjunto de blocos de um PBD/0 Conjunto vazio∀ Para todo, qualquer(v

2)

Combinação simples de v elementos de 2 em 2v! Fatorial de v

× Produto cartesiano∞ Infinito, representa um elemento adicional ao quasigrupo em um ST S ou PBD

KT S(v) Sistema Triplo de Kirkman de ordem v

πi Classe Paralela i

Fi 1-fator de um grafoNR( j) Quantas vezes o símbolo j aparece em R

CAPÍTULO 1Introdução

A Teoria de Planejamentos Combinatórios, do termo original Combinatorial

Design Theory, é o estudo da organização dos elementos de um conjunto finito em padrões(geralmente subconjuntos), de acordo com regras especificadas [15]. Trata-se de uma dasáreas da Matemática moderna em que podemos observar um rápido crescimento comdiversas aplicações, conforme veremos mais adiante.

A área de Combinatorial Design Theory surgiu em um nível mais formal a partirdo trabalho de Euler, por meio do desenvolvimento sistemático dos quadrados latinos, amais de 200 anos atrás. Em 1782 Euler introduziu os “36 problemas oficiais” e começoua pesquisa por pares de quadrados latinos ortogonais [12].

Outros nomes de destaque no desenvolvimento desta teoria são Kirkman, Steinere Cayley, cientistas de meados do século 19, que trabalharam em tópicos de destaque,por exemplo, sistemas triplos. No século 20, os pesquisadores Bose, Ryser, Hanani eHall também contribuiram efetivamente nesta área de pesquisa. [12]. Alguns nomes dedestaque no cenário de pesquisa contemporâneo em Combinatorial Design Theory sãoLindner, Rodger [22], Colbourn [7] e Wallis [29], além de vários outros, devido aoprogressivo desenvolvimento desta área.

Originalmente, os pesquisadores desta área tinham por objetivo consolidar ateoria de modo matematicamente coerente, a fim de definir as principais propriedadesda teoria de planejamentos combinatórios, isto sem aparentemente focar em aplicaçõespráticas. Assim, devido a natureza matemática desta teoria, ela possui laços com outrasáreas da matemática, tais como teoria dos grupos, teoria dos campos finitos, teoria dasgeometrias finitas, teoria dos números, teoria de matrizes combinatórias e teoria dosgrafos. Mas, como consequência deste desenvolvimento, as aplicações foram surgindonaturalmente, e hoje podemos encontrar exemplos de aplicações em áreas tais como teoriade informação, estatística, biologia e engenharia, e com ênfase em ciência da computação.

No contexto da ciência da computação, a Combinatorial Design Theory formauma parte valiosa do aparato necessário para resolver problemas computacionais efeti-vamente. De fato, a ciência da computação e a teoria dos planejamentos combinatóriostem muitas áreas de interseção em comum [9]. Consequentemente, esta teoria se tornou

18

um campo interdisciplinar para os pesquisadores de matemática e ciência da computação[15].

No estudo da Teoria dos Planejamentos Combinatórios, um Planejamento Com-binatório é resumidamente e intuitivamente, uma forma padrão de selecionar subconjun-tos, que chamaremos de blocos, de um conjunto finito, satisfazendo algumas propriedadesestabelecidas. Nesta teoria, o foco principal é a discussão das técnicas para construçãode diferentes planejamentos em blocos. O que vai diferenciar os diversos tipos de pla-nejamentos combinatórios é a forma de estabelecer e padronizar essas propriedades deseleção de subconjuntos. Entre os vários tipos de planejamentos combinatórios, se des-tacam duas estruturas: BIBD (planejamento de blocos balanceados incompletos) e PBD

(planejamento balanceado em pares). Um caso particular desta última estrutura são osSTS (Sistemas Triplos de Steiner), que são um tipo de PBD, em que todos os blocos temo mesmo tamanho 3, sendo chamados de triplas.

De modo geral, um planejamento combinatório será definido formalmente comoum sistema de conjuntos (S,B), em que o conjunto S será um conjunto de símbolos quais-quer e o conjunto B será formado por subconjuntos (blocos) do conjunto de símbolos, deacordo com as propriedades estabelecidas, que caracterizarão qual o tipo de planejamentocombinató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).

Como exemplo motivacional, vamos focar a atenção em um problema que ocorreem redes de comunicação. Vamos supor que há v sites nessa rede de comunicação,e precisamos estabelecer os caminhos entre estes sites. Neste contexto, uma rede embarramento poderá ser esquematizada como um sistema de conjuntos (S,B), em que S

é um conjunto de v sites, e B é um conjunto formado por subconjuntos de sites associadospor um barramento. Tal estrutura, quando particularizada com as propriedades inerentesao campo de estudo de topologia de redes, poderá ser formalizada como um planejamentocombinatório.

O problema de interconexão de redes, que consiste em estabelecer os caminhosentre os nós de entrada e os nós de saída, também pode ser formalizado como umplanejamento combinatório, como se segue: podemos definir uma rede interconectadacomo um sistema de conjuntos (V,B), onde V é o conjunto de nós, que conecta os nós deentrada, os nós de saída e os nós de switch (que retransmitem a mensagem de um canalde comunicação para outro), e B é o conjunto de links entre esses nós.

A teoria de codificação é um campo associado à criptografia, em que há a pre-ocupação de garantir a integridade da mensagem estabelecida entre as partes autorizadasno processo de comunicação remotamente, evitando que a mensagem seja alterada poralgum meio não autorizado. Os códigos de autenticação são usados a fim de minimizar apossibilidade de que alguma intercepção da mensagem não seja detectada. Um código de

19

autenticação é definido formalmente como um conjunto de estados, mensagens e regras decodificação. Ao definir os conjuntos que caracterizam esses conceitos de modo matemá-tico, os códigos de autenticação também podem ser estudados na forma de planejamentocombinatório.

Outra importante aplicação em ciência da computação é em organização dearquivos, ao estabelecer as consultas emparelhadas parciais. Até mesmo em teste desoftware, que é um campo mais prático em ciência da computação, podemos usar ateoria de planejamentos combinatórios a fim de reduzir o número de testes necessáriospara assegurar que o desempenho do software produzido está correto nas instâncias maisrazoáveis [8].

O objetivo principal deste trabalho é fazer uma introdução à Teoria de Plane-jamentos Combinatórios, com ênfase nos procedimentos de construção dos SistemasTriplos de Steiner. Construir um Planejamento Combinatório, ou particularmente, umSistema Triplo de Steiner, significa estabelecer claramente os conjuntos que formam osistema, ou seja, o conjunto de símbolos e o conjunto de blocos, conforme as proprieda-des estabelecidas.

No processo de formalização da Teoria de Planejamentos Combinatórios há a ne-cessidade de aplicação de uma razoável bagagem de Álgebra Moderna e também de Teo-ria dos Números. Por tal motivo, o capítulo 2 faz uma introdução aos conceitos prévios decongruência, grupo aditivo e de modo fundamental aos quadrados latinos e quasigrupos,que constituirão a matéria-prima básica, os “tijolinhos”, de nossas construções. Tambémveremos que alguns planejamentos combinatórios podem ser visualizados na forma degrafos, além de terem propriedades definidas na Teoria de Grafos, por isto, a última seçãodo capítulo 2 traz uma introdução sucinta à Teoria dos Grafos, nos restringindo apenasaos conceitos mais básicos, já que a Teoria dos Grafos é um campo bem abrangente.

O capítulo 3 constitui o núcleo fundamental do trabalho. Iniciamos vislumbrandouma noção intuitiva de um Planejamento Combinatório. O primeiro tipo de planeja-mento combinatório a ser discutido será o de PBD, que é um planejamento balanceadoem blocos, com um conceito bem abrangente. Particularizando o conceito geral de PBD,chegamos a uma classe importantíssima de planejamentos combinatórios: os Sistemas

Triplos de Steiner. Neste contexto, um dos principais trabalhos desta área pode ser en-contrado em [22]. Partimos desta bibliografia em termos formais, mas sempre primandopor um maior nível de detalhamento no estabelecimento das técnicas de construções eprocurando também discutir novos e diferentes exemplos.

O capítulo 4 trata sobre resolubilidade. Discutir resolubilidade nada mais édo que estabelecer quando um Sistema Triplo de Steiner é resolvível e quando não éresolvível. Neste contexto, surge o importante conceito de classe paralela. Focaremosem um problema especial, que consiste em construir um Sistema Triplo de Steiner não-

20

resolvível a partir de outro Sistema Triplo de Steiner, de modo recursivo.No capítulo 5 discutiremos sobre imersões (embeddings), que é um tópico de

grande impacto na pesquisa científica contemporânea dos Planejamentos Combinatórios.Já o capítulo 6 investiga sobre uma importante aplicação dos Planejamentos

Combinatórios à Teoria da Computação, em um tópico sobre NP-Completude.Concluímos com o capítulo 7, que traz as principais perspectivas de pesquisa

nesta área.

CAPÍTULO 2Conceitos Básicos

No desenvolvimento da Teoria dos Planejamentos Combinatórios, com foco nosSistemas Triplos de Steiner (S,T ), trabalharemos com conjuntos S de ordens v = |S|inteiras. Por tal motivo, o conjunto Z, que é o conjunto dos números inteiros, será oconjunto numérico em que focaremos, pois todas as ordens (tamanhos) dos conjuntos dossistemas triplos e planejamentos em blocos considerados serão restritas ao conjunto dosnúmeros inteiros.

Neste capítulo apresentaremos alguns conceitos e definições no campo dosnúmeros inteiros que serão úteis no desenvolvimento do trabalho.

2.1 Congruência

O conceito de congruência é de fundamental importância na Matemática paranúmeros inteiros e foi introduzido na literatura científica pelo famoso matemático KarlFriedrich Gauss (1777 - 1855). No nosso contexto, o conceito de congruência seráutilizado ao definirmos as ordens dos conjuntos dos sistemas triplos e planejamentos emblocos que consideraremos.

Abaixo segue a definição de congruência, em linguagem contemporânea:

Definição 2.1 (Congruência) Sejam a, b e m números inteiros. Diz-se que a é congru-ente a b múdulo m, e escreve-se

a≡ b(mod m)

se, e somente se, existe um número inteiro q tal que

a−b = qm

Exemplos de congruência:a) 26≡ 5(mod 7), pois 26−5 = 3×7;b) 15≡ 0(mod 3), pois 15−0 = 5×3;

2.2 Grupos 22

c) 23≡−5(mod 4), pois 23− (−5) = 7×4;Um resultado fundamental sobre congruência é apresentado na Proposição a

seguir, demonstrada em [27].

Proposição 2.2 Se m > 1, então a ≡ b(mod m) se, e somente se, a e b deixam o mesmo

resto quando dividos por m.

Da proposição acima, recai o seguinte Corolário:

Corolário 2.3 Se r é o resto da divisão de a por m, então a≡ r(mod m).

2.2 Grupos

Definição 2.4 (Grupo - definição baseada em [13]) Um sistema matemático consti-

tuído de um conjunto não vazio G e uma operação (x,y) 7→ x ∗ y sobre G é chamado

grupo se essa operação se sujeita aos seguintes axiomas:

G1) associatividade: (a∗b)∗ c = a∗ (b∗ c), quaisquer que sejam a,b,c ∈ G;

G2) existência de elemento neutro: existe um elemento e ∈ G tal que a ∗ e =

e∗a = a, qualquer que seja a ∈ G;

G3) existência de simétricos: para todo a ∈ G existe um elemento a′ ∈ G tal que

a∗a′ = a′ ∗a = e.

Definição 2.5 (Grupo Comutativo ou abeliano) É um grupo, que além das proprieda-

des da definição anterior, também apresenta o seguinte axioma:

G4) comutatividade: a∗b = b∗a, quaisquer que sejam a,b ∈ G.

Observação 2.6 A notação (G,∗) é usada para indicar um grupo, em que o símbolo ∗indica a operação sobre o conjunto G.

Exemplo 1: (Z,+) - Grupo aditivo dos inteiros (comutativo).Trata-se do sistema formado pelo conhecido conjunto dos números inteiros e a

operação de adição usual sobre esse conjunto. Para termos a certeza que realmente trata-sede um grupo, devemos verificar cada um dos axiomas da definição 2.4. Vejamos abaixo:

G1) associatividade: a adição usual é uma operação sobre Z associativa;G2) existência de elemento neutro: O número 0 é o elemento neutro da adição;G3) existência de simétricos: Todo elemento a ∈ Z tem um oposto −a ∈ Z, tal

que a+(−a) = (−a)+a = 0;Além disso, a operação de adição usual em Z também é comutativa, logo também

satisfaz ao axioma G4) estabelecido pela definição 2.5, e assim o grupo também écomutativo.

2.2 Grupos 23

Exemplo 2: (Q∗, ·) - Grupo multiplicativo dos racionais (comutativo).Trata-se do sistema formado pelo conjunto Q∗ dos racionais não nulos e a

multriplicação usual (·) sobre esse conjunto. O conjunto Q∗ é fechado em relação àmultiplicação, ou seja, o produto de dois números racionais não nulos também é umnúmero racional diferente de zero. Vejamos abaixo, a verificação dos axiomas:

G1) associatividade: a multiplicação usual é associativa em Q∗;G2) existência de elemento neutro: O número 1 é o elemento neutro da multipli-

cação;G3) existência de simétricos: Todo elemento a ∈ Q∗ tem um inverso a−1 ∈ Q∗,

tal que a ·a−1 = a−1 ·a = 1.G4) comutatividade: a multiplicação usual é comutativa em Q∗, logo o grupo é

abeliano.

Definição 2.7 (Conjunto Zm) Zm = {0,1,2, ...,m−1}, é um conjunto de exatamente m

elementos, e é chamado de conjunto dos inteiros módulo m.

Definição 2.8 (Adição Módulo m) Sejam x e y elementos do conjunto Zm =

{0,1,2, ...,m−1}. A operação,m+ definida em Zm pela regra x

m+ y = resto da divi-

são de x+ y por m, é chamada de adição módulo m [27].

Exemplos de aplicação da operação:Consideremos Z7 = {0,1,2,3,4,5,6} e apliquemos as seguintes adições:

a) 17+ 5 = (resto da divisão de 1+5 por 7) = 6

b) 37+ 4 = (resto da divisão de 3+4 por 7) = 0

c) 87+ 2 = (resto da divisão de 8+2 por 7) = 3.

Para simplificar podemos colocar os resultados da aplicação da operação em umatabela, chamada tábua da adição módulo m, que é construída colocando-se o valor dex

m+ y na linha x e coluna y. A tabela 2.1 mostra a tábua de adição de Z7.

Tabela 2.1: Tábua de Adição Módulo 7: (Z7,+).

7+ 0 1 2 3 4 5 60 0 1 2 3 4 5 61 1 2 3 4 5 6 02 2 3 4 5 6 0 13 3 4 5 6 0 1 24 4 5 6 0 1 2 35 5 6 0 1 2 3 46 6 0 1 2 3 4 5

A tabela 2.2 mostra a tábua de adição de Z8.

2.3 Quadrados Latinos e Quasigrupos 24


8+ 0 1 2 3 4 5 6 70 0 1 2 3 4 5 6 71 1 2 3 4 5 6 7 02 2 3 4 5 6 7 0 13 3 4 5 6 7 0 1 24 4 5 6 7 0 1 2 35 5 6 7 0 1 2 3 46 6 7 0 1 2 3 4 57 7 0 1 2 3 4 5 6

A estrutura (Zm,m+), formada pelo conjunto Zm, que é o conjunto dos inteiros

módulo m, conforme definição 2.7, e a operaçãom+, que é a operação de adição módulo

m, conforme definição 2.8, forma um grupo aditivo. Na prática, simplificaremos a notaçãopara (Zm,+), para representar este grupo.

A seguir, a verificação que (Zm,+) realmente é um grupo:G1) associatividade: a operação de adição módulo m é associativa em Zm;G2) existência de elemento neutro: 0 é o elemento neutro da adição módulo m;G3) existência de simétricos: Todo elemento a ∈ Zm tem um oposto−a ∈ Zm, tal

que a+(−a) = (−a)+a = 0.G4) comutatividade: a operação de adição módulo m é comutativa, logo o grupo

é abeliano.

2.3 Quadrados Latinos e Quasigrupos

Nesta seção apresentaremos os conceitos de quadrados latinos e quasigrupos.Eles serão úteis como construtores de blocos, ao aplicarmos as técnicas de construção nopróximo capítulo. É como se eles fossem os “tijolinhos” básicos para construirmos blocosbem mais complexos.

2.3.1 Quadrados Latinos

Definição 2.9 (Quadrado Latino) Um quadrado latino de ordem n é uma matriz n×n

onde cada uma das células contém exatamente um dos símbolos {1,2, ...,n}, tal que cada

linha e cada coluna da tabela contém cada um dos símbolos em {1,2, ...,n} exatamente

uma vez [22].


Figura 2.1: Exemplo de um quadrado latino de ordem 4 com asdenominações de cartas.

Figura 2.2: Exemplo de um quadrado latino de ordem 4 com osrótulos de cartas.

2.3.2 Quasigrupos

Definição 2.10 (Quasigrupo) Um quasigrupo de ordem n é um par (Q,◦), onde Q é um

conjunto de tamanho n e ◦ é uma operação binária sobre Q tal que para cada par de

elementos a,b ∈ Q, as equações a◦ x = b e y◦a = b [22].

Observação 2.11 Demonstra-se a equivalência entre quasigrupos e quadrados latinos

[22]. Assim, basta sabermos construir quadrados latinos e colocar os rótulos (de ca-

beçalho e linha lateral) juntamente com o símbolo da operação na tabela do quadrado

latino (para destacar o conjunto e a operação da definição) para o transformar em um

quasigrupo.

As definições abaixo se aplicam tanto aos quasigrupos quanto aos quadrados

latinos.

Definição 2.12 (comutativo) Um quasigrupo (ou quadrado latino) é comutativo se as

células (i, j) e ( j, i) contém os mesmos símbolos, para todo 1≤ i e j ≤ n.


Definição 2.13 (Idempotente) Um quasigrupo (ou quadrado latino) é idempotente

quando a célula (i, i) contém o símbolo i para 1≤ i≤ n.

Definição 2.14 (Semi-idempotente) Um quasigrupo (ou quadrado latino) de ordem 2n

é semi-idempotente se para o intervalo 1≤ i≤ n as células (i, i) e (n+ i,n+ i) contêm o

símbolo i.

Também mostra-se que um quasigrupo pode ser obtido a partir de um grupo

aditivo de inteiros de mesma ordem. Observamos que o grupo aditivo já é comutativo.Assim, podemos obter um quasigrupo comutativo idempotente de ordem ímpar 2n+ 1,n ≥ 1, a partir de (Z2n+1,+), que é o grupo aditivo dos inteiros módulo 2n+1, por umasimples renomeação da tabela do grupo aditivo, para se adequar ao intervalo de valoresdo quasigrupo e torná-lo idempotente. Analogamente, podemos obter um quasigrupocomutativo semi-idempotente de ordem par 2n, n≥ 1, a partir de (Z2n,+), que é o grupoaditivo dos inteiros módulo 2n, também por uma simples renomeação da tabela do grupoaditivo, para torná-lo semi-idempotente.

Para exemplificar, nos concentremos no grupo aditivo (Z7,+) do exemplo databela 2.1 da seção 2.2.

Apliquemos a seguinte operação de conversão a partir da diagonal principal databela do grupo aditivo, para renomear os elementos:

0→ 1; 1→ 5; 2→ 2; 3→ 6; 4→ 3; 5→ 7; 6→ 4;Esta renomeação, transforma a diagonal principal na sequência: 1,2,3,4,5,6,7,

ou seja, a célula (i, i) passa a conter o símbolo i para 1 ≤ i ≤ 7, o que torna a tabelaidempotente.

Após a aplicação da renomeação dos elementos conforme definido acima, che-gamos a uma nova tabela: 2.3, que afinal é um quasigrupo comutativo idempotente.

Tabela 2.3: Quasigrupo comutativo idempotente de ordem 7:(Q,◦).

◦ 1 2 3 4 5 6 71 1 5 2 6 3 7 42 5 2 6 3 7 4 13 2 6 3 7 4 1 54 6 3 7 4 1 5 25 3 7 4 1 5 2 66 7 4 1 5 2 6 37 4 1 5 2 6 3 7

Agora, voltemos ao grupo aditivo (Z8,+) do exemplo da tabela 2.2 da seção 2.2.Apliquemos a seguinte operação de conversão na tabela do grupo aditivo, para

renomear os elementos:

2.4 Grafos 27

0→ 1; 1→ 5; 2→ 2; 3→ 6; 4→ 3; 5→ 7; 6→ 4; 7→ 8.Esta renomeação, transforma a diagonal principal na sequência:

1,2,3,4,1,2,3,4, ou seja, a célula (i, i) e (4 + i,4 + i) passam a conter o símbolo i,para 1≤ i≤ 4, o que torna a tabela semi-idempotente.

Após a aplicação da renomeação dos elementos conforme definido acima, che-gamos a uma nova tabela: 2.4, que afinal é um quasigrupo comutativo semi-idempotente.

Tabela 2.4: Quasigrupo comutativo semi-idempotente de ordem 8:(Q,◦)

◦ 1 2 3 4 5 6 7 81 1 5 2 6 3 7 4 82 5 2 6 3 7 4 8 13 2 6 3 7 4 8 1 54 6 3 7 4 8 1 5 25 3 7 4 8 1 5 2 66 7 4 8 1 5 2 6 37 4 8 1 5 2 6 3 78 8 1 5 2 6 3 7 4

Uma vez que já definimos os procedimentos para construção dos quasigruposa partir dos grupos aditivos, podemos aplicar os quasigrupos como item fundamentalnas técnicas de construção dos planejamentos em blocos e sistemas triplos, conformedefiniremos no próximo capítulo.

2.4 Grafos

A Teoria dos Grafos é bastante ampla. Nesta seção destacaremos apenas as de-finições básicas que serão úteis para aplicação no contexto dos Planejamentos Combina-

tórios, que é nosso principal foco. Boas referências para um estudo mais completo emTeoria dos Grafos são: [2] , [11] e [30].

Abaixo segue a definição formal de grafo, de acordo com [11].

Definição 2.15 (Grafo) Um grafo é um par G = (V,E) de conjuntos tais que E ⊆V ×V ,

onde os elementos de E são subconjuntos de 2 elementos de V . Os elementos de V são

chamados de vértices (ou nós) do grafo G e os elementos de E são chamados de arestas(ou linhas).

Observação 2.16 (Representação de um grafo) Uma forma padrão de representar um

grafo é desenhar um ponto para cada vértice e ligar dois destes pontos (correspondentes

a dois vértices) por uma linha formando uma aresta. A figura 2.3 mostra um exemplo de

um grafo sobre o conjunto de vértices V = {1,2,3,4,5,6,7,8,9} com arestas no conjunto

E = {{1,3} ,{1,5} ,{2,4} ,{2,6} ,{3,6} ,{3,8} ,{3,9} ,{5,8}}

2.4 Grafos 28

Figura 2.3: Exemplo de um grafo.

Definição 2.17 (Ordem de um grafo) O número de vértices de um grafo G é a sua

ordem, representada por |G|. Já o número de arestas é representado por ‖G‖.

Definição 2.18 (Grafo Completo) É um grafo no qual cada par de vértices distintos está

associado por uma aresta. Um grafo completo de n vértices é denotado por Kn.

Observação 2.19 Decorre diretamente da definição acima que para cada ordem n existe

um único grafo completo.

A figura 2.4 mostra um exemplo de um grafo completo, que no caso é um K5.

Figura 2.4: Um grafo completo K5.

2.4 Grafos 29

As definições abaixo são relativas à fatoração de grafos e terão importânciafundamental para aplicação em uma construção especial no próximo capítulo.

Definição 2.20 (1-fator) 1-fator de um grafo G é um conjunto de arestas disjuntas em

pares que particionam o conjunto de vértices.

Definição 2.21 (1-fatoração) 1-fatoração de um grafo G é um conjunto de 1-fatores que

particionam o cojunto de arestas de G.

CAPÍTULO 3Planejamentos em Blocos

3.1 Planejamentos Balanceados

Um Planejamento Combinatório pode ser compreendido, de modo intuitivo,como sendo uma maneira de selecionar subconjuntos, também chamados de blocos, deum conjunto finito, de tal forma que algumas propriedades especificadas sejam satisfeitas.

Um dos principais Planejamentos Combinatórios são os Planejamentos Balan-ceados em Pares, ou PBD. Em termos formais, temos a seguinte definição para um PBD,explorada em [22]:

Definição 3.1 (Planejamento Balanceado em Pares - PBD) É um par ordenado (S,B),

onde S é um conjunto finito de símbolos, e B é uma coleção de subconjuntos de S

chamados blocos, tais que cada par de elementos distintos de S ocorrem juntos em

exatamente um bloco de B. |S| é chamado de ordem do PBD.

Pela definição acima, não há nenhuma restrição sobre a natureza do conjunto S,ou seja, ele pode ser numérico, formado por pares ordenados, caracterizado por pontos,ou quaisquer outros símbolos.

Note também que pela definição acima, os blocos que formam o conjunto B

podem ter tamanhos distintos, ou seja, podemos ter um bloco de tamanho 5, outro detamanho 3, e assim por diante.

Vale frisar que definir um sistema PBD significa esboçar os dois conjuntos queformam o par (S,B), ou seja, definir o conjunto finito S, e também exibir o conjunto B

formado por todos os subconjuntos de S, que satisfazem à propriedade da definição.Para fins de esclarecer a definição, segue o exemplo abaixo:S = {1,2,3,4,5,6,7,8,9,10,11}, um conjunto numérico, e o conjunto de blocos:B = {{1,2,3,4,5,6} ,{1,6,7} ,{1,8,9} ,{1,10,11} ,{2,6,9} ,{2,7,11} ,{2,8,10} , {3,6,11} ,{3,7,8} ,{3,9,10} ,{4,6,10} ,{4,7,9} ,{4,8,11} ,{5,6,8} ,{5,7,10} ,{5,9,11}}.Temos nesse exemplo um único bloco de tamanho 5 e todos os demais são de

tamanho 3.

3.2 Sistemas Triplos de Steiner 31

Para constatar que o conjunto dos blocos esboçados satisfazem a propriedadeda definição, devemos verificar que cada par de elementos distintos de S pertencem aum bloco, e mais do que isto, devem pertencer a um único bloco. Se aleatoriamenteescolhermos dois elementos distintos de S, por exemplo 3 e 10, veremos que este parpartence a um único bloco: {3,9,10}. Procedendo de modo análogo e verificando paratodos os demais pares de elementes distintos de S, chegaremos a essa mesma conclusão.

3.2 Sistemas Triplos de Steiner

Chamam atenção e exercem importância fundamental em pesquisa a situaçãoparticular em que cada bloco B do PBD tem tamanho único 3. Neste caso, os blocos sãotambém chamados de triplas, e temos a seguinte definição formal, também explorada em[22]:

Definição 3.2 (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 PBD em que B = T , ouseja, 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 = /0. Este é umexemplo obviamente trivial.

ii) S = {α,β,γ}, então existe uma única tripla formada pelos próprios elementosde S, logo T = {α,β,γ}.

iii) S = {1,2,3,4,5,6,7}, então temos o seguinte conjunto T formado pelastriplas:

{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, consideremos o grafo completo K7, formado

pelo seguinte conjunto de vértices: V = {1,2,3,4,5,6,7}. Nesse grafo, consideremos otriângulo ligando os vértices 1, 2 e 4, conforme representado na figura 3.1. Se rotacionar-mos esse triângulo para a direita, obteremos o triângulo 2, 3 e 5, que não possui arestaem comum com o primeiro triângulo. Se repetirmos este procedimento por mais cincorotações, teremos todas as triplas de S descritas como triângulos de K7.


Figura 3.1: Rotacionando triângulos no grafo completo K7.

De modo geral, tal como no exemplo anterior, podemos visualizar um Sistema

Triplo de Steiner de ordem v como um grafo completo Kv. Para tal procedimento, bastaassociarmos as triplas do STS com triângulos do grafo completo, mantendo a seguintepropriedade: os triângulos deverão ser constituídos de modo que cada aresta do grafocompleto pertença a um único triângulo, de modo análogo ao fato de que cada par deelementos distintos do conjunto S do ST S 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 ST S⇔ Arestas distintas do grafo

completo.A figura 3.2 mostra um exemplo de um grafo completo dividido em triângulos.

Figura 3.2: Divisão do grafo completo K7 em triângulos.

Nos exemplos preliminares que consideramos até o momento, as ordens dosSistemas Triplos de Steiner foram respectivamente: i) 1, ii) 3 e iii) 7. Baseado nadefinição de um Sistema Triplo de Steiner será que é possível construir um sistemade qualquer ordem ou há alguma restrição de ordem? Para responder a tal indagação,nos concentremos no Lema e Teorema a seguir, que trazem resultados fundamentais


e fornecem os subsídios que serão úteis para posterior aplicação nas construções dosSistemas Triplos de Steiner.

Lema 3.3 (Quantidade de triplas de um STS) A quantidade de triplas de um Sistema

Triplo de Steiner de ordem v é: |T | = v(v−1)6 .

Prova. Temos que (S,T ) é um STS de ordem v. ∀ tripla {a,b,c} contém os três subcon-juntos de dois elementos {a,b}, {b,c}, e {a,c}. Como v é a ordem do STS, a quantidadede subconjuntos de dois elementos de S é:

(v2)

= v!2!(v−2)! = 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 t1, então (a,b) /∈ tripla t2. Vimos que 1 tripla contém 3 paresde elementos distintos, logo |T | triplas contém 3|T | pares de elementos distintos. Mastambém temos que a quantidade de subconjuntos de dois elementos (pares distintos) doconjunto S é:

( v2

). Daí, chegamos que 3|T | =

( v2

), o que implica que 3|T | = v(v−1)

2 , e entãoT = v(v−1)

6 , é a quantidade de triplas de qualquer Sistema Triplo de Steiner de ordem v. �

Teorema 3.4 (Ordem de um STS) Um Sistema Triplo de Steiner (S,T ) de ordem vexiste se e somente se v≡ 1 ou 3 (mod) 6.

Prova. Primeiramente, ∀ x ∈ S, definamos um novo conjunto T (x), como segue:T (x) = {t \{x}x ∈ t ∈ T}.A descrição desse conjunto signifca que T (x) definido tendo como parâmetro

qualquer elemento x é formado pegando todas as triplas que contém o elemento x emquestão, e retirando o próprio elemento x. Essa operação transforma as triplas em pares(subconjuntos de dois elementos).

Notemos também que T (x) deve conter todos os elementos de S, com exceçãodo 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, consideremos 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,1,3}}.Se aleatoriamente, escolhermos x = 5, então:T (x) = T (5) = {{2,3} ,{4,7} ,{6,1}}, que é uma partição de S\{x}.Como conseguimos particionar S \ {x} em subconjuntos de dois elementos,

concluímos que a cardinalidade de S\{x} é par, o que significa que:|S\{x}| = v−1 é par.De v−1 par, temos diretamente que v (cardinalidade de S) é ímpar.Uma vez que descobrimos que v é ímpar, vamos agora verificar o efeito da apli-

cação de uma operação de divisão e também aplicaremos a propriedade de congruência,a fim de obtermos mais informações.


Façamos a divisão de v ímpar por 6. Então, v = 6q+ r (onde q e r são inteiros e0 < 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 (mod 6)⇒ v = 6q+1b) v≡ 3 (mod 6)⇒ v = 6q+3c) v≡ 5 (mod 6)⇒ v = 6q+5Façamos agora a verificação para cada ítem se o número encontrado v é compa-

tível com uma quantidade inteira de triplas, conforme expressão do Lema anterior.a) |T | = v(v−1)

6 = |T | = (6q+1)6q6 = (6q+1)q, que é um número exato de triplas.

b) |T | = v(v−1)6 = |T | = (6q+3)(6q+2)

6 = 6q2+5q+1, que também gera um númeroexato de triplas.

c) |T | = v(v−1)6 = |T | = (6q+5)(6q+4)

6 = 6q2 + 9q+ 206 , que devido a esta parte

fracionária, temos que para v ≡ 5(mod6) a quantidade de triplas não gera um númerointeiro.

Descartando o item c, provamos que:Se um Sistema Triplo de Steiner (S,T ) de ordem v existe então v≡ 1 ou 3 (mod

6).A recíproca do enunciado que provamos, e que consiste na segunda parte do

Teorema é:Se v≡ 1 ou 3 (mod 6) então existe um Sistema Triplo de Steiner de ordem v.A demonstração desta segunda parte consiste em mostrar que é possível construir

um sistema (o que comprova sua existência) para as ordens v ≡ 1 ou 3 (mod 6), e seráfeita nas próximas seções quando aplicaremos as técnicas de construção de sistemas.

Observação 3.5 O item c) nos mostra que os valores de v tais que v ≡ 5 (mod 6) não

geram Sistemas Triplos de Steiner, mas verificaremos mais adiante que poderemos chegar

bem próximo de um STS, sendo possível para estas ordens construir Planejamentos

Balanceados em Blocos - PBD (conforme definição de PBD já apresentada no início

desta seção).

�

3.3 A Construção de Bose 35

3.3 A Construção de Bose

A Construção de Bose é uma técnica aplicada para construção de Sistemas

Triplos de Steiner de ordem v≡ 3(mod 6).Antes de partir para a construção propriamente dita, recordemos que um Sistema

Triplo de Steiner de ordem v é caracterizado pelo par (S,T ) de conjuntos. Assim, construirum STS de ordem v significa definir claramente o par de conjuntos (S,T ).

Primeiramente, vamos definir o conjunto S de símbolos, conforme segue abaixo:v≡ 3(mod 6)⇒ v−3 = 6n⇒ v = 6n+3⇒ v = 3(2n+1).Ou seja, a ordem de v é 3 vezes a ordem 2n+ 1. Assim, nosso objetivo inicial

será encontrar um quasigrupo (Q,◦) comutativo e idempotente de ordem 2n+ 1, onde2n + 1 = v/3. No capítulo anterior vimos que estes quasigrupos existem e tambémdefinimos um procedimento para construí-los. Uma vez obtido esse quasigrupo podemosdefinir o conjunto S como segue:

S = Q × {1,2,3}.Conforme vimos anteriormente, não há nenhuma restrição sobre quais símbolos

usar para construir o conjunto S do STS, tendo em vista que o mais importante é a ordemv do conjunto S e não a escolha particular dos símbolos. Da maneira que definimos acima,o conjunto S foi caracterizado pelo produto cartesiano do conjunto Q do quasigrupo deordem 2n+1 pelo conjunto {1,2,3} de 3 elementos. Logo, o número de elementos desseproduto cartesiano é (2n+1) vezes 3, que totaliza a ordem v = 3(2n+1) para o conjuntoS do STS. Assim, conforme essa definição, os elementos (símbolos) do conjunto S serãopares ordenados (i,k) de um produto cartesiano. Uma interpretação para o conjunto S

definido por esse produto cartesiano é considerá-lo como 3 cópias dos elementos doconjunto Q do quasigrupo. Graficamente, podemos colocar os elementos do conjuntoQ em uma linha com 2n + 1 vértices, e repetir essa linha mais duas vezes, gerandotrês no total, cada uma sendo considerada um nível, totalizando um grafo de 3(2n+ 1)vértices, para representar o conjunto S de 6n+ 3 símbolos. No grafo, o par (i,k) terá aseguinte interpretação: a coordenada i será um elemento do conjunto Q do quasigrupo,onde 1 ≤ i ≤ 2n+1 e a coordenada k será o nível, onde 1 ≤ k ≤ 3. A figura 3.3 ilustra arepresentação dos vértices do grafo nas coordenadas (i,k).

Agora que já definimos o conjunto S do sistema, vamos definir o conjunto T detriplas. Teremos dois tipos distintos de triplas, conforme definido abaixo:

Tipo 1: ∀ 1≤ i≤ 2n+1, {(i,1),(i,2),(i,3)} ∈ T .Tipo 2: ∀ 1 ≤ i < j ≤ 2n+ 1, {(i,1),( j,1),(i◦ j,2)}, {(i,2),( j,2),(i◦ j,3)},

{(i,3),( j,3),(i◦ j,1)} ∈ T .As triplas podem ser desenhadas marcando-se os pares ordenados corresponden-

tes no sistema de coordenadas (i,k) construído por meio da representação das três cópias


(em três níveis) do conjunto Q do quasigrupo, conforme ilustra a figura 3.3.

Figura 3.3: Representação gráfica das triplas em um sistema decoordenadas (i,k).

Uma vez que já definimos o conjunto S e o conjunto T , agora temos um Sistema

Triplo de Steiner de ordem v = 6n+3.Para demonstrar que a construção gerada realmente é um Sistema Triplo de Stei-

ner de ordem v devemos contar o número de triplas e comparar com o número estabele-cido no Lema 3.3 e também verificar se cada par de elementos distintos pertencem a umatripla.

Formalmente, isto consiste em verificar as duas afirmações abaixo:1) cada par de elementos distintos de S pertencem a pelo menos uma tripla em

T , e2) |T | ≤ v(v−1)/6.Uma vez verificadas as duas afirmações acima conclui-se que o par (S,T ) é um

Sistema Triplo de Steiner.Para fins de verificação, vamos provar o item 2 acima na Construção de Bose:

Prova. Denotemos por |T1| o número de triplas do tipo 1 e por |T2| o número de triplas dotipo 2.

No caso das triplas do tipo 1 temos que 1≤ i≤ 2n+1, logo temos 2n+1 escolhaspara i, e portanto:

|T1| = 2n+1.


Já para as triplas do tipo 2 temos que a quantidade de escolhas para i e j é(2n+1

2)

, e cada escolha gera 3 triplas do tipo 2. Logo:

|T2| = 3(

2n+12

)= 3(2n+1)(2n)/2.

Totalizando as triplas do tipo 1 e do tipo 2 temos:|T | = |T1| + |T2|⇒ |T | = (2n+1)(3n+1) = v(v−1)/6.

�

A demonstração da outra parte (item 1) que completa a prova de que a Constru-

ção de Bose gera um Sistema Triplo de Steiner é feita em [22].Exemplo 1: Usar a Construção de Bose para construir um Sistema Triplo de

Steiner de ordem v = 9.

Observação 3.6 Vamos começar com esse exemplo em que v = 9, pois é a primeira

situação não trivial em que v≡ 3(mod 6), pois para v = 3 recaímos em um caso trivial.

Para fins de definir o conjunto S de símbolos, precisamos encontrar um quasi-grupo (Q,◦) comutativo e idempotente de ordem 2n+ 1, onde 2n+ 1 = v/3. Em nossoexemplo, a ordem do quasigrupo que precisamos é: 2n+1 = 9/3 = 3. Já o conjunto Q éQ = {1,2,3}.

Para construir um quasigrupo comutativo idempotente de ordem 3, usamos comoauxílio a tábua de adição de Z3 (que é um grupo aditivo), conforme segue na tabela 3.1.


3+ 0 1 20 0 1 21 1 2 02 2 0 1

Apliquemos a seguinte operação de conversão a partir da diagonal principal databela do grupo aditivo, para renomear os elementos:

0→ 1; 1→ 3; 2→ 2.Assim, chegamos ao quasigrupo comutativo idempodente de ordem 3, conforme

segue na tabela 3.2.Assim, o conjunto S de símbolos fica assim definido:S = Q × {1,2,3}.Ou seja:S = {1,2,3} × {1,2,3}.



◦ 1 2 31 1 3 22 3 2 13 2 1 3

Uma vez definido o conjunto S de símbolos por meio de pares ordenados,precisamos agora encontrar o conjunto T de triplas, conforme definido na Construção

de Bose.Primeiramente, as triplas do Tipo 1:∀ 1≤ i < 3, {(i,1),(i,2),(i,3)} ∈ T .Logo, temos:i = 1: {(1,1),(1,2),(1,3)},i = 2: {(2,1),(2,2),(2,3)},i = 3: {(3,1),(3,2),(3,3)}.Agora, as triplas do Tipo 2:∀ 1 ≤ i < j ≤ 3: {(i,1),( j,1),(i◦ j,2)}, {(i,2),( j,2),(i◦ j,3)},

{(i,3),( j,3),(i◦ j,1)} ∈ T .Logo, temos:1) i = 1 e j = 2: {(1,1),(2,1),(1◦2 = 3,2)}, {(1,2),(2,2),(1◦2 = 3,3)},

{(1,3),(2,3),(1◦2 = 3,1)}.2) i = 1 e j = 3: {(1,1),(3,1),(1◦3 = 2,2)}, {(1,2),(3,2),(1◦3 = 2,3)},

{(1,3),(3,3),(1◦3 = 2,1)}.3) i = 2 e j = 3: {(2,1),(3,1),(2◦3 = 1,2)}, {(2,2),(3,2),(2◦3 = 1,3)},

{(2,3),(3,3),(2◦3 = 1,1)}.Obtemos 3 triplas do Tipo 1 e 9 triplas do Tipo 2, totalizando um total de 12

triplas, que é compatível com a quantidade de triplas expressa no Lema 3.3.A figura 3.4 mostra a representação gráfica das triplas do tipo 1, e as figuras 3.5,

3.6 e 3.7 mostram a representação das triplas do tipo 2 do STS(9).Nestas figuras, cada círculo representa uma coordenada (i,k), em que i ∈ Q

do quasigrupo, e 1 ≤ k ≤ 3, onde os níveis k são representados por retângulos. Ascoordenadas (círculos) que pertencem a uma mesma tripla são unidas por linhas.


Figura 3.4: STS(9): Representação gráfica das triplas do tipo 1.

Figura 3.5: STS(9): Representação gráfica das triplas do tipo 2 -subconjunto 1.





Exemplo 2: Usar a Construção de Bose para construir um Sistema Triplo de

Steiner de ordem v = 15.Primeiramente, precisamos encontrar um quasigrupo (Q,◦) comutativo e idem-

potente de ordem 2n+ 1, onde 2n+ 1 = v/3. Logo: 2n+ 1 = 15/3 = 5 é a ordem doquasigrupo, e o conjunto Q é: {1,2,3,4,5}.

Para construir um quasigrupo comutativo idempotente de ordem 5, vamos recor-rer ao grupo aditivo (Z5,+), conforme definido por meio da tábua de adição de Z5, quesegue na tabela 3.3.


5+ 0 1 2 3 40 0 1 2 3 41 1 2 3 4 02 2 3 4 0 13 3 4 0 1 24 4 0 1 2 3

Apliquemos a seguinte operação de conversão a partir da diagonal principal databela do grupo aditivo, para renomear os elementos (objetivando tornar o quasigrupoidempotente):

0→ 1; 1→ 4; 2→ 2; 3→ 5; e 4→ 3.Assim, chegamos ao quasigrupo comutativo idempodente de ordem 5, conforme

segue na tabela 3.4.


◦ 1 2 3 4 51 1 4 2 5 32 4 2 5 3 13 2 5 3 1 44 5 3 1 4 25 3 1 4 2 5

Assim, o conjunto S de símbolos fica assim definido:S = Q × {1,2,3}.Ou seja:S = {1,2,3,4,5} × {1,2,3}.Uma vez definido o conjunto S de símbolos por meio dos pares ordenados que

constituem o produto cartesiano expresso acima, precisamos agora encontrar o conjuntoT de triplas, conforme definição formal das triplas do tipo 1 e do tipo 2 na Construção de

Bose.


Triplas do Tipo 1:∀ 1≤ i < 5, {(i,1),(i,2),(i,3)} ∈ T .Logo, temos:i = 1: {(1,1),(1,2),(1,3)},i = 2: {(2,1),(2,2),(2,3)},i = 3: {(3,1),(3,2),(3,3)}.i = 4: {(4,1),(4,2),(4,3)}.i = 5: {(5,1),(5,2),(5,3)}.Triplas do Tipo 2:∀ 1 ≤ i < j ≤ 5: {(i,1),( j,1),(i◦ j,2)}, {(i,2),( j,2),(i◦ j,3)},

{(i,3),( j,3),(i◦ j,1)} ∈ T .Logo, temos:1) i = 1 e j = 2:{(1,1),(2,1),(1◦2 = 4,2)}, {(1,2),(2,2),(1◦2 = 4,3)}, {(1,3),(2,3),(1◦2 = 4,1)}.2) i = 1 e j = 3:{(1,1),(3,1),(1◦3 = 2,2)}, {(1,2),(3,2),(1◦3 = 2,3)}, {(1,3),(3,3),(1◦3 = 2,1)}.3) i = 1 e j = 4:{(1,1),(4,1),(1◦4 = 5,2)}, {(1,2),(4,2),(1◦4 = 5,3)}, {(1,3),(4,3),(1◦4 = 5,1)}.4) i = 1 e j = 5:{(1,1),(5,1),(1◦5 = 3,2)}, {(1,2),(5,2),(1◦5 = 3,3)}, {(1,3),(5,3),(1◦5 = 3,1)}.5) i = 2 e j = 3:{(2,1),(3,1),(2◦3 = 5,2)}, {(2,2),(3,2),(2◦3 = 5,3)}, {(2,3),(3,3),(2◦3 = 5,1)}.6) i = 2 e j = 4:{(2,1),(4,1),(2◦4 = 3,2)}, {(2,2),(4,2),(2◦4 = 3,3)}, {(2,3),(4,3),(2◦4 = 3,1)}.7) i = 2 e j = 5:{(2,1),(5,1),(2◦5 = 1,2)}, {(2,2),(5,2),(2◦5 = 1,3)}, {(2,3),(5,3),(2◦5 = 1,1)}.8) i = 3 e j = 4:{(3,1),(4,1),(3◦4 = 1,2)}, {(3,2),(4,2),(3◦4 = 1,3)}, {(3,3),(4,3),(3◦4 = 1,1)}.9) i = 3 e j = 5:{(3,1),(5,1),(3◦5 = 4,2)}, {(3,2),(5,2),(3◦5 = 4,3)}, {(3,3),(5,3),(3◦5 = 4,1)}.10) i = 4 e j = 5:{(4,1),(5,1),(4◦5 = 2,2)}, {(4,2),(5,2),(4◦5 = 2,3)}, {(4,3),(5,3),(4◦5 = 2,1)}.Obtemos 5 triplas do Tipo 1 e 30 triplas (10 subconjuntos de 3) do Tipo 2,

totalizando um total de 35 triplas, que é igual à quantidade de triplas expressa no Lema3.3.

A figura 3.8 mostra a representação gráfica das triplas do tipo 1, e as figuras 3.9a 3.18 mostram a representação das triplas do tipo 2 do STS(15).


Figura 3.8: STS(15): Representação gráfica das triplas do tipo 1.


Figura 3.10: STS(15): Representação gráfica das triplas do tipo 2- subconjunto 2.










3.4 A Construção de Skolem 47



3.4 A Construção de Skolem

A Construção de Skolem é uma técnica aplicada para construção de Sistemas

Triplos de Steiner de ordem v≡ 1(mod 6).Para definir o conjunto S de símbolos, notemos o desenvolvimento da expressão

abaixo:v≡ 1(mod 6)⇒ v−1 = 6n⇒ v = 1+6n⇒ v = 1+3(2n).Para representar a ordem 2n devemos encontrar um quasigrupo (Q,◦) comutativo

semi-idempotente de ordem 2n, onde 2n = v− 1/3. No capítulo 2 discutimos sobre aexistência e maneira de construir estes quasigrupos comutativos semi-idempotentes.


Após obter o quasigrupo conforme definido acima podemos definir o conjunto S

da seguinte forma:S = {∞}

⋃(Q × {1,2,3}).

A interpretação para a definição do conjunto S é a seguinte: O produto cartesianodo conjunto Q do quasigrupo pelo conjunto {1,2,3} representa a ordem 3(2n) na expres-são v = 1+ 3(2n), o que significa fazer três cópias dos elementos do quasigrupo, quepodem ser visualizados graficamente em três níveis, em uma representação semelhante àque foi utilizada na Construção de Bose. Já o símbolo ∞ é apenas um símbolo qualquerque serve para representar a ordem 1 na expressão v = 1+ 3(2n), e não tem a interpre-tação matemática do infinito propriamente dito. Dessa forma, em um procedimento bemparecido ao que foi usado na Construção de Bose, com algumas adaptações também po-demos ter uma visualização gráfica do conjunto S: os 6n+ 1 símbolos de S podem serrepresentados em um grafo nos quais os 3(2n) = 6n vértices são os elementos do quasi-grupo copiados em três níveis (em um sistema de coordenadas (i,k) em que i ∈ Q e k éum dos três níveis) e 1 vértice é representado pelo símbolo ∞.

Uma vez que já definimos o conjunto S do sistema, vamos agora definir oconjunto T de triplas. Teremos três tipos distintos de triplas, conforme definido abaixo:

Tipo 1: ∀ 1≤ i≤ n, {(i,1),(i,2),(i,3)} ∈ T .Tipo 2: ∀ 1 ≤ i ≤ n, {∞,(n+ i,1),(i,2)}, {∞,(n+ i,2),(i,3)},

{∞,(n+ i,3),(i,1)} ∈ T .Tipo 3: ∀ 1 ≤ i < j ≤ 2n, {(i,1),( j,1),(i◦ j,2)}, {(i,2),( j,2),(i◦ j,3)},

{(i,3),( j,3),(i◦ j,1)} ∈ T .As triplas podem ser desenhadas marcando-se os pontos correspondentes no

grafo que definimos acima.

Observação 3.7 As triplas do tipo 3 são semelhantes às usadas no tipo 2 da Construção

de Bose e servem para formar as triplas que não estão combinadas com o símbolo ∞.

O procedimento para verificar que a Construção de Skolen realmente gera umSistema Triplo de Steiner é o mesmo usado na Construção de Bose.

Exemplo: Construir um Sistema Triplo de Steiner de ordem v = 13, usando aConstrução de Skolem.

Nosso objetivo inicial é encontrar um quasigrupo (Q,◦) comutativo semi-idempotente de ordem 2n, onde 2n = (v−1)/3. Logo: 2n = (13−1)/3 = 4 é a ordem doquasigrupo, e o conjunto Q é: {1,2,3,4}.

No sentido de auxiliar a construção de um quasigrupo comutativo semi-idempotente de ordem 4, recorramos ao grupo aditivo (Z4,+), conforme definido pormeio da tábua de adição de Z4, que segue na tabela 3.5.



4+ 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 3 0 1 2

Tabela 3.6: Quasigrupo comutativo semi-idempotente de ordem 4:(Q,◦).

◦ 1 2 3 41 1 3 2 42 3 2 4 13 2 4 1 34 4 1 3 2

Na tabela do grupo aditivo renomeamos os elementos da seguinte forma, paraobtermos o quasigrupo comutativo semi-idempotente:

0→ 1; 1→ 3; 2→ 2; 3→ 4.Feita esta renomeação chegamos ao quasigrupo comutativo semi-idempodente

de ordem 4, conforme consta na tabela 3.6.Assim, o conjunto S de símbolos fica assim definido:S = {∞}

⋃(Q × {1,2,3}).

Ou seja:S = {∞}

⋃({1,2,3,4} × {1,2,3}).

Lembramos que os pares ordenados (i,k), em que i ∈ Q do quasigrupo e1 ≤ k ≤ 3 é o nível, que são subconjuntos do produto cartesiano acima, poderão serrepresentados graficamente sendo considerados vértices de um grafo, juntamente como símbolo adicional ∞. Nos vértices deste grafo poderemos marcar as coordenadascorrespondentes às triplas, o que facilita o processo de visualização.

A seguir precisamos também construir o conjunto T de triplas, em conformidadecom a definição formal expressa acima, que divide as triplas em Tipo 1, Tipo 2 e Tipo 3.

Antes, vale observar que no quasigrupo temos 2n = 4, o que implica quen = 2. Omitiremos a variável n das expressões abaixo, e colocaremos apenas o seu valorcorrespondente.

Triplas do Tipo 1:∀ 1≤ i≤ 2, {(i,1),(i,2),(i,3)} ∈ T .Logo, temos:i = 1: {(1,1),(1,2),(1,3)},i = 2: {(2,1),(2,2),(2,3)},Triplas do Tipo 2:


∀ 1≤ i≤ 2, {∞,(n+ i,1),(i,2)}, {∞,(n+ i,2),(i,3)}, {∞,(n+ i,3),(i,1)} ∈ T .Logo, temos:1) i = 1 e n+ i = 3:a) {∞,(3,1),(1,2)},b) {∞,(3,2),(1,3)},c) {∞,(3,3),(1,1)}.2) i = 2 e n+ i = 4:a) {∞,(4,1),(2,2)},b) {∞,(4,2),(2,3)},c) {∞,(4,3),(2,1)}.Triplas do Tipo 3:∀ 1 ≤ i < j ≤ 4, {(i,1),( j,1),(i◦ j,2)}, {(i,2),( j,2),(i◦ j,3)},

{(i,3),( j,3),(i◦ j,1)} ∈ T .Logo, temos:1) i = 1 e j = 2:{(1,1),(2,1),(1◦2 = 3,2)}, {(1,2),(2,2),(1◦2 = 3,3)}, {(1,3),(2,3),(1◦2 = 3,1)}.2) i = 1 e j = 3:{(1,1),(3,1),(1◦3 = 2,2)}, {(1,2),(3,2),(1◦3 = 2,3)}, {(1,3),(3,3),(1◦3 = 2,1)}.3) i = 1 e j = 4:{(1,1),(4,1),(1◦4 = 4,2)}, {(1,2),(4,2),(1◦4 = 4,3)}, {(1,3),(4,3),(1◦4 = 4,1)}.4) i = 2 e j = 3:{(2,1),(3,1),(2◦3 = 4,2)}, {(2,2),(3,2),(2◦3 = 4,3)}, {(2,3),(3,3),(2◦3 = 4,1)}.5) i = 2 e j = 4:{(2,1),(4,1),(2◦4 = 1,2)}, {(2,2),(4,2),(2◦4 = 1,3)}, {(2,3),(4,3),(2◦4 = 1,1)}.6) i = 3 e j = 4:{(3,1),(4,1),(3◦4 = 3,2)}, {(3,2),(4,2),(3◦4 = 3,3)}, {(3,3),(4,3),(3◦4 = 3,1)}.Obtemos 2 triplas do Tipo 1, 6 triplas (2 subconjuntos de 3) do Tipo 2 e 18

triplas (6 subconjuntos de 3) do Tipo 3, totalizando um total de 26 triplas, que é igual àquantidade de triplas expressa no Lema 3.3.

A figura 3.19 mostra a representação gráfica das triplas do tipo 1, as figuras 3.20a 3.25 mostram a representação das triplas do tipo 2, e as figuras 3.26 a 3.31 mostram arepresentação das triplas do tipo 3 do STS(13).


Figura 3.19: STS(13): Representação gráfica das triplas do tipo 1

Figura 3.20: STS(13): Representação gráfica das triplas do tipo 2- subconjunto 1 a)

Figura 3.21: STS(13): Representação gráfica das triplas do tipo 2- subconjunto 1 b)


Figura 3.22: STS(13): Representação gráfica das triplas do tipo 2- subconjunto 1 c)

Figura 3.23: STS(13): Representação gráfica das triplas do tipo 2- subconjunto 2 a)

Figura 3.24: STS(13): Representação gráfica das triplas do tipo 2- subconjunto 2 b)


Figura 3.25: STS(13): Representação gráfica das triplas do tipo 2- subconjunto 2 c)

Figura 3.26: STS(13): Representação gráfica das triplas do tipo 3- subconjunto 1







3.5 A Construção 6n + 5 56


Observação 3.8 Até o momento, com as técnicas discutidas por meio da Construção de

Bose e Construção de Skolem temos condições de construir Sistemas Triplos de Steiner

para todas as ordens que satisfazem ao Teorema 3.4. Lembramos que a definição formal

dos procedimentos de construção dos sistemas para as ordens v ≡ 1 ou 3 (mod) 6

demonstram a segunda parte (recíproca) do Teorema. Na próxima seção estudaremos

uma ordem particular, que apesar de não caracterizar um Sistema Triplo de Steiner se

aproxima bastante.

3.5 A Construção 6n + 5

Já vimos que não é possível construir um STS para as ordens em que v ≡5(mod 6), mas nesta seção veremos que nessas situações poderemos construir um PBD

com exatamente um bloco de tamanho 5 e todos os demais de tamanho 3.Primeiramente verifiquemos o desenvolvimento da expressão abaixo:v ≡ 5(mod 6) ⇒ v− 5 = 6n ⇒ v = 5 + 6n ⇒ v = 2 + 3 + 3(2n) ⇒ v =

2+3(2n+1)Para representar a ordem 2n + 1 usaremos um quasigrupo (Q,◦) comutativo

idempotente de ordem 2n+1, onde 2n+1 = v−2/3. Esses quasigrupos são semelhantesaos que foram utilizados na Construção de Bose. A parte 3(2n+ 1) da expressão v =

2+3(2n+1) significa fazer 3 cópias do conjunto Q do quasigrupo. Já para representar ovalor inicial 2 em v = 2+3(2n+1) utilizaremos dois símbolos adicionais: ∞1 e ∞2.

Após a obtenção dos elementos acima podemos definir o conjunto S de símbolosda seguinte forma:

S = {∞1,∞2}⋃

(Q × {1,2,3}).


Além de definir um quasigrupo e dois símbolos adicionais, também usaremosuma permutação cíclica auxiliar α definida sobre os elementos de Q:

(1)(2,3, ...,2n+1)Na sequência definiremos o conjunto B de blocos, divididos em três tipos:Tipo 1:{∞1,∞2,(1,1),(1,2),(1,3)}. Esse é o único bloco de tamanho 5.Os blocos definidos abaixo são triplas:Tipo 2:∀ 1≤ i≤ n:Triplas formadas com ∞1:{∞1,(2i,1),(2i,2)}, {∞1,(2i,3),((2i)α,1)}, {∞1,((2i)α,2),((2i)α,3)}.Triplas formadas com ∞2:{∞2,(2i,2),(2i,3)}, {∞2,((2i)α,1),((2i)α,2)},

{∞2,(2i,1),((2i)α−1,3)

}.

Tipo 3:∀ 1≤ i < j ≤ 2n+1:{(i,1),( j,1),(i◦ j,2)}, {(i,2),( j,2),(i◦ j,3)}, {(i,3),( j,3),((i◦ j)α,1)}.Se substituírmos v = 6n+ 5 na expressão do Lema 3.3, e descartarmos a parte

fracionária, obteremos que |T | = 6n2 + 9n, é o número de triplas, sendo que tambémtemos um único bloco de tamanho 5 em um PBD(S,B), onde v≡ 5(mod 6).

O procedimento para demonstrar que essa construção gera um PBD com umúnico bloco de tamanho 5 e os demais de tamanho 3 (triplas) é semelhante ao citado naConstrução de Bose.

Exemplo: Construir um PBD de ordem v = 17, usando a Construção 6n+5.Precisamos utilizar um quasigrupo (Q,◦) comutativo idempotente de ordem

2n+1, onde 2n+1 = (v−2)/3. Logo: 2n+1 = (17−2)/3 = 5 é a ordem do quasigrupo,e o conjunto Q é: {1,2,3,4,5}.

Já construímos um quasigrupo comutativo idempotente de ordem 5 no Exemplo2 da seção 3.3 e vamos utilizá-lo nesta construção.

Agora, vamos definir a permutação cíclica abaixo, sobre os elementos de Q:α = (1)(2,3,4,5).⇒ 1α = 1, 2α = 3, 3α = 4, 4α = 5, 5α = 2.Também precisamos da permutação inversa de α:α−1 = (1)(5,4,3,2).⇒ 1α−1 = 1, 5α−1 = 4, 4α−1 = 3, 3α−1 = 2, 2α−1 = 5.Definição do conjunto S de símbolos:S = {∞1,∞2}

⋃(Q × {1,2,3}).

Ou seja:S = {∞1,∞2}

⋃({1,2,3,4,5} × {1,2,3}).


Definição do conjunto B de blocos:Tipo 1:{∞1,∞2,(1,1),(1,2),(1,3)}. É o único bloco de tamanho 5.Os blocos abaixo são todos de tamanho 3 (triplas):Tipo 2:Temos que 2n+1 = 5⇒ n = 2.Substituíndo o valor de n no intervalo 1≤ i≤ n,consideraremos o intervalo abaixo:1≤ i≤ 2.Para i = 1:Triplas formadas com ∞1:{∞1,(2i,1),(2i,2)}= {∞1,(2,1),(2,2)}{∞1,(2i,3),((2i)α,1)}= {∞1,(2,3),(3,1)}{∞1,((2i)α,2),((2i)α,3)}= {∞1,(3,2),(3,3)}Triplas formadas com ∞2:{∞2,(2i,2),(2i,3)}= {∞2,(2,2),(2,3)}{∞2,((2i)α,1),((2i)α,2)}= {∞2,(3,1),(3,2)}{

∞2,(2i,1),((2i)α−1,3)}= {∞2,(2,1),(5,3)}

Para i = 2:Triplas formadas com ∞1:{∞1,(2i,1),(2i,2)}= {∞1,(4,1),(4,2)}{∞1,(2i,3),((2i)α,1)}= {∞1,(4,3),(5,1)}{∞1,((2i)α,2),((2i)α,3)}= {∞1,(5,2),(5,3)}Triplas formadas com ∞2:{∞2,(2i,2),(2i,3)}= {∞2,(4,2),(4,3)}{∞2,((2i)α,1),((2i)α,2)}= {∞2,(5,1),(5,2)}{

∞2,(2i,1),((2i)α−1,3)}= {∞2,(4,1),(3,3)}

Tipo 3:∀ 1≤ i < j ≤ 5:{(i,1),( j,1),(i◦ j,2)}, {(i,2),( j,2),(i◦ j,3)}, {(i,3),( j,3),((i◦ j)α,1)}.Logo, temos:1) i = 1 e j = 2:{(1,1),(2,1),(1◦2 = 4,2)}, {(1,2),(2,2),(1◦2 = 4,3)}, {(1,3),(2,3),((1◦2)α = 5,1)}.2) i = 1 e j = 3:{(1,1),(3,1),(1◦3 = 2,2)}, {(1,2),(3,2),(1◦3 = 2,3)}, {(1,3),(3,3),((1◦3)α = 3,1)}.3) i = 1 e j = 4:{(1,1),(4,1),(1◦4 = 5,2)}, {(1,2),(4,2),(1◦4 = 5,3)}, {(1,3),(4,3),((1◦4)α = 2,1)}.4) i = 1 e j = 5:


{(1,1),(5,1),(1◦5 = 3,2)}, {(1,2),(5,2),(1◦5 = 3,3)}, {(1,3),(5,3),((1◦5)α = 4,1)}.5) i = 2 e j = 3:{(2,1),(3,1),(2◦3 = 5,2)}, {(2,2),(3,2),(2◦3 = 5,3)}, {(2,3),(3,3),((2◦3)α = 2,1)}.6) i = 2 e j = 4:{(2,1),(4,1),(2◦4 = 3,2)}, {(2,2),(4,2),(2◦4 = 3,3)}, {(2,3),(4,3),((2◦4)α = 4,1)}.7) i = 2 e j = 5:{(2,1),(5,1),(2◦5 = 1,2)}, {(2,2),(5,2),(2◦5 = 1,3)}, {(2,3),(5,3),((2◦5)α = 1,1)}.8) i = 3 e j = 4:{(3,1),(4,1),(3◦4 = 1,2)}, {(3,2),(4,2),(3◦4 = 1,3)}, {(3,3),(4,3),((3◦4)α = 1,1)}.9) i = 3 e j = 5:{(3,1),(5,1),(3◦5 = 4,2)}, {(3,2),(5,2),(3◦5 = 4,3)}, {(3,3),(5,3),((3◦5)α = 5,1)}.10) i = 4 e j = 5:{(4,1),(5,1),(4◦5 = 2,2)}, {(4,2),(5,2),(4◦5 = 2,3)}, {(4,3),(5,3),((4◦5)α = 3,1)}.Obtemos 1 bloco de tamanho 5, que é o Tipo 1. Também obtemos a seguinte

quantidade de triplas: 12 triplas do Tipo 2 e 30 triplas (10 subconjuntos de 3) do Tipo 3,totalizando um total de 42 triplas.

A figura 3.32 mostra a representação gráfica do bloco de tamanho 5. A figura3.33 mostra a representação das triplas do tipo 2, sendo que nesta figura a cor azul indicaas triplas formadas com o símbolo ∞1 e a cor vermelha indica as triplas formadas como símbolo ∞2. Já as figuras 3.34 a 3.43 mostram a representação das triplas do tipo 3,sendo que em cada figura desenhamos três triplas com três cores diferentes para facilitara visualização. Este terceiro tipo é semelhante ao Tipo 2 da Construção de Bose, com adiferença que a terceira tripla de cada subconjunto de 3 triplas é definida pela coordenada(i◦ j)α,1), e não pela coordenada (i◦ j,1). A presença da permutação cíclica α nas triplasdo Tipo 3 garante que não seja repetido nenhum subconjunto de dois elementos que játenha sido formado anteriormente.

Figura 3.32: PBD(17): Representação gráfica do bloco de tama-nho 5 - tipo 1


Figura 3.33: PBD(17): Representação gráfica das triplas do tipo2

Figura 3.34: PBD(17): Representação gráfica das triplas do tipo3 - subconjunto 1











3.6 A Construção de Wilson 64



3.6 A Construção de Wilson

Nesta seção necessitaremos dos conceitos preliminares de 1-fator e 1-fatoração,que foram definidos no capítulo 2. Inicialmente definiremos outros conceitos prévios:roda e biroda, baseados em [22], que serão úteis para aplicação em um algoritmo especialpara fins da discussão da Construção de Wilson.

Definição 3.9 (Roda) É um grafo consistindo de um ciclo de tamanho par e 1-fator no

qual as arestas ligam os vértices opostos do ciclo, chamados raios.

Uma roda pode ter 1-fatoração em três 1-fatores se considerarmos as arestasalternadas do ciclo para dois dos 1-fatores e os raios para o terceiro.


Observação 3.10 Não devemos confundir a definição de roda com grafo roda, que tem

outro significado.

A figura 3.44 mostra um exemplo de uma roda e a tabela 3.7 mostra uma 1-fatoração obtida desta roda em três 1-fatores: F0, F1 e F2. Os fatores F0 e F1 são obtidospor meio de arestas alternadas do grafo, já o fator F3 é composto pelos raios.

Figura 3.44: Uma roda R com 4 vértices.

Tabela 3.7: 1-fatoração da roda R.

1-fator F0 1-fator F1 1-fator F21 2 2 3 1 33 4 1 4 2 4

Definição 3.11 (Biroda) É um grafo consistindo da união de dois ciclos C1 e C2, com

vértices disjuntos, tais que os vértices de C1 estão associados aos vértices de C2 por um

isomorfismo.

A figura 3.45 mostra um exemplo de uma biroda em que o número de vértices épar e a tabela 3.8 mostra uma 1-fatoração obtida dessa biroda em três 1-fatores: F0, F1 eF2.


Figura 3.45: Uma biroda R sobre 12 vértices.

Tabela 3.8: 1-fatoração da biroda R.

1-fator F0 1-fator F1 1-fator F21 2 2 3 1 73 4 4 5 2 85 6 1 6 3 97 8 8 9 4 109 10 10 11 5 11

11 12 7 12 6 12

A figura 3.46 mostra um exemplo de uma biroda em que o número de vértices éímpar e a tabela 3.9 mostra uma 1-fatoração obtida desta biroda em três 1-fatores: F0, F1

e F2.

Figura 3.46: Uma biroda R sobre 10 vértices.


Tabela 3.9: 1-fatoração da biroda R.

1-fator F0 1-fator F1 1-fator F21 2 2 3 1 53 4 4 5 6 106 7 7 8 2 78 9 9 10 3 85 10 1 6 4 9

Para avançarmos também precisamos da definição de um grafo particular, con-forme segue abaixo:

Definição 3.12 (Grafo de Deficiência) O grafo de deficiência de (Zm,+), onde m≡ 1 ou

5 (mod 6), é o grafo G = (V,E) com o conjunto de vértices V = Zm \{0}, e o conjunto de

arestas E = F ∪T , tal que F = {{x,−x}|x ∈ Zm \{0}} e T = {{x,−2x}|x ∈ Zm \{0}}.

O algoritmo a seguir determina passo a passo os procedimentos para obtençãode 1-fatoração do grafo de deficiência de Zm.

Observação 3.13 Vale observar que antes de ensinar a obter 1-fatoração do grafo de

deficiência, a aplicação do algoritmo também servirá para construir o próprio grafo de

deficiência de Z7.

Algoritmo 3.1: 1-fatoração do grafo de deficiência

Entrada: Grafo G = (V,E) de deficiência de (Zm,+)

Saída: 1-fatoração de G = (V,E)

(1) Decomponha o conjunto T em ciclos C com vértices disjuntos.

(2) Se C é um ciclo de tamanho par então cada par de vértices opostos é daforma {x,−x}, ou existe outro ciclo C∗ tal que x ∈C se e somente se−x ∈C∗. Chamemos de F(C) o conjunto das arestas de F que cobrem osvértices de C ou de C∪C∗. No primeiro caso, C∪F(C) forma uma roda,com vértices em C e raios F(C). No segundo caso, C∪C∗∪F(C) formauma biroda.

(3) Se C é um ciclo de tamanho ímpar então existe um outro ciclo C∗ tal quex ∈C se e somente se −x ∈C∗. Então, C∪C∗∪F(C) forma uma biroda.

(4) A aplicação dos passos (2) e (3) particionam o grafo de deficiência emrodas e birodas. Já sabemos o procedimento para obter 1-fatoração de rodase birodas, logo, juntando todos os 1-fatores chegamos a 1-fatoração do grafode deficiência.


Exemplo: Obter 1-fatoração do grafo de deficiência de Z7.7≡ 1(mod6), pois 7−1 = 6×1.Vértices do grafo de deficiência de Z7:V = Zm \{0}= {1,2,3,4,5,6}.Todas as operações serão realizadas em (Z7,+), logo usaremos a tabela 2.1 da

seção 2.1 para nos auxiliar no desenvolvimento das operações.Inicialmente aplicaremos o Passo (1) do Algoritmo para decompor o conjunto

T = {{x,−2x}|x ∈ Z7 \{0}} em ciclos C com vértices disjuntos.Para x= 1, temos que 2x= x+x= 2, logo−2x= 5 (lembrando que−2x significa

o oposto de 2x em Z7). Assim, o par (1,5) forma a primeira aresta.Para x = 5, temos que 2x = x+ x = 3 (lembrando que a soma também é em Z7),

logo −2x = 4. Assim, (5,4) é a nossa segunda aresta.Prosseguindo desta forma, partindo da última coordenada obtida para obter a

próxima:x = 4⇒ 2x = 1⇒−2x = 6⇒ (4,6) é uma aresta.x = 6⇒ 2x = 5⇒−2x = 2⇒ (6,2) é uma aresta.x = 2⇒ 2x = 4⇒−2x = 3⇒ (2,3) é uma aresta.x = 3⇒ 2x = 6⇒−2x = 1⇒ (3,1) é uma aresta.Neste caso, o Passo (1) cobriu todos os vértices de V e decompôs todas as arestas

de T em um único ciclo C de tamanho par: {1,5,4,6,2,3}.Se temos um único ciclo de tamanho par, então pelo Passo (2) os vértices opostos

da forma (x,−2x) que formam o conjunto F devem pertencer a este ciclo. Já que nãotemos nenhum ciclo de tamanho ímpar, então podemos descartar o Passo (3).

Prosseguindo pelo Passo (2):Para x = 1, temos que −x = 6. Para x = 5, temos que −x = 2. Para x = 4, temos

−x = 3. Ou seja, F(C) = {(1,6),(2,5),(3,4)}. A união do ciclo C com os raios de F(C)

formam uma roda sobre 6 vértices, conforme ilustrado pela figura 3.47.Para aplicarmos o Passo (4) devemos obter 1-fatoração da roda sobre 6 vértices,

que neste caso, também será 1-fatoração do grafo de deficiência de Z7, conforme a tabela3.10.


Tabela 3.10: 1-fatoração do grafo de deficiência de Z7.

1-fator F0 1-fator F1 1-fator F21 3 2 3 1 62 6 4 6 2 54 5 1 5 3 4

Figura 3.47: O grafo de deficiência de Z7.

Já discutimos as técnicas para construção de Sistemas Triplos de Steinerpara todas as ordens válidas (v ≡ 1 ou 3(mod)6), por meio da Construção de Bose eConstrução de Skolem. A Construção de Wilson é uma nova ferramenta que permiteconstruir Sistemas Triplos de Steiner para as ordens v ≡ 1 ou 3(mod)6. Primeiramente,


acompanhemos o desenvolvimento das expressões abaixo, decorrentes da aplicação depropriedades de congruência:

v≡ 1(mod)6⇒ v−2≡ 5(mod)6 (I)v≡ 3(mod)6⇒ v−2≡ 1(mod)6 (II)De (I) e (II), concluímos que v≡ 1 ou 3(mod)6⇒ v−2≡ 1 ou 5(mod)6.Observamos que para a ordem v− 2 estabelecida acima, é possível obter 1-

fatoração do grafo de deficiência de Zv−2, pois v−2≡ 1 ou 5(mod)6.Para construir um Sistema Triplo de Steiner de ordem v ≡ 1 ou 3(mod)6, a

Construção de Wilson define o seguinte conjunto S de símbolos:S = {∞1,∞2}

⋃Zv−2.

A cardinalidade de Zv−2 é v−2. Logo, os dois símbolos adicionais em {∞1,∞2}servem para tornar v a ordem do conjunto S.

Agora, a definição do conjunto T de triplas:Tipo 1: {{x,y,z}|x+ y+ z≡ 0(mod(v−2))}, onde x,y,z são elementos distintos

em Zv2 \{0}Tipo 2: Os subconjuntos de dois elementos de Zv−2 \ {0} não cobertos pelas

triplas do Tipo 1 são subconjuntos do grafo de deficiência de Zv−2. Já vimos anteriormenteque é possível obter 1-fatoração do grafo de deficiência em três 1-fatores: F0, F1 e F2. Astriplas a seguir combinam os subconjuntos de dois elementos do grafo de deficiênciade Zv−2 com os símbolos 0, ∞1 e ∞2, que não pertencem ao grafo de deficiência. Acombinação é feita por meio dos 1-fatores para evitar qualquer repetição de subconjuntode dois elementos nas triplas.

T0 = {{0,x,y}|{x,y} ∈ F0},T1 = {{∞1,x,y}|{x,y} ∈ F1},T0 = {{∞2,x,y}|{x,y} ∈ F2}.Tipo 3: {0,∞1,∞2}. Esta combinação é necessária, pois no tipo anterior estes

elementos não apareceram combinados entre si.O conjunto T de triplas é formado pelos três tipos de triplas definidos acima.Exemplo: Usar a Construção de Wilson para construir um ST S(9).Já havíamos construindo este sistema anteriormente, por meio da Construção de

Bose, em que os símbolos são pares ordenados de um produto cartesiano, mas vamosconstruí-lo novamente, agora usando a Construção de Wilson, que traz uma forma maissintética para a construção de sistemas e usa um conjunto de símbolos que não está noformato de pares ordenados, conforme definimos acima.

Primeiramente, vamos encontrar o conjunto S de símbolos.Temos que v = 9, logo v−2 = 7. Assim, vamos utilizar o grafo de deficiência de

Z7 que já construímos anteriormente (conforme figura 3.47). Logo:S = {∞1,∞2}

⋃Z7 é o conjunto de símbolos.


Agora, devemos encontrar o conjunto T de triplas:Tipo 1: {1,2,4}, {3,5,6} são triplas em que os elementos satisfazem a equação

expressa no Tipo 1.Tipo 2: Já temos 1-fatoração do grafo de deficiência de Z7, conforme tabela 3.10.

Utilizando esta 1-fatoração, chegamos às triplas abaixo:{0,1,3} ,{0,2,6} ,{0,4,5}{∞1,2,3} ,{∞1,4,6} ,{∞1,1,5}{∞2,1,6} ,{∞2,2,5} ,{∞2,3,4}Tipo 3: {0,∞1,∞2}.

CAPÍTULO 4Resolubilidade

4.1 Classes Paralelas e STS resolvíveis

Começamos com as definições abaixo, baseadas em [22]:

Definição 4.1 (Classe Paralela) Uma classe paralela em um Sistema Triplo de Steiner

(S,T ) é um conjunto de triplas em T que particionam o conjunto S.

Definição 4.2 (STS Resolvível) Um Sistema Triplo de Steiner (S,T ) é resolvível se as

triplas em T podem ser particionadas em classes paralelas. Também podemos chamar

um STS resolvível de Sistema Triplo de Kirkman - KTS(v).

Observação 4.3 Quando não é possível particionar as triplas em classes paralelas,

então dizemos que o sistema é não-resolvível.

Para ilustrar a definição de classe paralela, voltemos ao Exemplo 1 da seção 3.3do capítulo anterior.

Neste exemplo, os símbolos do conjunto S são pares ordenados de um produtocartesiano. Vamos fazer um arranjo, renomeando os pares ordenados para númeroscardinais simples, conforme segue abaixo:

(1,1)⇒ 1;(1,2)⇒ 2;(1,3)⇒ 3;(2,1)⇒ 4;(2,2)⇒ 5;(2,3)⇒ 6;(3,1)⇒ 7;(3,2)⇒ 8;(3,3)⇒ 9.Após esta renomeação, ficará fácil visualizar um KT S(9), ou seja, um ST S(9)

resolvível, com as triplas particionadas em 4 classes paralelas: π1, π2, π3 e π4, conformesegue:

4.1 Classes Paralelas e STS resolvíveis 73

π1

1 2 34 5 67 8 9π2

1 4 82 5 93 6 7π3

1 5 72 6 83 4 9π4

2 4 73 5 81 6 9Em [22] também encontramos dois importantes fatos sobre KT S(v), conforme

listados abaixo:1) O número de classes paralelas é: (v−1)/2;2) O número de triplas em cada classe paralela é v/3;Para exemplificar, em um Sistema Triplo de Steiner resolvível de ordem v = 15,

ou seja, um KT S(15), teremos pelo fato 1) acima que o sistema será particionado em(v−1)/2= (15−1)/2= 7 classes paralelas, sendo em que em cada classe paralela haveráv/3 = 15/3 = 5 triplas (pelo fato 2).

Também poderíamos indagar se existem Sistemas Triplos de Steiner resolvíveispara todas as ordens, ou se sua existência é limitada a alguma ordem específica. A respostaà tal indagação é expressa pelo Teorema abaixo:

Teorema 4.4 (Existência de STS resolvível) Existe STS(v) resolvível se e somente se

v≡ 3(mod 6).

Prova. Demonstração feita por Ray-Chaudhuri e Wilson, em 1971 [24]. �

Observação 4.5 É importante observar que este teorema afirma que para uma ordem v,

em que v≡ 3(mod 6), existe STS(v) resolvível, mas isto não impede que para esta mesma

ordem v também exista STS(v) não-resolvível. É neste contexto que definimos o problema

que trataremos na próxima seção, que consiste em construir STS(v) não-resolvíveis na

classe de ordens v≡ 3(mod 6) em que STS(v) resolvíveis existem.

4.2 Construíndo STS não-resolvíveis 74

4.2 Construíndo STS não-resolvíveis

Nosso objetivo principal será construir, de modo recursivo, um STS não-resolvível, a partir de um STS já conhecido. Em [5] obtemos a fundamentação teóricapara esta construção, a qual esboçaremos abaixo, com riqueza de detalhes.

Seja (X ,β) um ST S(v), em que v ≡ 1(mod 6). Partindo deste ST S(v), objeti-vamos construir um (Z,γ), ST S(2v+ 1), em que 2v+ 1 ≡ 3(mod 6). Vale lembrar queaplicando propriedades de congruência: v≡ 1(mod 6)⇒ 2v+1≡ 3(mod 6).

O conjunto X é assim definido:X = {1,2,3, ...,v}.A partir de X , definimos Z:Z = {1,2,3, ...,v,v+1,v+2, ...,2v+1}.Agora, vamos definir um novo conjunto Y , como sendo a diferença entre os

conjuntos Z e X :Y = Z \X = {v+1,v+2, ...,2v+1}.Seja n a cardinalidade do conjunto Y . Logo:n = |Y |= |Z| \ |X |= (2v+1)− v = v+1.Como v é a ordem do ST S (X ,β), então temos claramente que v é ímpar, e, por

consequência, v+1 é par. Logo: n = |Y | é par. Usaremos este resultado mais adiante.Uma vez que já temos n, vamos construir Kn, o grafo completo de ordem n,

rotulando o conjunto de vértices V com os elementos do conjunto Y . Em seguida vamosobter 1-fatoração de Kn: {F1,F2,F3, ...,Fn−1}. Também temos que v = n− 1, logo esta1-fatoração pode ser reescrita da seguinte forma: {F1,F2,F3, ...,Fv}. Mais detalhes sobre1-fatoração de grafos completos Kn podem ser encontrados em [7].

Agora, para cada fator Fi, em que 1 ≤ i ≤ v, adicionamos o elemento i a cadaaresta em Fi, e chamamos o resultado de Ti: o conjunto de triplas contendo i. Este resultadocombina os elementos de Y (pois os 1-fatores Fi são formados por subconjuntos de doiselementos de Y ) com os elementos de X (pois i ∈ X), formando triplas.

Assim, fazendo a união de todos estes novos conjuntos de triplas Ti, (⋃v

i=1 Ti),com as triplas já formadas em β, chegamos ao conjunto de triplas γ.

Desta forma completamos o sistema de conjuntos (Z,γ), conforme segue abaixo:Z = X ∪Y , é o conjunto de símbolos.γ = β∪ (

⋃vi=1 Ti), é o conjunto de triplas.

Com a definição do conjunto de sistemas (Z,γ) construímos um ST S(2v+ 1),onde 2v+1≡ 3(mod 6), recursivamente, a partir de um ST S(v), onde v≡ 1(mod 6).

Primeiramente veremos um exemplo que ilustra esta construção, e em seguidatrataremos sobre a não-resolubilidade.


Exemplo: A partir de um ST S de ordem v = 7, construir recursivamente um ST S

de ordem 2v+1 = 15.Já construímos um ST S de ordem 7 na seção 3.2, utilizando rotação de triângulos.

Outra solução seria construir um ST S(7) facilmente por meio da Construção de Skolem eem seguida renomear os pares ordenados para números cardinais simples.

Seja (X ,β) o sistema de conjuntos que define este ST S(7). Logo, utilizando aconstrução já feita na seção 3.2, temos:

X = {1,2,3,4,5,6,7}, é o conjunto de símbolos.β = {{1,2,4} ,{2,3,5} ,{3,4,6} ,{4,5,7} ,{5,6,1} ,{6,7,2} ,{7,1,3}}, é o

conjunto de triplas.A partir deste ST S de ordem v = 7, em que 7 ≡ 1(mod 6), nosso objetivo é

construir recursivamente um ST S de ordem 2v+ 1 = 15, em que 15 ≡ 3(mod 6). Seja oconjunto de sistemas (Z,γ) o ST S(15) que almejamos construir.

Z = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}.O conjunto auxiliar Y é definido pela diferença entre os conjuntos Z e X :Y = Z \X = {8,9,10,11,12,13,14,15}.Logo, a cardinalidade n do conjunto Y é:n = |Y |= |Z| \ |X |= (2v+1)− v = v+1 = 8.A próxima etapa é construir Kn, o grafo completo de ordem n = 8, ro-

tulando o conjunto de vértices V com os elementos do conjunto Y , ou seja:Y = {8,9,10,11,12,13,14,15}. Em seguida devemos obter 1-fatoração de K8:{F1,F2,F3,F4,F5,F6,F7}.

A figura 4.1 ilustra um grafo completo K8 já com 1-fatoração em 7 1-fatores,sendo que as arestas de um mesmo 1-fator estão desenhadas com a mesma cor, e as arestasde 1-fatores distintos estão desenhadas com cores distintas.

Figura 4.1: 1-fatoração do grafo completo K8.


Os 7 1-fatores que formam 1-fatoração de K8 são:F1 = {{8,9} ,{10,11} ,{12,13} ,{14,15}}F2 = {{8,10} ,{9,11} ,{12,14} ,{13,15}}F3 = {{8,11} ,{9,10} ,{12,15} ,{13,14}}F4 = {{8,12} ,{9,13} ,{10,14} ,{11,15}}F5 = {{8,13} ,{9,12} ,{10,15} ,{11,14}}F6 = {{8,14} ,{9,15} ,{10,12} ,{11,13}}F7 = {{8,15} ,{9,14} ,{10,13} ,{11,12}}Para cada fator Fi, em que 1≤ i≤ v, adicionamos o elemento i a cada aresta em

Fi, e obtemos os conjuntos Ti, conforme segue abaixo:T1 = {{1,8,9} ,{1,10,11} ,{1,12,13} ,{1,14,15}}T2 = {{2,8,10} ,{2,9,11} ,{2,12,14} ,{2,13,15}}T3 = {{3,8,11} ,{3,9,10} ,{3,12,15} ,{3,13,14}}T4 = {{4,8,12} ,{4,9,13} ,{4,10,14} ,{4,11,15}}T5 = {{5,8,13} ,{5,9,12} ,{5,10,15} ,{5,11,14}}T6 = {{6,8,14} ,{6,9,15} ,{6,10,12} ,{6,11,13}}T7 = {{7,8,15} ,{7,9,14} ,{7,10,13} ,{7,11,12}}Façamos a união de todos os conjuntos de triplas Ti, (

⋃vi=1 Ti), com as triplas já

formadas em β, para chegarmos ao conjunto de triplas γ:γ = β∪ (

⋃vi=1 Ti)

Já havíamos definido o conjunto de símbolos Z, em que Z = X ∪Y .Com esta construção concluímos que o sistema de conjuntos (Z,γ) é um

ST S(15).Até aqui definimos um procedimento para construirmos um ST S(2v+1) recur-

sivamente a partir de um ST S(v). Mas ainda não temos condições de afirmar a não-resolubilidade do sistema. Para tal, necessitamos de um novo conceito, conforme defi-nição abaixo, a fim de utilizarmos no próximo teorema para tratarmos sobre a existênciade ST S(2v+1) não resolvível.

Definição 4.6 (Configuração de Pasch) É um conjunto de quatro triplas da forma:

{{a,b,c} ,{a,x,y} ,{b,x,z} ,{c,y,z}}.

Teorema 4.7 (Existência de ST S(2v+1) não-resolvível) Para v ≡ 1(mod 6) existe um

ST S(2v+1) que não é resolvível.

Prova. Primeiramente vamos especificar a construção que definimos para que exista umaConfiguração de Pasch. Para tal, seja {x,y,z} um bloco em β e seja a,b,c elementosem Y . Devemos afirmar que os elementos x,y,z podem ser relacionados aos três 1-fatoresdistintos contendo os pares ab,ac,bc. Então, teremos uma Configuração de Pasch dife-renciada formada pelo seguinte conjunto de triplas: {{x,y,z} ,{x,a,b} ,{y,a,c} ,{z,b,c}}.


Para comprovar esta afirmação, recordemos que em nossa construção, a tripla Ti é for-mada adicionando o elemento i ∈ X ao 1-fator Fi, em que os elementos de Fi pertencemao conjunto Y . Logo, se o par ab está no fator Fx então temos a tripla {x,a,b}. Já se o parab não está no fator Fx mas em outro fator Fx′ , basta inverter os índices x e x′, para queonde tínhamos a tripla {x′,a,b} teremos a tripla {x,a,b}. Fazendo esta mesma verificaçãopara os demais elementos, concluímos que esta configuração é sempre possível, bastandorenomear os índices se for o caso.

A próxima etapa é substituir as quatro triplas da Configuração de Pasch paraobtermos a nova configuração: {{a,b,c} ,{a,x,y} ,{b,x,z} ,{c,y,z}}. Esta mudança foifeita apenas rearranjando os elementos das triplas no conjunto das quatro triplas semacrescentar novo elemento e também sem retirar elemento já existente. Mesmo com estearranjo neste conjunto de quatro triplas, o resultado ainda permanece um Sistema Triplo

de Steiner. Agora, vamos supor por contradição que o ST S é resolvível e seja P1 a classeparalela que contenha a tripla {a,x,y}. Temos que as triplas {a,b,c}, {b,x,z} e {c,y,z}não podem pertencer a classe paralela P1, pois estas triplas possuem elementos em comumcom {a,x,y}. Logo, as outras triplas que aparecem em P1 ou são formadas apenas porelementos de X e não possuem elementos de Y (triplas do conjunto β), ou são formadaspor 1 elemento de X e dois elementos de Y (triplas do conjunto Ti, o que totaliza um múl-tiplo de dois, ou seja, 2m destas triplas. Mas, {a,x,y} também pertence à classe paralelaP1 e possui um único elemento a ∈ Y . Isto resulta que 2m+1, ou seja, um número ímpar,é a quantidade de elementos de Y na classe paralela P1. Mas todos os vértices de Y devempertencer a classe paralela Pi, o que tem como consequência que |Y | também seja ím-par. Mas quando definimos a construção já havíamos demonstrado que |Y | é par, e assimchegamos a uma contradição. Portanto, concluímos que o ST S(2v+1) não é resolvível. �

Corolário 4.8 Existe um ST S(v) não-resolvível, para v≡ 3(mod 12) e v > 3.

Prova. Pelo teorema anterior existe um ST S(2v′+1) não-resolvível, para v′ ≡ 1(mod 6).Façamos v = 2v′+1, logo v′ = (v−1)/2 (I). Mas, v′ ≡ 1(mod 6) implica que v′ = 6n+1(II). Igualando (I) e (II) temos: (v− 1)/2 = 6n+ 1, o que resulta em v = 3+ 12n, que éequivalente a v≡ 3(mod 12). �

Teorema 4.9 Para todo v≡ 3(mod 6), v > 9, existe um ST S(v) não-resolvível.

Prova. Encontrada em [5]. Esta demonstração utiliza uma construção direta, que é aConstrução de Wilson, que foi definida na seção 3.6. �

CAPÍTULO 5Imersões

Neste capítulo trataremos sobre as imersões (embeddings) no contexto dos Pla-nejamentos Combinatórios. Matematicamente, uma imersão ocorre quando uma instânciade alguma estrutura matemática está inserida (imersa) em outra instância dessa estrutura.Em nosso contexto, estas instâncias poderão ser: Sistemas Triplos de Steiner (completos),Sistemas Triplos de Steiner parciais (conforme definiremos mais adiante), quadrados la-tinos e até mesmo retângulos latinos incompletos. Iniciaremos definindo e investigandoeste último.

Definição 5.1 (Retângulo Latino incompleto r× s - conforme [22]) Um retângulo la-

tino incompleto R sobre o conjunto de símbolos S é uma matriz r× s (podendo ocorrer

r = s) em que cada símbolo em S ocorre no máximo uma vez em cada linha e em cada

coluna, sendo que cada célula contém exatamente um símbolo.

Observação 5.2 Quando temos r = s= n, então é claro que o retângulo latino incompleto

se torna um quadrado latino.

Um retângulo latino incompleto r× s R está imerso em um quadrado latino T deordem t se a matriz r× s que ocorre no canto superior esquerdo de T é R.

Para ilustrar a aplicação da definição acima, o próximo exemplo mostra a imersãode um retângulo latino incompleto em um quadrado latino.

Consideremos o quadrado latino T de ordem 5, conforme tabela 5.1.Agora, consideremos o retângulo latino incompleto R de dimensão 3 x 4 sobre

os símbolos 1,2,3,4,5, conforme tabela 5.2.

Tabela 5.1: Quadrado latino T de ordem 5.

1 4 2 5 34 2 5 3 12 5 3 1 45 3 1 4 23 1 4 2 5

79

Tabela 5.2: Retângulo latino incompleto R de dimensão 3 x 4.

1 4 2 54 2 5 32 5 3 1

Tabela 5.3: Retângulo Latino incompleto R imerso no Quadradolatino T de ordem 5.

1 4 2 5 34 2 5 3 12 5 3 1 45 3 1 4 23 1 4 2 5

Temos que este retângulo latino incompleto R de dimensão 3 x 4 está imerso noquadrado latino T , conforme podemos verificar em destaque na tabela 5.3.

Mas a questão crucial a se investigar é: Quais são as condições que nos permitemafirmar se um determinado retângulo latino incompleto r× s pode ser imerso em umquadrado latino de ordem t?

A resposta a tal indagação é respondida pelo Teorema a seguir:

Teorema 5.3 (Condição de Ryser) O retângulo latino incompleto R de dimensão r× s

pode ser imerso em um quadrado latino T de ordem t se e somente se NR( j) ≥ r+ s− t

para 1≤ j ≤ t.

Prova. É encontrada em [22]. A segunda parte envolve a aplicação da propriedade decoloração de arestas em grafos bipartidos. �

Observação 5.4 A notação NR( j) indica quantas vezes o símbolo j aparece em R.

Agora vamos partir do contexto dos retângulos latinos incompletos e dos qua-drados latinos para um campo mais abrangente, que são os Sistemas Triplos de Steiner.E a questão preponderante é investigar se há alguma condição que determina quando umSTS pode ser imerso em outro STS. O Teorema a seguir determina esta condição.

Teorema 5.5 (Imersões de Sistemas Triplo de Steiner completos) Um Sistema Triplo

de Steiner de ordem u pode ser imerso em um Sistema Triplo de Steiner de ordem v > u

se e somente se u e v são admissíveis e v≥ 2u+1.

Prova. Encontrada em [14]. �

80

Observação 5.6 Dizer que um Sistema Triplo de Steiner de ordem v é admissível,

significa que v é um inteiro que satisfaz v≡ 1,3(mod 6).

Uma vez já discutido a existência das imersões no contexto dos Sistemas Triplosde Steiner (completos), vamos focar em um novo e interessante conceito que é o deSistema Triplo de Steiner parcial, conforme definição abaixo.

Definição 5.7 (Sistema Triplo de Steiner parcial) Um Sistema Triplo de Steiner parcial

de ordem v é um par (X ,P), onde X é um conjunto com v elementos e P é um conjunto de

triplas escolhidas de X tais que cada par de elementos de X ocorre em no máximo uma

única tripla.

Observação 5.8 (Diferença entre um STS completo e um STS parcial) Quando usa-

mos a terminologia Sistema Triplo de Steiner completo nos referimos simplesmente a

um Sistema Triplo de Steiner, conforme definição feita no capítulo 3. Nesta definição te-

mos que cada par de elementos distintos do conjunto de símbolos deve ocorrer em uma

única tripla. Já na definição de Sistema Triplo de Steiner parcial cada par de elementos

distintos do conjunto de símbolos deve ocorrer em no máximo uma única tripla, o que

significa que um determinado par de símbolos distintos pode não ocorrer em nenhuma

tripla.

No capítulo 3 também mostramos que um Sistema Triplo de Steiner de ordemv pode ser representado como um grafo completo de ordem v, ou seja, Kv. O mesmoprocedimento podemos fazer com relação aos Sistemas Triplos de Steiner parciais, eassim, chegamos a definição alternativa abaixo.

Definição 5.9 (Sistema Triplo de Steiner parcial visto em um Grafo Completo) Um

Sistema Triplo de Steiner parcial de ordem v é um par (X ,P), onde X é uma coleção de

triplas (triângulos) com arestas disjuntas do conjunto de arestas do grafo completo Kv

com vértices no conjunto X.

A figura 5.1 mostra um exemplo de um Sistema Triplo de Steiner parcial deordem 9, como um subconjunto do grafo completo K9. Neste STS parcial algumas arestasdo grafo completo, por exemplo (1,4) e (3,7), não foram utilizadas para formar as triplas(triângulos do grafo completo). Já se tivéssemos um STS completo, todas as arestas dografo completo formariam triplas. Esta é a principal diferença entre um STS completo eum STS parcial.

81

Figura 5.1: Representação de um Sistema Triplo de Steiner parcialde ordem 9.

Um Sistema Triplo de Steiner parcial (X ,P) está imerso em um Sistema Triplode Steiner parcial (X ′,P′) se X ⊆ X ′ e P⊆ P′. Consequentemente, um Sistema Triplo deSteiner parcial (X ,P) está imerso em um Sistema Triplo de Steiner (completo) (X ,T ) seP⊆ T .

O problema principal é determinar quais as condições em que é possível que umSistema Triplo de Steiner parcial seja imerso em um Sistema Triplo de Steiner (completo).O Teorema a seguir esclarece essa questão.

Teorema 5.10 (Conjectura de Lindner) Qualquer Sistema Triplo de Steiner parcial de

ordem u pode ser imerso em um Sistema Triplo de Steiner de ordem v se e somente se

v≡ 1,3(mod 6) e v≥ 2u+1.

Prova. O enunciado deste Teorema foi inicialmente proposto na forma de conjectura. Massua demonstração completa pode ser encontrada no trabalho de BRYANT e HORSLEY[3]. �

82

A Teoria de imersões é bastante ampla e seu escopo de aplicação engloba outrasestruturas matemáticas. Por exemplo, o trabalho de [21] mostra a imersão de SistemasTriplos de Steiner em sistemas triplos de hexágono. Já o trabalho de [1] mostra a imersãode sistemas de 5-ciclos em sistemas triplos de pentágono.

CAPÍTULO 6NP-Completude e Planejamentos Combinatórios

A NP-Completude é um tópico da Teoria da Computação associada ao estudo daComplexidade de Tempo. Neste capítulo exibiremos alguns problemas em Planejamen-tos Combinatórios, particularmente relacionados aos Sistemas Triplos de Steiner, quesejam NP-Completos. Mas, antes disso façamos um breve resumo sobre os conceitos bási-cos de Complexidade de Tempo, que são as classes de complexidade P, NP, NP-Completo,

NP-Difícil, que são definidas por meio das linguagens da Teoria da Computação. Os con-ceitos de Máquina de Turing e linguagens são fundamentais em Teoria da Computaçãoe juntamente com as definições abaixo podem ser estudados detalhadamente em [28].

Definição 6.1 (Classe P) P é a classe de linguagens que são decidíveis em tempo poli-

nomial sobre uma máquina de Turing determinística de uma única fita.

Definição 6.2 (Classe NP) NP é a classe das linguagens que têm verificadores de tempo

polinomial.

Comparativamente, P é a classe das linguagens para as quais pertinência podeser decidida rapidamente (em tempo polinomial). Já NP é a classe das linguagens paraas quais pertinência pode ser verificada rapidamente (em tempo polinomial). Nestecontexto decidida e verificada são termos distintos e decorrem dos conceitos de decisore verificador, respectivamente. Um decisor é um tipo de Máquina de Turing capaz dedecidir uma linguagem. Já, um verificador é um algoritmo para verificar se uma cadeia éum membro de uma linguagem.

Definição 6.3 (NP-Completude) Uma linguagem B é NP-Completa se satisfaz duas

condições: 1) B está em NP; e 2) toda A em NP é redutível em tempo polinomial a B.

Os problemas que são NP-Completos são aqueles em que a complexidadeindividual está relacionada à complexidade da classe inteira.

Definição 6.4 (NP-Difícil) Um problema é NP-Difícil se todos os problemas em NP são

redutíveis a ele em tempo polinomial, mesmo que ele próprio possa não estar em NP.

84

Agora, vamos partir para nossas aplicações. No capítulo anterior, verificamosas condições em que é possível que um Sistema Triplo de Steiner parcial seja imerso emum Sistema Triplo de Steiner completo. Um resultado interessante sobre NP-Completude,decorre do trabalho de [6], que mostrou que o problema de decidir se um Sistema Triplo deSteiner parcial de ordem u pode ser imerso em um Sistema Triplo de Steiner completo deordem w, para qualquer w≤ 2u−1 é NP-Completo. O mesmo trabalho também mostrouque o problema de decisão de verificar se um quasigrupo comutativo parcial pode sercompletado em um quasigrupo comutativo (completo) também é NP-Completo.

No capítulo 4 tratamos sobre resolubilidade. Lá vimos que um Sistema Triplode Steiner é resolvível se as suas triplas podem ser particionadas em classes paralelas.Também vimos que Sistemas Triplos de Steiner resolvíveis existem somente para asordens v, em que v ≡ 3(mod 6). No contexto da NP-Completude uma questão idealpara abordagem seria: Dado um Sistema Triplo de Steiner de ordem v, em que v ≡3(mod 6), decidir se este sistema contém uma classe paralela. No capítulo 4 tambémvimos que uma classe paralela é um conjunto de v/3 triplas que particionam o conjuntode símbolos. Mas, segundo o trabalho de [20], ainda não se sabe afirmar se este problemade decisão é NP-Completo ou não. A dificuldade maior decorre do fato de que é difícilidentificar um problema já conhecido que seja NP-Completo, do qual uma reduçãoem tempo polinomial para instâncias do Sistema Triplo de Steiner possa ser derivada.Entretanto, se simplificarmos o problema, e considerarmos Sistemas Triplos de Steinerparciais (conforme definido no capítulo anterior), ao invés dos Sistemas Triplos deSteiner (completos), este problema de decisão se torna NP-Completo. Abaixo, segue aformulação deste problema, adaptado do trabalho de LI e TOULOUSE [20].

Problema (PSTS-1-RES): Dado um STS(6n + 3) parcial, ele contém uma classeparalela?

Para solução deste problema precisamos definir o seguinte problema abaixo:Problema (X3X) - Cobertura Exata por 3 conjuntos: Suponha que V é um

conjunto de pontos onde |V | = 3q e B é uma família de triplas de(v

3)

. B contém umsubconjunto B′, tal que |B′|= q e

⋃B∈B′ B =V ?

O Problema X3X é um problema de decisão, bem conhecido da literaturacientífica, que é NP-Completo, em conformidade com [16].

A solução do Problema PSTS-1-RES pode ser formalizada por meio do Teo-rema a seguir, que será detalhado abaixo, baseado no trabalho de LI e TOULOUSE [20].

Teorema 6.5 (PSTS-1RES) PSTS-1-RES é NP-Completo.

Prova. A prova que o problema PSTS-1-RES é NP-Completo é construída usandouma transformação em tempo polinomial do Problema (X3X) - Cobertura Exata por3 conjuntos. Esta demonstração é feita em detalhes no artigo de LI e TOULOUSE [20]. �

85

No contexto dos problemas NP-Difíceis, também temos um interessante resul-tado, expresso pelo Teorema a seguir:

Teorema 6.6 Determinar o índice cromático de um Sistema Triplo de Steiner parcial é

um problema NP-Difícil.

Prova. A prova pode ser encontrada em LI e TOULOUSE [20]. �

Afirmar NP-Completude não é uma tarefa fácil e envolve resultados bemcomplexos. Mas, mesmo no contexto dos Planejamentos Combinatórios, muito ainda háa ser feito, tanto na busca de soluções para problemas em aberto, bem como na procurade otimizar alguns algoritmos de aproximação já existentes.

CAPÍTULO 7Conclusões

Neste trabalho fizemos uma introdução à Teoria de Planejamentos Combinató-rios, com ênfase nas construções dos Sistemas Triplos de Steiner. Esta área de pesquisaé bastante ampla e não procuramos discutir de modo conclusivo toda a sua amplitude,mas somente apresentar e argumentar os aspectos fundamentais desta vasta teoria.

Ao discutir as técnicas de construção dos principais planejamentos em blocos,enfatizando os Sistemas Triplos de Steiner, procuramos manter um equilíbrio entre onível matemático formal e exemplos práticos que enriquecem a compreensão da aplicaçãoteórica dos planejamentos em blocos. Rediscutimos construções tradicionais com ummaior nível de detalhamento e exemplos, a fim de apresentar os conceitos de modogradativo e assimilável.

O conceito de resolubilidade surge a partir da definição de classes paralelase serve para decidir quando um Sistema Triplo de Steiner é resolvível e quando nãoé resolvível. Enfatizamos os aspectos de construção recursiva dos complexos SistemasTriplos de Steiner que não são resolvíveis.

No início deste trabalho vimos algumas possibilidades de aplicação da Teoriade Planejamentos Combinatórios em áreas tais como redes de comunicação, criptografiae ciência da computação. Mas, vale a pena frisar que o escopo de aplicação é bemabrangente, e atinge as áreas mais distintas. A seguir veremos algumas destas novasaplicações:

As redes de sensores sem fio vem ganhando destaque na sociedade contempo-rânea e as suas tecnologias estão sendo aprimoradas gradualmente. A questão da distri-buição de chaves em redes sem fio tem importância fundamental pois envolve questõesde segurança. Pesquisas recentes utilizam abordagem de planejamentos combinatórios,por meio das técnicas de planejamentos em blocos, para distribuir as chaves das redes desensores sem fio [4].

Há até mesmo aplicações inusitadas, por exemplo, WALLIS [29] utiliza osSistemas Triplos de Steiner para fundamentar o planejamento de rodadas de times emtorneios de golf.

87

Entre os tópicos que merecem destaque na pesquisa contemporânea podemoscitar as projeções em geometrias finitas, e também a imersão de Sistemas Triplos deSteiner em superfícies [18].

Espera-se que com este trabalho o leitor tenha seu interesse despertado paraa compreensão do significado da Teoria dos Planejamentos Combinatórios e suaimportância fundamental para a Matemática Moderna, Ciência da Computação e várioscampos de aplicação.

Referências Bibliográficas

[1] BILLINGTON, E.; LINDNER, C. Embedding 5-cycle systems into pentagon triple

systems. Discrete Mathematics, 309(14):4828–4834, 2009.

[2] BONDY, J.; MURTY, U. Graph theory, volume 244 of Graduate Texts in Mathema-

tics. Springer, New York, 2008.

[3] BRYANT, D.; HORSLEY, D. A proof of lindner’s conjecture on embeddings of

partial steiner triple systems. Journal of Combinatorial Designs, 17(1):63–89,

2009.

[4] CAMTEPE, S.; YENER, B. Combinatorial design of key distribution mechanisms

for wireless sensor networks. Computer Security–ESORICS 2004, p. 293–308,

2004.

[5] CHING LI, B.; VAN REES, G. Existence of non-resolvable steiner triple systems.

Journal of Combinatorial Designs, 13(1):16–24, 2005.

[6] COLBOURN, C. Embedding partial steiner triple systems is np-complete. Journal

of Combinatorial Theory, Series A, 35(1):100–105, 1983.

[7] COLBOURN, C.; DINITZ, J. Handbook of Combinatorial Designs, (Discrete Mathe-

matics and Its Applications). Chapman & Hall/CRC, 2007.

[8] COLBOURN, C.; DINITZ, J.; STINSON, D.; OF WATERLOO. DEPT. OF COMBINATO-

RICS, U.; OPTIMIZATION.; OF WATERLOO. FACULTY OF MATHEMATICS, U. Applica-

tions of combinatorial designs to communications, cryptography, and networ-

king. Citeseer, 1999.

[9] COLBOURN, C.; VAN OORSCHOT, P. Applications of combinatorial designs in

computer science. ACM Computing Surveys (CSUR), 21(2):223–250, 1989.

[10] CORMEN, T. Introduction to algorithms. The MIT press, 2001.

[11] DIESTEL, R. Graph theory, Graduate Texts in Mathematics Vol. 173. Springer-

Verlag, New York, 2000.


[12] DINITZ, J.; STINSON, D. Contemporary design theory: A collection of Surveys,

volume 26. Wiley-Interscience, 1992.

[13] DOMINGUES, H.; IEZZI, G. Álgebra moderna. Atual Editora, 2003.

[14] DOYEN RICHARD M, J. Embeddings of steiner triple systems. Discrete Mathema-

tics, 5(3):229–239, 1973.

[15] DUKES, P.; LAMKEN, E.; WILSON, R. Combinatorial design theory. 2008.

[16] GAREY, M.; JOHNSON, D. Computers and Intractability: A Guide to the Theory

of NP-completeness. WH Freeman & Co., 1979.

[17] GONÇALVES, A. Introdução à Álgebra. Instituto de Matemática Pura e Aplicada,

2001.

[18] GRANNELL, M.; GRIGGS, T.; SIRAN, J. Surface embeddings of steiner triple

systems. Journal of Combinatorial Designs, 6(5):325–336, 1998.

[19] LAYWINE, C.; MULLEN, G. Discrete mathematics using Latin squares, volume 49.

Wiley-Interscience, 1998.

[20] LI, P.; TOULOUSE, M. Some np-completeness results on partial steiner triple

systems and parallel classes. Ars Combinatoria, 80:45–52, 2006.

[21] LINDNER, C.; QUATTROCCHI, G.; RODGER, C. Embedding steiner triple systems

in hexagon triple systems. Discrete Mathematics, 309(2):487–490, 2009.

[22] LINDNER, C.; RODGER, C. Design theory. Chapman & Hall/CRC, 2009.

[23] MESZKA, M.; ROSA, A.; ZIOLO, I. Steiner almost self-complementary graphs and

halving near-steiner triple systems. Discrete Mathematics, 309(18):5650–5654,

2009.

[24] RAY-CHAUDHURI, D.; WILSON, R. Solution of kirkman’s schoolgirl problem. In:

Proc. Symp. Pure Math, volume 19, p. 187–203, 1971.

[25] ROSEN, K. Discrete mathematics and its applications. McGraw-Hill, 2003.

[26] SCHEINERMAN, E. Matemática Discreta: Uma Introdução. Pioneira Thomson

Learning, 2003.

[27] SILVA, V. V. D. Números: Construção e Propriedades. Editora UFG, 2003.

[28] SIPSER, M.; DE QUEIROZ, R. Introdução à teoria da computação. Thomson

Learning, 2007.


[29] WALLIS, W. Introduction to Combinatorial Designs, (Discrete Mathematics and

Applications). Chapman & Hall/CRC, 2007.

[30] WEST, D.; OTHERS. Introduction to graph theory, volume 1. Prentice Hall Upper

Saddle River, NJ, 2001.

Documents

Planejamentos Combinatórios - inf.ufg.br fileENIO PEREZ RODRIGUES BARBOSA Planejamentos Combinatórios Construindo Sistemas Triplos de Steiner Dissertação defendida no Programa