fevereiro | 2021
Petra Sofia Nunes Silva
MESTRADO EM MATEMÁTICA, ESTATÍSTICA E APLICAÇÕES
Triângulo DNG
DISSERTAÇÃO DE MESTRADO
 
Petra Sofia Nunes Silva
MESTRADO EM MATEMÁTICA, ESTATÍSTICA E APLICAÇÕES
Triângulo DNG
DISSERTAÇÃO DE MESTRADO
ORIENTAÇÃO
Maria Teresa Alves Homem de Gouveia
 
Agradecimentos
Em primeiro lugar quero agradecer a todos os Professores, mas de um modo
muito especial à minha orientadora, a Professora Drª Teresa Gouveia, por ter sido
incansável com todo o seu apoio e disponibilidade indispensáveis na realização desta
dissertação.
Aos meus colegas de Mestrado, em especial à Laura Berenguer, pela amizade
desde o primeiro ano da Licenciatura.
À minha tia e madrinha, Ana Nunes, por ser um exemplo e uma segunda mãe
para mim, sempre presente e sempre com o conselho mais acertado.
Aos meus avós maternos, América e Eleutério Nunes, pela incrível educação e
valores que sempre transmitiram, pelo carinho, por sempre demonstrarem o orgulho
que têm em mim e por todo o apoio que me deram nas minhas escolhas académicas.
À Ana Luísa, pela paciência que sempre teve comigo, pelo apoio que sempre me
deu, por me dizer sempre tudo o que preciso de ouvir, por ser a minha bengala e
pela amizade incondicional que me dá todos os dias.
Aos meus amigos de sempre, principalmente à Ssica por ter sempre os melhores
conselhos e os melhores ensinamentos, por me fazer dar gargalhadas como ninguém
e por ser também a minha bengala.
À Carlota, ao Adão, ao Nikolaj e restante grupo por todas as semanas, por umas
horas, me fazerem esquecer o trabalho e simplesmente rir e me divertir com todos
vocês, e por todos os abraços de apoio que me deram no momento certo.
Ao meu Júlio, por ser o meu companheiro em tudo, por ser sempre a minha força,
por me fazer ver o lado positivo da vida, por me fazer aproveitar cada segundo, por
ser o meu porto seguro e por me ensinar a estar grata por tudo.
E por fim, o meu maior agradecimento vai para a minha melhor amiga, a mulher
que me deu tudo, a minha mãe, Dulce Nunes. A minha mãe sempre me disse que
eu podia ser quem quisesse ou fazer o que quisesse desde que nunca procrastinasse
e desse sempre o melhor de mim. Encheu a nossa casa com amor, alegria, livros e
músicas e nunca poupou nos abraços, nas loucuras e nas gargalhadas. Ensinou-me
tudo sobre a liberdade e a independência, enquanto me mostrava que não há melhor
lugar no mundo que o abraço de uma mãe. Devo-lhe tudo o que tenho, e espero um
dia ser como ela. Obrigada, Mãe, és o meu modelo em tudo.
i
ii
Resumo
Com o estudo da teoria dos grafos e da teoria dos designs surgiu o principal ob-
jetivo desta dissertação, nomeadamente, a construção do triângulo DNG, ou seja, a
construção de ligações entre a teoria dos designs combinatórios, a teoria dos números
e a teoria dos grafos.
Nesta dissertação, em primeiro lugar, fez-se uma introdução teórica com alguns
exemplos, de cada uma das teorias pertencentes ao triângulo DNG e, de seguida,
demonstrou-se como estas poderiam estar ligadas, aplicando-as em diversos proble-
mas.
Dentro do grupo dos designs, foi dada a devida relevância aos BIBDs (Balanced
Incomplete Block Designs), em que conseguimos calcular a matriz de Hadamard
para alguns BIBDs não simétricos.
Em relação à teoria dos números, mantivemos o nosso foco nos números euleri-
anos, por percebermos que existia uma relação entre estes e os BIBDs.
Na teoria dos grafos, para além dos grafos completos, importantíssimos na relação
da teoria dos grafos com a teoria dos designs, demos importância ao polinómio de
Tutte e a sua relação com os grafos bipartidos.
As aplicações do triângulo DNG em situações recorrentes da nossa vida servem
para provar que a matemática está interligada e sempre presente, mesmo que por
vezes a sua importância não seja visível para todos.
Palavras-chave: Grafo, Design, Número Euleriano, Polinómio de Tutte,
Matriz de Hadamard.
iii
iv
Abstract
With the study of the graph theory and the design theory, the main objective
of this dissertation emerged, namely, on the construction of the DNG triangle, that
is, the construction of connections between the theory of combinatorial designs, the
theory of numbers and the theory of graphs.
In this dissertation, in first place, a theoretical introduction was made with some
examples, of each of the theories belonging to the DNG triangle, and then, it was
demonstrated how they could be linked, applying them in several problems.
Within the design group, due importance was given to BIBDs (Balanced Incom-
plete Block Designs), in which we were able to calculate the Hadamard matrix for
some non-symmetric BIBDs.
Regarding number theory, we kept our focus on Eulerian numbers, as we realized
that there was a relationship between them and the BIBDs.
In graph theory, in addition to the complete graphs, that are very important in
the relation between graph theory and design theory, we gave importance to Tutte’s
polynomial and its relation to bipartite graphs.
The applications of the DNG triangle in recurring situations of our lives proves
that mathematics is interconnected and always present, even though its importance
is not visible to everyone.
Keywords: Graph, Design, Eulerian Number, Tutte Polynomial, Hada-
mard Matrix.
v
vi
Índice
Lista de Figuras xi
Lista de Tabelas xiii
Lista de Notações xvii
1 Introdução 1
2 Designs 3
2.1 Alguns conceitos básicos . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Matriz de Incidência e Matriz Complementar . . . . . . . . . . . . . . 6
2.3 Matriz de Hadamard . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3.1 Matriz de Hadamard para BIBDs não simétricos . . . . . . . . 10
3 Números 19
3.1 Números pares e ímpares . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Números primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3 Combinações de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4 Congruência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.5 Relação de recorrência . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.6 Números eulerianos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Grafos 27
4.1 Alguns conceitos básicos . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2 Grafos especiais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2.1 Grafo Euleriano . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2.2 Grafo Hamiltoniano . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2.3 Grafo Planar . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.3 Matriz de Incidência . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.4 Matriz de Adjacência . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.5 Matching Perfeito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.6 Árvore Geradora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.6.1 Teorema da árvore-matriz . . . . . . . . . . . . . . . . . . . . 40
4.7 Número Cromático . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.7.1 Polinómio Cromático . . . . . . . . . . . . . . . . . . . . . . . 42
4.7.2 Coloração de alguns grafos especiais . . . . . . . . . . . . . . . 44
4.8 Digrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
vii
viii ÍNDICE
4.9 Polinómio de Tutte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.9.1 Polinómio de Tutte em grafos bipartidos . . . . . . . . . . . . 48
5 Triângulo DNG 57
5.1 Grafos completos e BIBDs . . . . . . . . . . . . . . . . . . . . . . . . 57
5.1.1 Grafo Conexo, Euleriano, Hamiltoniano e Planar . . . . . . . 60
5.1.2 Matrizes de incidência e de adjacência . . . . . . . . . . . . . 62
5.1.3 Bloco Complementar . . . . . . . . . . . . . . . . . . . . . . . 63
5.1.4 Matching Perfeito . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.1.5 Árvore Geradora . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.1.6 Digrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2 Grafos especiais e BIBDs . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.3 Multigrafos e BIBDs . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.4 Grafos completos e BIBDs simétricos . . . . . . . . . . . . . . . . . . 67
5.5 Números Eulerianos e BIBDs . . . . . . . . . . . . . . . . . . . . . . 68
5.6 Polinómio de Tutte e BIBDs . . . . . . . . . . . . . . . . . . . . . . . 71
6 Aplicações 77
6.1 Problema do Carteiro Chinês . . . . . . . . . . . . . . . . . . . . . . 77
6.2 Ciências da Computação . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.3 Relações entre as Pessoas . . . . . . . . . . . . . . . . . . . . . . . . . 82
7 Conclusão 85
A Álgebra linear 89
A.1 Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
A.1.1 Matriz quadrada . . . . . . . . . . . . . . . . . . . . . . . . . 89
A.1.2 Matriz diagonal . . . . . . . . . . . . . . . . . . . . . . . . . . 89
A.1.3 Matriz identidade . . . . . . . . . . . . . . . . . . . . . . . . . 90
A.1.4 Matriz transposta . . . . . . . . . . . . . . . . . . . . . . . . . 90
A.1.5 Soma de matrizes . . . . . . . . . . . . . . . . . . . . . . . . . 90
A.1.6 Multiplicação de matrizes . . . . . . . . . . . . . . . . . . . . 91
A.2 Determinantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
A.2.1 Matriz de dimensão 2× 2 . . . . . . . . . . . . . . . . . . . . 92
A.2.2 Matriz de dimensão 3× 3 . . . . . . . . . . . . . . . . . . . . 93
Anexos 93
A Matriz de Hadamard do (11,22,10,5,4)-BIBD 95
B Problema do Caixeiro-viajante 99
C Coloração de Mapas 103
D Aplicação nas Ciências 105
D.1 Os Grafos na Biologia . . . . . . . . . . . . . . . . . . . . . . . . . . 105
D.2 Os Grafos na Química . . . . . . . . . . . . . . . . . . . . . . . . . . 106
ÍNDICE ix
E Aplicação na resolução de crimes 107
x ÍNDICE
Lista de Figuras
2.1 Matriz de incidência do (5, 10, 4, 2, 1)−BIBD . . . . . . . . . . . . . . 6
2.2 Grafo criado a partir do (5, 10, 4, 2, 1)−BIBD . . . . . . . . . . . . . . 7
2.3 Matriz complementar do (5, 10, 4, 2, 1)−BIBD . . . . . . . . . . . . . 7
2.4 Matriz de incidência do (7, 7, 3, 3, 1)−BIBD . . . . . . . . . . . . . . . 9
2.5 Matriz de incidência do (5, 10, 4, 2, 1)−BIBD . . . . . . . . . . . . . . 13
2.6 Matriz de incidência do (7, 14, 6, 3, 2)−BIBD . . . . . . . . . . . . . . 15
2.7 Matriz de incidência do (9, 18, 8, 4, 3)−BIBD . . . . . . . . . . . . . . 17
4.1 As sete pontes de Ko¨nigsberg . . . . . . . . . . . . . . . . . . . . . . 27
4.2 Grafo criado por Euler para as sete pontes de Ko¨nigsberg . . . . . . 27
4.3 Da esquerda para a direita, grafo simples, multigrafo e pseudografo . 28
4.4 Um caminho simples do grafo G . . . . . . . . . . . . . . . . . . . . . 29
4.5 Um caminho fechado do grafo G . . . . . . . . . . . . . . . . . . . . . 29
4.6 Um passeio do grafo G . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.7 Um percurso do grafo G . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.8 Um circuito do grafo G . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.9 Um ciclo do grafo G . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.10 Grafo G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.11 Grafos completos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.12 Grafos cíclicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.13 Grafos roda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.14 Grafos nulos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.15 Grafos caminho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.16 Grafo bipartido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.17 Grafo bipartido com vértices de cores diferentes . . . . . . . . . . . . 33
4.18 Grafo bipartido completo . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.19 Grafo conexo e grafo desconexo . . . . . . . . . . . . . . . . . . . . . 34
4.20 Um grafo de Euler e de Hamilton . . . . . . . . . . . . . . . . . . . . 35
4.21 Representação do grafo K4 na forma planar . . . . . . . . . . . . . . 35
4.22 Grafo G conexo e planar . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.23 Grafo G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.24 Matriz de incidência do grafo G . . . . . . . . . . . . . . . . . . . . . 37
4.25 Grafo G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.26 Matriz de adjacência do grafo G . . . . . . . . . . . . . . . . . . . . . 38
4.27 Grafo G com matching perfeito . . . . . . . . . . . . . . . . . . . . . 39
4.28 Grafo completo K6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.29 Exemplos de árvores geradoras do grafo completo K6 . . . . . . . . . 40
xi
xii LISTA DE FIGURAS
4.30 Grafo G com quatro vértices . . . . . . . . . . . . . . . . . . . . . . . 40
4.31 Matriz de adjacência do grafo G . . . . . . . . . . . . . . . . . . . . . 40
4.32 Matriz S do grafo G . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.33 Grafo 4−colorável . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.34 Eliminação e contração da aresta 23 do grafo G . . . . . . . . . . . . 42
4.35 Grafo G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.36 Cálculo do polinómio cromático do grafo G . . . . . . . . . . . . . . . 43
4.37 Polinómio cromático do grafo G . . . . . . . . . . . . . . . . . . . . . 44
4.38 Grafo k−crítico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.39 Digrafo D com seis vértices . . . . . . . . . . . . . . . . . . . . . . . . 46
4.40 Matriz de incidência do digrafo D com seis vértices . . . . . . . . . . 46
4.41 Polinómio de Tutte do grafo completo K3 . . . . . . . . . . . . . . . . 47
4.42 Triângulo de Tutte de grafos bipartidos . . . . . . . . . . . . . . . . . 55
5.1 Grafo completo K3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.2 Grafo completo K4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.3 Grafo completo K5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.4 Grafo completo K6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.5 Grafo K3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.6 Grafo K4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.7 Matriz de incidência dos grafos Kn . . . . . . . . . . . . . . . . . . . 62
5.8 Matriz de adjacência dos grafos Kn . . . . . . . . . . . . . . . . . . . 62
5.9 Matching perfeito do grafo K4 . . . . . . . . . . . . . . . . . . . . . . 63
5.10 Matching perfeito do grafo K5 . . . . . . . . . . . . . . . . . . . . . . 63
5.11 Grafo completo K4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.12 Matriz de adjacência do grafo completo K4 . . . . . . . . . . . . . . . 64
5.13 Matriz S do grafo completo K4 . . . . . . . . . . . . . . . . . . . . . 64
5.14 Digrafo de um (4, 6, 3, 2, 1)−BIBD . . . . . . . . . . . . . . . . . . . 65
5.15 Multigrafo do (4, 12, 6, 2, 2)−BIBD . . . . . . . . . . . . . . . . . . . 67
5.16 Multigrafo do (4, 18, 9, 2, 3)−BIBD . . . . . . . . . . . . . . . . . . . 67
5.17 Grafo do BIBD simétrico (3, 3, 2, 2, 1) . . . . . . . . . . . . . . . . . . 68
6.1 Digrafo sem ciclo de Hamilton . . . . . . . . . . . . . . . . . . . . . . 78
6.2 Digrafo Euleriano e Hamiltoniano . . . . . . . . . . . . . . . . . . . . 78
6.3 Digrafo associado ao (6, 15, 5, 2, 1)−BIBD . . . . . . . . . . . . . . . . 79
6.4 Digrafo adaptado a Euleriano . . . . . . . . . . . . . . . . . . . . . . 80
6.5 Grafo que relaciona os diferentes sites . . . . . . . . . . . . . . . . . 81
6.6 Parte da árvore genealógica da família Bernoulli, fonte: Picado [PG08] 82
6.7 Grafo das relações de parentesco da família Bernoulli . . . . . . . . . 82
A.1 Matriz de incidência do design (11,22,10,5,4) . . . . . . . . . . . . . . 96
B.1 Grafo que demonstra os diferentes trajetos que o caixeiro-viajante
poderia escolher no concelho do Funchal . . . . . . . . . . . . . . . . 100
B.2 Ciclo de Hamilton com menor custo dos diferentes trajetos que o
caixeiro-viajante poderia escolher no concelho do Funchal . . . . . . . 101
C.1 Mapa da Ilha da Madeira representado na forma de grafo . . . . . . . 103
LISTA DE FIGURAS xiii
C.2 Coloração do grafo que representa o mapa da Ilha da Madeira . . . . 103
D.1 Exemplo de uma cadeia alimentar . . . . . . . . . . . . . . . . . . . . 105
D.2 Exemplo de uma rede alimentar . . . . . . . . . . . . . . . . . . . . . 105
D.3 Grafo representativo da molécula da água . . . . . . . . . . . . . . . 106
D.4 Grafo representativo da molécula da cafeína . . . . . . . . . . . . . . 106
E.1 Digrafo que representa os testemunhos dos suspeitos . . . . . . . . . . 107
xiv LISTA DE FIGURAS
Lista de Tabelas
2.1 Exemplo de uma solução do problema de Kirkman . . . . . . . . . . . 3
2.2 Valores de k e λ quando v é um número primo . . . . . . . . . . . . . 9
4.1 Grau de entrada e de saída de cada um dos vértices . . . . . . . . . . 46
5.1 BIBDs correspondentes aos grafos completos . . . . . . . . . . . . . . 59
5.2 Graus de entrada e de saída de cada um dos vértices . . . . . . . . . 65
5.3 Graus de entrada e de saída de cada um dos vértices de um digrafo
completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.4 BIBD resultante de E(n, 1) . . . . . . . . . . . . . . . . . . . . . . . 69
5.5 BIBD resultante de E(n, 2) . . . . . . . . . . . . . . . . . . . . . . . 69
5.6 BIBD resultante de E(n, 3) . . . . . . . . . . . . . . . . . . . . . . . 70
5.7 Ligação entre o polinómio de Tutte de grafos bipartidos completos e
os BIBDs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.1 Graus de entrada e de saída de cada um dos vértices do digrafo sem
ciclo de Hamilton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.2 Graus de entrada e de saída de cada um dos vértices do digrafo Eu-
leriano e Hamiltoniano . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.3 Graus de entrada e de saída de cada vértice do digrafo associado ao
(6, 15, 5, 2, 1)−BIBD . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6.4 Graus de entrada e de saída do digrafo adaptado a Euleriano . . . . . 80
B.1 Ciclos de Hamilton no concelho do Funchal . . . . . . . . . . . . . . . 100
E.1 Graus de entrada de cada um dos vértices . . . . . . . . . . . . . . . 107
xv
xvi LISTA DE TABELAS
Lista de Notações
BIBD Balanced Incomplete Block Design
X conjunto finito com v elementos
A coleção de b subconjuntos de X
v ou |X| número de elementos de X
b ou |A| número de subconjuntos de A
r número de vezes que um elemento se repete nos subconjuntos
de A
k número de elementos de cada subconjunto (ou bloco) de A
λ número de vezes que cada par ocorre nos blocos de A
N conjunto dos números naturais(
n
k
)
= C(n, k) número de k−combinações de um conjunto com n elementos
Mv×b matriz de incidência de um BIBD
mij entradas da matriz Mv×b
A¯ coleção dos blocos complementares de um BIBD
H matriz de Hadamard
HT matriz transposta de H
Hn matriz de Hadamard de ordem n
In matriz identidade de ordem n
MIv×2v matriz de incidência para um BIBD não simétrico
Z conjunto dos números inteiros
E(n, k) = En,k =
〈
n
k
〉
números eulerianos
P permutação de {1, 2, 3, ..., n}
V (G) conjunto de vértices do grafo G
xvii
xviii LISTA DE NOTAÇÕES
E(G) conjunto de arestas do grafo G
G = (V,E) grafo G que contém o conjunto de vértices V e o conjunto
de arestas E
|V | número de vértices de um grafo
|E| número de arestas de um grafo
deg(vi) grau de um vértice i
Kn grafo completo
Cn grafo cíclico
Wn grafo roda
Nn grafo nulo
Pn grafo caminho
Kn,m grafo bipartido completo
fi face de um grafo planar
|fi| número de faces de um grafo
deg(fi) grau da face i
IG matriz de incidência do grafo G
AG matriz de adjacência do grafo G
M matching
T árvore
T (G) número de árvores geradoras do grafo G
r(Kn) número de árvores de Kn
S matriz diagonal que contém o número de graus de cada vér-
tice
Q matriz resultante da diferença entre as matrizes S e AG
PG(K) polinómio cromático
χ(G) número cromático do grafo G
G− e eliminação da aresta e do grafo G
G/e contração da aresta e do grafo G
D digrafo ou grafo orientado
LISTA DE NOTAÇÕES xix
degE(vi) grau de entrada do vértice i num digrafo
degS(vi) grau de saída do vértice i num digrafo
t cauda de um arco
h cabeça de um arco
ID matriz de incidência de um digrafo D
TG(x, y) = T (G;x, y) polinómio de Tutte do grafo G
Tn,k elementos do triângulo de Tutte
det A determinante da matriz A
xx LISTA DE NOTAÇÕES
Capítulo 1
Introdução
Esta dissertação, intitulada Triângulo DNG, surgiu no âmbito do Mestrado em
Matemática, Estatística e Aplicações da Universidade da Madeira.
O principal objetivo desta dissertação é a construção de ligações entre a teoria
dos designs combinatórios, a teoria dos números e a teoria dos grafos. Este ciclo,
criado através dessas ligações, denomina-se triângulo DNG, em que DNG representa
a letra inicial de cada uma das componentes dos vértices do triângulo.
A teoria dos grafos despertou-nos interesse devido ao seu crescimento exponencial
no século XX e às imensas e diferentes aplicações que esta tem no nosso mundo.
Cada vez mais, com o avanço das tecnologias e das redes de transportes, percebe-se
a importância da teoria dos grafos ao constatarmos que esta está presente em tudo
o que nos rodeia.
A teoria dos designs, sendo um tema que na matemática só começou a ser verda-
deiramente estudado no século XX, ainda tem muitos problemas em aberto. Ante-
riormente, segundo Stinson [Sti07], nos séculos XVIII e XIX, a teoria do design era
utilizada na matemática recreativa, nomeadamente, na resolução de quebra-cabeças.
Os estudos mais recentes, especialmente sobre os BIBDs (Balanced Incomplete Block
Designs), incentivaram o nosso interesse em relacioná-los com os grafos, pois achá-
mos interessante estudar como é que um grafo ficaria organizado num conjunto finito,
em que os seus elementos estariam em subconjuntos, satisfazendo as propriedades
de um BIBD.
A teoria dos números, ao contrário das anteriores, segundo Brualdi [Bur11], teve
a sua origem na Grécia Antiga, em que a palavra número significava somente número
inteiro positivo.
Esta dissertação está organizada da forma que se segue.
No Capítulo 2, aborda-se a teoria dos designs, narrando um pouco da sua história
e apresentando alguns conceitos básicos. Para além destes conceitos, também se
explica o que é a matriz de Hadamard e consegue-se provar que existe aplicabilidade
desta matriz, não só para os BIBDs simétricos, mas também para alguns BIBDs não
simétricos.
No Capítulo 3, apresenta-se uma breve introdução à teoria dos números com
maior ênfase nos números eulerianos, já que estes são um ponto fulcral do triângulo
DNG.
No Capítulo 4, são introduzidos todos os conceitos necessários da teoria dos
1
2 Introdução
grafos para esta dissertação. Além de conceitos gerais sobre a teoria dos grafos, o
tema mais destacado é o do polinómio de Tutte.
No Capítulo 5, explica-se o que efetivamente é o triângulo DNG, que relaciona
os grafos completos, os números eulerianos e o polinómio de Tutte com os BIBDs.
No Capítulo 6, demonstra-se a aplicabilidade do triângulo DNG em situações do
nosso quotidiano.
No Capítulo 7, finalmente, encontram-se algumas conclusões e perspetivas de
futuras investigações.
Capítulo 2
Designs
A teoria do design combinatório tem origem na teoria da estatística experimen-
tal, na matemática recreativa e na geometria. Esta teoria relaciona determinados
padrões com a construção de conjuntos finitos e tem o seu foco na organização
de elementos de um conjunto finito em subconjuntos, de modo que determinadas
propriedades sejam satisfeitas. Os principais problemas são, em geral, os de exis-
tência, numeração e classificação, propriedades estruturais e aplicações. São várias
as aplicações da teoria do design, nomeadamente na programação e na criptografia.
Exemplo 2.0.1. Problema de Kirkman
Originalmente, a teoria do design foi criada para fins recreativos para solucio-
nar o problema de Kirkman, 1850. O problema de Kirkman consistiu em organizar
quinze alunos em cinco grupos de três para que, numa visita de estudo de sete dias,
cada par de alunos passeasse uma única vez. A Tabela 2.1 representa uma possível
solução para este problema.
Tabela 2.1: Exemplo de uma solução do problema de Kirkman
Domingo Segunda Terça Quarta Quinta Sexta Sábado
1 2 3 1 4 5 1 6 7 1 8 9 1 10 11 1 12 13 1 14 15
4 8 12 2 8 10 2 9 11 2 12 15 2 13 14 2 4 6 2 5 7
5 10 14 3 13 15 3 12 14 3 5 6 3 4 7 3 9 10 3 8 11
6 11 13 6 9 14 4 10 15 4 11 14 5 9 12 5 11 15 4 9 13
7 9 15 7 11 12 5 8 13 7 10 13 6 8 15 7 8 14 6 10 12
Uma das principais noções da teoria do design, a noção de equilíbrio entre pares,
tem a sua origem na teoria da estatística experimental. A exigência de um certo tipo
de padrão leva-nos à noção de um dos tipos mais comuns de designs combinatórios,
o Balanced Incomplete Block Design, usualmente designado por BIBD, introduzido
em 1936 por Yates, sendo que mais tarde, no final da década de 30, Bose e Fisher
contribuíram para o estudo de BIBDs, estudando a sua estrutura e a sua constru-
ção. Desde então, ainda não foi construído um algoritmo geral para determinar a
existência destes designs, embora já tenham sido introduzidos vários métodos de
3
4 Designs
construção de BIBDs para parâmetros específicos. No entanto, existem muitas per-
guntas em aberto e que permanecem sem solução desde 1936.
Exemplo 2.0.2. Problema de Yates
Em 1936, Yates quis criar um conjunto de blocos, com as seguintes condições:
1. k, o número de unidades experimentais por bloco, é fixo;
2. k < v, ou seja, o número de unidades experimentais por bloco é menor que o
número de tratamentos;
3. dois tratamentos ocorrem juntos em cada bloco com a mesma frequência, ou
seja, se os tratamentos f e g ocorrem juntos em dois blocos, então os trata-
mentos h e i também ocorrem juntos em dois blocos.
Desta forma, Yates considerou que existiam seis tratamentos e cada bloco era
constituído por três desses tratamentos.
X = {f, g, h, i, j, l}
A =
{ {f, g, h} , {f, g, i} , {f, h, j} , {f, i, l} , {f, j, l} , {g, h, l} , {g, i, j} ,
{g, j, l} , {h, i, j} , {h, i, l}
}
2.1 Alguns conceitos básicos
Definição 2.1.1. Um design (ou design combinatório ou bloco design) é um par
(X,A), tal que X é um conjunto finito e A é uma coleção não vazia de subconjuntos
de X.
Usualmente, aos elementos de X chamamos pontos e aos subconjuntos de A,
blocos.
Uma das classes mais importantes de designs são os BIBDs (ver Definição 2.1.2).
Definição 2.1.2. Um Balanced Incomplete Block Design (BIBD) com parâmetros
naturais (v, b, r, k, λ), onde 2 ≤ k < v, é um par (X,A) em que X é um conjunto
finito de v elementos chamados pontos, A é a coleção de b subconjuntos estritos de
X, com cardinal k, cada um chamado de bloco. Cada ponto ocorre em exatamente
r blocos e cada par de pontos distintos ocorre em exatamente λ blocos.
Assim, conhecendo estes conceitos, é fácil identificar os parâmetros de um
(v, b, r, k, λ)−BIBD, no problema de Kirkman:
|X| = v = 15, pois são quinze alunos;
2.1 Alguns conceitos básicos 5
|A| = b = 35, pois são cinco grupos de alunos por cada um dos sete dias, ou
seja, trinta e cinco subconjuntos;
r = 7, pois cada elemento repete-se sete vezes nos subconjuntos;
k = 3, pois cada subconjunto é constituído por três elementos;
λ = 1, pois cada par de elementos surge apenas uma única vez.
Por sua vez, para o problema de Yates os parâmetros (v, b, r, k, λ) do BIBD são
(6, 10, 5, 3, 2)−BIBD, pois existem dez blocos em que cada par de tratamentos ocorre
duas vezes e cada tratamento ocorre cinco vezes.
Definição 2.1.3. Diz-se que um BIBD é simétrico quando v = b (ou equivalente-
mente r = k).
Definição 2.1.4. Um BIBD é considerado simples se não tiver blocos repetidos, e
completo se for simples e tiver
(
v
k
)
1 blocos.
Teorema 2.1.1. Se um BIBD existe, então os seus parâmetros satisfazem as se-
guintes equações:
vr = bk (2.1)
λ(v − 1) = r(k − 1) (2.2)
Observação 2.1.1. Atendendo ao Teorema 2.1.1, podemos concluir que os cinco
parâmetros de um BIBD não são independentes, pois b e r podem-se obter de forma
única a partir dos parâmetros v, k e λ. Por este motivo, escrevemos muitas vezes
(v, k, λ)−BIBD para denotar (v, b, r, k, λ)−BIBD.
Exemplo 2.1.1. Considerando o BIBD (7,3,1), determinemos os valores dos parâ-
metros b e r:
λ (v − 1) = r (k − 1)⇔ 1 (7− 1) = r (3− 1)⇔ 6 = 2r ⇔ r = 3
vr = bk ⇔ 7r = 3b⇔ 7×3
3
= b⇔ b = 7
Teorema 2.1.2 (Inequação de Fisher). Se um (v, k, λ)−BIBD existe com
2 ≤ k < v , (2.3)
então
v ≤ b (2.4)
1Número de k−combinações de um conjunto, constituído por v elementos.
6 Designs
Corolário 2.1.2.1. Se um BIBD existe então λ(v − 1) ≡ 0(mod(k − 1))2 e
λv(v − 1) ≡ 0(mod(k(k − 1))), ou seja, quando λ(v−1)
k−1 ∈ N e λv(v−1)k(k−1) ∈ N.
Observação 2.1.2. Note-se que, (21, 6, 1)−BIBD não existe porque
b = 14 < 21 = v. No entanto, satisfaz as condições do Corolário 2.1.2.1.
Exemplo 2.1.2. Vamos calcular o valor mínimo de λ, considerando o (9,3,λ)−BIBD.
λ(v−1)
k−1 ∈ N→ 82λ ∈ N→ 41λ ∈ N→ λ = 1
λv(v−1)
k(k−1) ∈ N→ 726 λ ∈ N→ 121 λ ∈ N→ λ = 1
λ (v − 1) = r (k − 1)⇔ 1 (9− 1) = r (3− 1)⇔ 8 = 2r ⇔ r = 4
vr = bk ⇔ 9r = 3b⇔ 9×4
3
= b⇔ b = 12
Assim, o (9, 3, λ)−BIBD, para o menor valor de λ, será o (9,12,4,3,1)−BIBD.
2.2 Matriz de Incidência e Matriz Complementar
Definição 2.2.1. Amatriz de incidência de um BIBD (X,A) é designada porMv×b e
as suas entradas mij são determinadas por: mij=
{
0, xi /∈ Aj
1, xi ∈ Aj
, em que 1 ≤ i ≤ v,
1 ≤ j ≤ b, xi ∈ X, e Aj ∈ A.
Na matriz de incidência o número 1 ocorre r vezes em cada linha e k vezes em
cada coluna. Além disso, em duas linhas distintas ambas têm 1 em λ colunas.
Exemplo 2.2.1. Considerando um (5, 10, 4, 2, 1)−BIBD com
X={1, 2, 3, 4, 5} e
A={12, 13, 14, 15, 23, 24, 25, 34, 35, 45}.3
A sua matriz de incidência será:
Figura 2.1: Matriz de incidência do (5, 10, 4, 2, 1)−BIBD
2a ≡ b(mod k) significa que a diferença entre a e b é divisível por k (ver Capítulo 3).
3Para simplificar a notação, usualmente, escrevemos os blocos de A (isto é, os subconjuntos de
X) são as chavetas e sem vírgulas.
2.2 Matriz de Incidência e Matriz Complementar 7
em que cada linha corresponde aos elementos do conjunto X e cada coluna cor-
responde aos blocos (elementos de A).
Analisando a matriz de incidência, é possível ver que o número 1 aparece quatro
vezes em cada linha (r = 4) e duas vezes em cada coluna (k = 2). Em duas linhas
distintas, ambas têm o número 1 somente numa coluna (λ = 1). Através da matriz
de incidência é possível construir o seguinte grafo4 (Figura 2.2):
Figura 2.2: Grafo criado a partir do (5, 10, 4, 2, 1)−BIBD
Definição 2.2.2. Seja (X,A) um design. Ao design (X, A¯) chamamos design com-
plementar, onde A¯ =
{
A¯j ( X : A¯j = X \ Aj e Aj ∈ A
}
.
Teorema 2.2.1. Quando k ≤ v−2 num (v,b,r,k,λ) – BIBD, o design complementar
associado é da forma (v, b, b− r, v − k, b− 2r + λ) – BIBD.
Definição 2.2.3. À matriz de incidência de um BIBD complementar chamamos
matriz de incidência complementar (ou simplesmente matriz complementar).
Exemplo 2.2.2. Considerando um (5, 10, 4, 2, 1)−BIBD com
X = {1, 2, 3, 4, 5} e
A = {12, 13, 14, 15, 23, 24, 25, 34, 35, 45},
vem que, A¯ = {345, 245, 235, 234, 145, 135, 134, 125, 124, 123}. Então, o BIBD
complementar será: (5, 10, 6, 3, 3).
A sua matriz complementar é:
Figura 2.3: Matriz complementar do (5, 10, 4, 2, 1)−BIBD
4A definição de grafo será abordada no Capítulo 4.
8 Designs
2.3 Matriz de Hadamard
Em 1893, o matemático francês Jacques Hadamard apresentou uma matriz com
caraterísticas especiais, mais tarde conhecida, como matriz de Hadamard.
Esta matriz tem várias aplicações, em particular nos BIBDs.
Definição 2.3.1. A matriz de Hadamard, H, é uma matriz quadrada de ordem n
cujas entradas são ±1, tal que HHT = nIn.
Teorema 2.3.1. Quando m > 1 existe uma matriz de Hadamard, de ordem 4m, se
e só se, existir um (4m− 1,2m− 1,m− 1)−BIBD (que é simétrico).
Corolário 2.3.1.1. Existe uma matriz de Hadamard de ordem 4m (com m > 1) se
4m− 1 for um número primo.
Sabendo que
v = 4m− 1⇔ 4m = v + 1⇔ m = v + 1
4
é possível calcular k e λ em função a v:
k = 2m− 1⇔ k = v + 1
2
− 1⇔ k = v − 1
2
λ = m− 1⇔ λ = v + 1
4
− 1⇔ λ = v − 3
4
Assim, sabendo que v é um número primo, é fácil identificar para que valores de
v a construção da matriz de Hadamard é possível.
Para os primeiros dezoito números primos, é possível construir uma matriz de
Hadamard quando v = 7, 11, 19, 23, 31, 43, 47, ou 59, como podemos observar
na tabela seguinte:
2.3 Matriz de Hadamard 9
Tabela 2.2: Valores de k e λ quando v é um número primo
v k λ
2 0,5 -0,25
3 1 0
5 2 0,5
7 3 1
11 5 2
13 6 2,5
17 8 3,5
19 9 4
23 11 5
29 14 6,5
31 15 7
37 18 8,5
41 20 9,5
43 21 10
47 23 11
53 26 12,5
59 29 14
61 30 14,5
...
...
...
Observação 2.3.1. Como sabemos a matriz de Hadamard, H, é de ordem n e uma
vez que a matriz de incidência de um BIBD simétrico (v = b) é de ordem v, a matriz
H é de ordem v + 1 (n = v + 1), isto é, HHT = nIn = (v + 1)Iv+1.
Assim, como n = v+1, as primeiras matrizes de Hadamard, associadas a BIBDs
simétricos, são as matrizes H8, H12, H20, H24, H32, H44, H48 e H60.
Exemplo 2.3.1. Considerando um (7, 7, 3, 3, 1)−BIBD, em que
X = {1, 2, 3, 4, 5, 6, 7} e
A = {123, 145, 167, 246, 257, 347, 356}
a sua matriz de incidência é a seguinte:
Figura 2.4: Matriz de incidência do (7, 7, 3, 3, 1)−BIBD
10 Designs
Para tornar a matriz de incidência em matriz de Hadamard, é necessário acres-
centar uma linha e uma coluna com as entradas todas iguais a 1, e substituir o
número 0 por −1. 
1 1 1 1 1 1 1 1
1 1 1 1 −1 −1 −1 −1
1 1 −1 −1 1 1 −1 −1
1 1 −1 −1 −1 −1 1 1
1 −1 1 −1 1 −1 1 −1
1 −1 1 −1 −1 1 −1 1
1 −1 −1 1 1 −1 −1 1
1 −1 −1 1 −1 1 1 −1

Ao multiplicar a matriz de Hadamard pela sua transposta, verifica-se que o
resultado dessa multiplicação é a matriz identidade vezes n (neste caso n = 8).
H8H
T
8 =

1 1 1 1 1 1 1 1
1 1 1 1 −1 −1 −1 −1
1 1 −1 −1 1 1 −1 −1
1 1 −1 −1 −1 −1 1 1
1 −1 1 −1 1 −1 1 −1
1 −1 1 −1 −1 1 −1 1
1 −1 −1 1 1 −1 −1 1
1 −1 −1 1 −1 1 1 −1


1 1 1 1 1 1 1 1
1 1 1 1 −1 −1 −1 −1
1 1 −1 −1 1 1 −1 −1
1 1 −1 −1 −1 −1 1 1
1 −1 1 −1 1 −1 1 −1
1 −1 1 −1 −1 1 −1 1
1 −1 −1 1 −1 1 1 −1
1 −1 −1 1 1 −1 −1 1

=

8 0 0 0 0 0 0 0
0 8 0 0 0 0 0 0
0 0 8 0 0 0 0 0
0 0 0 8 0 0 0 0
0 0 0 0 8 0 0 0
0 0 0 0 0 8 0 0
0 0 0 0 0 0 8 0
0 0 0 0 0 0 0 8

= 8

1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1

= 8I8
2.3.1 Matriz de Hadamard para BIBDs não simétricos
Como existe matriz de Hadamard para BIBDs simétricos, decidimos investigar
se seria possível construir uma matriz de Hadamard para os BIBDs não simétricos.
Após alguns recuos e avanços e partindo de alguns pressupostos, conseguimos cons-
truir uma matriz para um determinado tipo de BIBDs não simétricos.
Em primeiro lugar, considera-se que b = 2v, para garantir que quando se divide
a matriz de incidência de um BIBD não simétrico por dois, esta divisão irá originar
duas matrizes de dimensão n × n, em que já é possível em cada uma delas imple-
mentar as regras da matriz de Hadamard para BIBDs simétricos.
2.3 Matriz de Hadamard 11
Para calcular os restantes parâmetros, considera-se que
vr = bk ⇔ vr = 2vk ⇔ k = 1
2
r
λ(v − 1) = r(k − 1)⇔ λ(v − 1) = r(1
2
r − 1)⇔ λ(v − 1) = 1
2
r2 − r .
Assim, r terá de ser um número par para que k seja um número natural, e
λ =
1
2
r2 − r
v − 1 ∈ N ,
ou seja, para λ ser um número inteiro positivo, considerando que r é um número
par e a expressão 1
2
r2− r origina um número par, conclui-se que v− 1 é um número
par, isto é, v é um número ímpar.
Desta forma, a matriz de Hadamard, criada a partir destes BIBDs não simétricos,
será uma matriz 1,2Hv+1 tal que
1Hv+1(1H
T
v+1) +2 Hv+1(2H
T
v+1) = 2(v + 1)Iv+1
Para chegarmos à expressão da matriz de Hadamard, para BIBDs não simétricos,
utilizamos a seguinte construção tendo por base as propriedades quer dos BIBDs
quer das matrizes. Supondo que v é ímpar e maior que 3 e ainda que r é par e maior
que 2, o BIBD tem a forma
(v, b, r, k, λ)→
(
v, 2v, r,
r
2
,
r2
2
− r
v − 1
)
(2.5)
A sua matriz de incidência é do tipo:
MIv×2v =

i1,1 i1,2 · · · i1,2v
i2,1 i2,2 · · · i2,2v
...
... . . .
...
iv,1 iv,2 · · · iv,2v

v×2v
com iv,1 + iv,2 + ...+ iv,2v = r → cada linha tem r 1’s e 2v − r 0’s
i1,2v + i2,2v + ...+ iv,2v = k =
r
2
→ cada coluna tem r
2
1’s e v − r
2
0’s
De seguida, organiza-se a matriz de incidência MIv×2v em duas matrizes:

i1,1 i1,2 · · · i1,v
i2,1 i2,2 · · · i2,v
...
... . . .
...
iv,1 iv,2 · · · iv,v

v×v
e

i1,v+1 i1,v+2 · · · i1,2v
i2,v+1 i2,v+2 · · · i2,2v
...
... . . .
...
iv,v+1 iv,v+2 · · · iv,2v

v×v
12 Designs
Acrescenta-se uma linha e uma coluna com entradas todas iguais a 1 e substitui-
se todas as entradas de zeros por −1.
1Hv+1 =

1 1 1 · · · 1
1 i1,1 i1,2 · · · i1,v
1 i2,1 i2,2 · · · i2,v
...
...
... . . .
...
1 iv,1 iv,2 · · · iv,v

(v+1)×(v+1)
e 2Hv+1 =

1 1 1 · · · 1
1 i1,v+1 i1,v+2 · · · i1,2v
1 i2,v+1 i2,v+2 · · · i2,2v
...
...
... . . .
...
1 iv,v+1 iv,v+2 · · · iv,2v

(v+1)×(v+1)
Desta forma, a soma de cada coluna é igual a zero com exceção da primeira
coluna.
1 + i1,v + i2,v + ...+ iv,v = 0, tem v− r2 termos iguais a −1 e r2 + 1 termos iguais a 1.
Posteriormente, calcula-se o produto entre cada uma das matrizes anteriores com
a sua matriz transposta, e soma-se as duas matrizes resultantes.
1Hv+1(1H
T
v+1) =

1 1 1 · · · 1
1 i1,1 i1,2 · · · i1,v
1 i2,1 i2,2 · · · i2,v
...
...
... . . .
...
1 iv,1 iv,2 · · · iv,v


1 1 1 · · · 1
1 i1,1 i2,1 · · · iv,1
1 i1,2 i2,2 · · · iv,2
...
...
... . . .
...
1 i1,v i2,v · · · iv,v

=

v + 1 h1,2 · · · h1,v+1
h2,1 v + 1 · · · h2,v+1
...
... . . .
...
hv+1,1 hv+1,2 · · · v + 1

(v+1)×(v+1)
→
diagonal → v + 1
h1,2 + h1,3 + ...+ h1,v+1 = 0
...
hv+1,1 + hv+1,2 + ...+ hv+1,v = 0
2.3 Matriz de Hadamard 13
2Hv+1(2H
T
v+1) =

1 1 1 · · · 1
1 i1,v+1 i1,v+2 · · · i1,2v
1 i2,v+1 i2,v+2 · · · i2,2v
...
...
... . . .
...
1 iv,v+1 iv,v+2 · · · iv,2v


1 1 1 · · · 1
1 i1,v+1 i2,v+1 · · · iv,v+1
1 i1,v+2 i2,v+2 · · · iv,v+2
...
...
... . . .
...
1 i1,2v i2,2v · · · i2v,2v

=

v + 1 j1,2 · · · j1,v+1
j2,1 v + 1 · · · j2,v+1
...
... . . .
...
jv+1,1 jv+1,2 · · · v + 1

(v+1)×(v+1)
→
diagonal → v + 1
j1,2 + j1,3 + ...+ j1,v+1 = 0
...
jv+1,1 + jv+1,2 + ...+ jv+1,v = 0
1Hv+1(1H
T
v+1)+2Hv+1(2H
T
v+1) =

2(v + 1) 0 · · · 0
0 2(v + 1) · · · 0
...
... . . .
...
0 0 · · · 2(v + 1)
 = 2(v+1)Iv+1
Exemplo 2.3.2. Para (5, 10, 4, 2, 1)−BIBD:
X = {1, 2, 3, 4, 5} e
A = {12, 13, 14, 15, 23, 24, 25, 34, 35, 45}.
A sua matriz de incidência é a seguinte:
Figura 2.5: Matriz de incidência do (5, 10, 4, 2, 1)−BIBD
Para construir a matriz de Hadamard, separa-se a matriz de incidência em duas
partes iguais, em que metade dos blocos fica na primeira matriz e a outra metade
na segunda. Em cada uma das matrizes, acrescenta-se uma linha e uma coluna com
as entradas todas iguais a 1, e substitui-se o número 0 por −1.
14 Designs
1H6 =

1 1 1 1 1 1
1 1 1 1 1 −1
1 1 −1 −1 −1 1
1 −1 1 −1 −1 1
1 −1 −1 1 −1 −1
1 −1 −1 −1 1 −1
 e 2H6 =

1 1 1 1 1 1
1 −1 −1 −1 −1 −1
1 1 1 −1 −1 −1
1 −1 −1 1 1 −1
1 1 −1 1 −1 1
1 −1 1 −1 1 1

De seguida, multiplica-se cada uma das duas matrizes pela sua matriz transposta
e soma-se as duas matrizes resultantes.
1H6(1H
T
6 ) =

1 1 1 1 1 1
1 1 1 1 1 −1
1 1 −1 −1 −1 1
1 −1 1 −1 −1 1
1 −1 −1 1 −1 −1
1 −1 −1 −1 1 −1


1 1 1 1 1 1
1 1 1 −1 −1 −1
1 1 −1 1 −1 −1
1 1 −1 −1 1 −1
1 1 −1 −1 −1 1
1 −1 1 1 −1 −1

=

6 4 0 0 −2 −2
4 6 −2 −2 0 0
0 −2 6 2 0 0
0 −2 2 6 0 0
−2 0 0 0 6 2
−2 0 0 0 2 6

2H6(2H
T
6 ) =

1 1 1 1 1 1
1 −1 −1 −1 −1 −1
1 1 1 −1 −1 −1
1 −1 −1 1 1 −1
1 1 −1 1 −1 1
1 −1 1 −1 1 1


1 1 1 1 1 1
1 −1 1 −1 1 −1
1 −1 1 −1 −1 1
1 −1 −1 1 1 −1
1 −1 −1 1 −1 1
1 −1 −1 −1 1 1

=

6 −4 0 0 2 2
−4 6 2 2 0 0
0 2 6 −2 0 0
0 2 −2 6 0 0
2 0 0 0 6 −2
2 0 0 0 −2 6

1H6(1H
T
6 ) +2 H6(2H
T
6 ) =

12 0 0 0 0 0
0 12 0 0 0 0
0 0 12 0 0 0
0 0 0 12 0 0
0 0 0 0 12 0
0 0 0 0 0 12
 = 12I6
2.3 Matriz de Hadamard 15
Para (7, 14, 6, 3, 2)−BIBD:
X = {1, 2, 3, 4, 5, 6, 7}
e
A = {123, 125, 136, 145, 147, 167, 234, 246, 257, 267, 347, 356, 357, 456}
A sua matriz de incidência é a seguinte:
Figura 2.6: Matriz de incidência do (7, 14, 6, 3, 2)−BIBD
Assim, seguindo o procedimento anteriormente descrito, a matriz de Hadamard
é a seguinte:
1H8 =

1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 −1
1 1 1 −1 −1 −1 −1 1
1 1 −1 1 −1 −1 −1 1
1 −1 −1 −1 1 1 −1 1
1 −1 1 −1 1 −1 −1 −1
1 −1 −1 1 −1 −1 1 −1
1 −1 −1 −1 −1 1 1 −1

e
2H8 =

1 1 1 1 1 1 1 1
1 −1 −1 −1 −1 −1 −1 −1
1 1 1 1 −1 −1 −1 −1
1 −1 −1 −1 1 1 1 −1
1 1 −1 −1 1 −1 −1 1
1 −1 1 −1 −1 1 1 1
1 1 −1 1 −1 1 −1 1
1 −1 1 1 1 −1 1 −1

16 Designs
1H8(1H
T
8 ) =

1 1 1 1 1 1 1 1
1 −1 −1 −1 −1 −1 −1 −1
1 1 1 1 −1 −1 −1 −1
1 −1 −1 −1 1 1 1 −1
1 1 −1 −1 1 −1 −1 1
1 −1 1 −1 −1 1 1 1
1 1 −1 1 −1 1 −1 1
1 −1 1 1 1 −1 1 −1


1 1 1 1 1 1 1 1
1 1 1 1 −1 −1 −1 −1
1 1 1 −1 −1 1 −1 −1
1 1 −1 1 −1 −1 1 −1
1 1 −1 −1 1 1 −1 −1
1 1 −1 −1 1 −1 −1 1
1 1 −1 −1 −1 −1 1 1
1 −1 1 1 1 −1 −1 −1

=

8 6 0 0 0 −2 −2 −2
6 8 −2 −2 −2 0 0 0
0 −2 8 4 0 2 −2 −2
0 −2 4 8 0 −2 2 −2
0 −2 0 0 8 2 −2 2
−2 0 2 −2 2 8 0 0
−2 0 −2 2 −2 0 8 4
−2 0 −2 −2 2 0 4 8

2H8(2H
T
8 ) =

1 1 1 1 1 1 1 1
1 −1 −1 −1 −1 −1 −1 −1
1 1 1 1 −1 −1 −1 −1
1 −1 −1 −1 1 1 1 −1
1 1 −1 −1 1 −1 −1 1
1 −1 1 −1 −1 1 1 1
1 1 −1 1 −1 1 −1 1
1 −1 1 1 1 −1 1 −1


1 1 1 1 1 1 1 1
1 −1 1 −1 1 −1 1 −1
1 −1 1 −1 −1 1 −1 1
1 −1 1 −1 −1 −1 1 1
1 −1 −1 1 1 −1 −1 1
1 −1 −1 1 −1 1 1 −1
1 −1 −1 1 −1 1 −1 1
1 −1 −1 −1 1 1 1 −1

=

8 −6 0 0 0 2 2 2
−6 8 2 2 2 0 0 0
0 2 8 −4 0 −2 2 2
0 2 −4 8 0 2 −2 2
0 2 0 0 8 −2 2 −2
2 0 −2 2 −2 8 0 0
2 0 2 −2 2 0 8 −4
2 0 2 2 −2 0 −4 8

2.3 Matriz de Hadamard 17
1H8(1H
T
8 ) +2 H8(2H
T
8 ) =

16 0 0 0 0 0 0 0
0 16 0 0 0 0 0 0
0 0 16 0 0 0 0 0
0 0 0 16 0 0 0 0
0 0 0 0 16 0 0 0
0 0 0 0 0 16 0 0
0 0 0 0 0 0 16 0
0 0 0 0 0 0 0 16

= 16I8
Para (9, 18, 8, 4, 3)−BIBD:
X = {1, 2, 3, 4, 5, 6, 7, 8, 9}
e
A =
{
1245, 1268, 1279, 1345, 1369, 1378, 1467, 1589, 2356, 2357, 2389, 2468, 2479,
3469, 3478, 4589, 5678, 5679
}
A sua matriz de incidência é a seguinte:
Figura 2.7: Matriz de incidência do (9, 18, 8, 4, 3)−BIBD
Assim, seguindo o procedimento anteriormente descrito, a matriz de Hadamard
é a seguinte:
1H10 =

1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 −1
1 1 1 1 −1 −1 −1 −1 −1 1
1 −1 −1 −1 1 1 1 −1 −1 1
1 1 −1 −1 1 −1 −1 1 −1 −1
1 1 −1 −1 1 −1 −1 −1 1 1
1 −1 1 −1 −1 1 −1 1 −1 1
1 −1 −1 1 −1 −1 1 1 −1 −1
1 −1 1 −1 −1 −1 1 −1 1 −1
1 −1 −1 1 −1 1 −1 −1 1 −1

e
18 Designs
2H10 =

1 1 1 1 1 1 1 1 1 1
1 −1 −1 −1 −1 −1 −1 −1 −1 −1
1 1 1 1 1 −1 −1 −1 −1 −1
1 1 1 −1 −1 1 1 −1 −1 −1
1 −1 −1 1 1 1 1 1 −1 −1
1 1 −1 −1 −1 −1 −1 1 1 1
1 −1 −1 1 −1 1 −1 −1 1 1
1 1 −1 −1 1 −1 1 −1 1 1
1 −1 1 1 −1 −1 1 1 1 −1
1 −1 1 −1 1 1 −1 1 −1 1

1H10(1H
T
10) +2 H10(2H
T
10) =

20 0 0 0 0 0 0 0 0 0
0 20 0 0 0 0 0 0 0 0
0 0 20 0 0 0 0 0 0 0
0 0 0 20 0 0 0 0 0 0
0 0 0 0 20 0 0 0 0 0
0 0 0 0 0 20 0 0 0 0
0 0 0 0 0 0 20 0 0 0
0 0 0 0 0 0 0 20 0 0
0 0 0 0 0 0 0 0 20 0
0 0 0 0 0 0 0 0 0 20

= 20I10
Com o aumento de v, torna-se quase impossível colocar todos os cálculos numa
página, como podemos observar no Anexo A.
Capítulo 3
Números
A teoria dos números é um dos ramos da matemática que trabalha essencialmente
nas propriedades dos números em geral. Em particular, temos o estudo dos números
naturais, cujo conjunto é representado por N, também denominados de números
inteiros positivos.
Além deste conjunto, também são estudados os números inteiros, cujo conjunto
é representado por Z, ou seja, além dos números inteiros positivos, este conjunto
também contém os números inteiros menores ou iguais a zero. Considera-se que a é
divisível por b quando ambos são diferentes de zero e a
b
∈ Z.
3.1 Números pares e ímpares
Definição 3.1.1. Considera-se que n é um número par quando n = 2k, sendo k
um número inteiro qualquer. Diz-se que n é um número ímpar quando n = 2k + 1,
sendo k um número inteiro qualquer.
3.2 Números primos
Definição 3.2.1. Um número primo é um número inteiro, maior ou igual a dois,
que só é divisível por si mesmo e por 1.
Os primeiros dezoito números primos são: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, ...
3.3 Combinações de conjuntos
Definição 3.3.1. Sejam k, n ∈ N0, tal que n ≥ k. O número de k−combinações,
de um conjunto, constituído por n elementos, representa-se por
(
n
k
)
e é calculado da
forma seguinte:
C(n, k) =
(
n
k
)
=
n!
k!(n− k)! (3.1)
19
20 Números
As combinações verificam as seguintes propriedades:(
n
k
)
=
(
n− 1
k
)
+
(
n− 1
k − 1
)
(
n
0
)
=
(
n+ 1
0
)
(
n
n
)
=
(
n+ 1
n+ 1
)
(
n
k
)
=
(
n
n− k
)
(
n
0
)
=
(
n
n
)
= 1
3.4 Congruência
Definição 3.4.1. Seja n é um número natural maior ou igual a dois. Dois números
inteiros a e b são congruentes em relação a n quando n mede a diferença entre a e
b, ou seja, quando a diferença entre a e b é divisível por n, ou ainda quando
a− b
n
∈ Z (3.2)
Quando tal acontece diz-se que "a é congruente a b módulo n" e escreve-se
a ≡ b (mod n) (3.3)
3.5 Relação de recorrência
Definição 3.5.1. Dada uma sequência de números reais a0, a1, ..., an, a sua relação
de recorrência é uma equação que nos permite relacionar o termo an com os seus
precedentes, sabendo que ai < an, para i < n.
Observação 3.5.1. A relação de recorrência pode ser linear ou não linear, ho-
mogénea ou não homogénea, de ordem k, onde k é a diferença entre o maior e o
menor índice dos termos da sequência, ou seja, a sequência expressa-se da forma
an, an−1, an−2, ..., an−k.
Uma relação de recorrência linear, homogénea de ordem k e com coeficientes
constantes representa-se da seguinte forma
Cnan + Cn−1an−1 + ...+ Cn−kan−k = 0, n ≥ k (3.4)
Substituindo an por λn, chega-se à equação característica associada à equação
(3.4)
Cnλ
n + Cn−1λn−1 + ...+ Cn−kλn−k = 0 (3.5)
3.5 Relação de recorrência 21
Exemplo 3.5.1. Resolução de uma relação de recorrência linear, homogénea de
ordem 1. a0 = 1
an = 2an−1
Solução homogénea:
an = 2an−1 ⇔ an − 2an−1 = 0
↓ an = λn
Equação característica:
⇔ λn − 2λn−1 = 0
⇔ λn−1(λ− 2) = 0
⇔ λn−1 = 01 ∨ λ = 2 (raiz real simples)
Assim, a solução geral é da seguinte forma:
an = C2
n , onde C ∈ R
Como a0 = 1 (condição inicial), então:
a0 = 1⇔ C20 = 1⇔ C = 1
Por conseguinte, a solução da relação de recorrência é
an = 2
n
Exemplo 3.5.2. Resolução de uma relação de recorrência linear, não homogénea,
completa de ordem 1. a1 = 2
an = an−1 + n
Equação homogénea associada:
an − an−1 = 0
↓ an = λn
Equação característica:
⇔ λn − λn−1 = 0
⇔ λn−1(λ− 1) = 0
1λn−1 = 0⇒ an−1 = 0⇒ an = 0 que é uma solução trivial, costuma-se excluir porque obtém-se
da solução geral para C = 0 ∈ R.
22 Números
⇔ λ = 1 (raiz real simples)
Assim, a solução geral da equação homogénea associada é
anh = ah = C1
n = C, C ∈ R
Solução particular:
anp = ap = An
2 +Bn
↓ an − an−1 = n
⇔ An2 +Bn− (A(n− 1)2 +B(n− 1)) = n
⇔ An2 +Bn− An2 + 2An− A−Bn+B = n
⇔ 2An− A+B = n
⇔
{
2A = 1
−A+B = 0
⇔
{
A = 1
2
B = 1
2
Assim,
ap =
1
2
n2 +
1
2
n
Sabemos que a solução geral da relação de recorrência é dada por an = ah + ap,
então
an = C +
1
2
n2 +
1
2
n
Como a1 = 2 (condição inicial), então
a1 = 2⇔ C + 12 × 12 + 12 × 1 = 2⇔ C = 1, ou seja, a solução solicitada é
an = 1 +
1
2
n2 +
1
2
n, n ≥ 1
3.6 Números eulerianos
Os números eulerianos, calculados em 1755 por Leonhard Euler, representam-se
por E(n, k) ou En,k ou ainda
〈
n
k
〉
e permitem calcular o número de permutações
de n elementos, onde n ∈ N, ou seja, do conjunto {1, 2, ..., n}, com precisamente k
ascendentes, onde k ∈ N0 (ver Definição 3.6.1).
3.6 Números eulerianos 23
Definição 3.6.1. Considerando que uma permutação de {1, 2, ..., n} é representada
por P = (p1, p2, p3, ..., pi, ..., pn), onde 1 ≤ i ≤ n, então para qualquer índice i em
que:
• 1 ≤ i < n, um ascendente da permutação P ocorre quando pi < pi+1;
• 1 ≤ i < n, um descendente da permutação P ocorre quando pi > pi+1;
• 1 ≤ i ≤ n, um excedente da permutação P ocorre quando pi > i;
• 1 ≤ i ≤ n, um excedente fraco da permutação P ocorre quando pi ≥ i.
Observação 3.6.1. Os números eulerianos E(n, k) também permitem calcular o
número de permutações com k descendentes, k excedentes ou ainda k+ 1 excedentes
fracos.
Exemplo 3.6.1. Consideremos a permutação P = (3, 4, 1, 5, 2), em que p1 = 3,
p2 = 4, p3 = 1, p4 = 5 e p5 = 2.
Para identificar os ascendentes da permutação P , em que 1 ≤ i < 5, tem-se:
i = 1 p1 < p2 ⇔ 3 < 4 V
i = 2 p2 < p3 ⇔ 4 < 1 F
i = 3 p3 < p4 ⇔ 1 < 5 V
i = 4 p4 < p5 ⇔ 5 < 2 F
 logo, existem ascendentes da permutação Pem i = 1 e i = 3
Para identificar os descendentes de permutação P , em que 1 ≤ i < 5:
i = 1 p1 > p2 ⇔ 3 > 4 F
i = 2 p2 > p3 ⇔ 4 > 1 V
i = 3 p3 > p4 ⇔ 1 > 5 F
i = 4 p4 > p5 ⇔ 5 > 2 V
 conclui-se que existem descendentesda permutação P em i = 2 e i = 4
Para identificar os excedentes de permutação P , em que 1 ≤ i ≤ 5:
i = 1 p1 > 1 ⇔ 3 > 1 V
i = 2 p2 > 2 ⇔ 4 > 2 V
i = 3 p3 > 3 ⇔ 1 > 3 F
i = 4 p4 > 4 ⇔ 5 > 4 V
i = 5 p5 > 5 ⇔ 2 > 5 F

então, existem excedentes da permutação P
em i = 1, i = 2 e i = 4
Para identificar os excedentes fracos de permutação P , em que 1 ≤ i ≤ 5:
i = 1 p1 ≥ 1 ⇔ 3 ≥ 1 V
i = 2 p2 ≥ 2 ⇔ 4 ≥ 2 V
i = 3 p3 ≥ 3 ⇔ 1 ≥ 3 F
i = 4 p4 ≥ 4 ⇔ 5 ≥ 4 V
i = 5 p5 ≥ 5 ⇔ 2 ≥ 5 F

ou seja, existem excedentes fracos
da permutação P em i = 1, i = 2 e i = 4
24 Números
Os números eulerianos permitem construir o triângulo de Euler através da fór-
mula de recorrência En,0 = En,n−1 = 1, n ≥ 1
En,k = (k + 1)En−1,k + (n− k)En−1,k−1 ou através da fórmula
explícita
En,k = E(n, k) =
〈n
k
〉
=
k∑
j=0
(−1)j
(
n+ 1
j
)
(k + 1− j)n, n ≥ 1 (3.6)
Assim, a relação entre o triângulo de Euler e os números eulerianos é a que se
segue:
1
1 1
1 4 1
1 11 11 1
1 26 66 26 1
...
E1,0
E2,0 E2,1
E3,0 E3,1 E3,2
E4,0 E4,1 E4,2 E4,3
E5,0 E5,1 E5,2 E5,3 E5,4
...
No cálculo dos números eulerianos, em vez de utilizar a fórmula explícita (3.6),
usamos as seguintes propriedades:
E(n, k) =
〈n
k
〉
= (k + 1)
〈
n− 1
k
〉
+ (n− k)
〈
n− 1
k − 1
〉
E(n, 0) =
〈n
0
〉
= 1, n ≥ 1
E(n, n− 1) =
〈
n
n− 1
〉
= 1, n ≥ 1
〈n
k
〉
=
〈
n
n− 1− k
〉
, n ≥ 1
Exemplo 3.6.2. Usando a fórmula (3.6), calculemos o número de permutações de
{1, 2, 3, 4, 5} com três ascendentes, representado por E5,3.
3.6 Números eulerianos 25
E5,3 = E(5, 3) =
〈
5
3
〉
=
3∑
j=0
(−1)j
(
5 + 1
j
)
(3 + 1− j)5
= (−1)0
(
6
0
)
(4− 0)5 + (−1)1
(
6
1
)
(4− 1)5+
(−1)2
(
6
2
)
(4− 2)5 + (−1)3
(
6
3
)
(4− 3)5
= 1× 1× 45 − 6× 35 + 15× 25 − 20× 15
= 1024− 1458 + 480− 20
= 26
Conclui-se que existem 26 permutações do conjunto {1, 2, 3, 4, 5} com três ascen-
dentes, que são as seguintes:∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣
(1, 2, 3, 5, 4)
(1, 2, 4, 3, 5)
(1, 2, 4, 5, 3)
(1, 2, 5, 3, 4)
(1, 3, 2, 4, 5)
(1, 3, 4, 5, 2)
(1, 3, 5, 2, 4)
(1, 4, 2, 3, 5)
(1, 4, 5, 2, 3)
(1, 5, 2, 3, 4)
∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣
(2, 1, 3, 4, 5)
(2, 3, 1, 4, 5)
(2, 3, 4, 1, 5)
(2, 3, 4, 5, 1)
(2, 3, 5, 1, 4)
(2, 4, 1, 3, 5)
(2, 4, 5, 1, 3)
(2, 5, 1, 3, 4)
∣∣∣∣∣∣∣∣
(3, 1, 2, 4, 5)
(3, 4, 1, 2, 5)
(3, 4, 5, 1, 2)
(3, 5, 1, 2, 4)
∣∣∣∣∣∣
(4, 1, 2, 3, 5)
(4, 5, 1, 2, 3)
(4, 5, 2, 1, 3)
∣∣(5, 1, 2, 3, 4)
Exemplo 3.6.3. Utilizando as propriedades anteriores, calculemos o número de
permutações do conjunto {1, 2, 3, 4, 5} com dois excedentes.
E(5, 2) =
〈
5
2
〉
= 3
〈
4
2
〉
+ 3
〈
4
1
〉
= 3
3〈32
〉
︸ ︷︷ ︸
1
+2
〈
3
1
〉+ 3
2〈31
〉
+ 3
〈
3
0
〉
︸ ︷︷ ︸
1

= 18 + 12
〈
3
1
〉
= 18 + 12
2〈21
〉
︸ ︷︷ ︸
1
+2
〈
2
0
〉
︸ ︷︷ ︸
1

= 66
26 Números
Capítulo 4
Grafos
O início da teoria dos grafos tem como importante referência a publicação
em 1736, do trabalho do matemático Euler sobre as pontes de Ko¨nigsberg. Em
Ko¨nigsberg existia o rio Preguel com sete pontes que faziam a ligação entre duas
ilhas e as margens do rio, tal como está exemplificado na Figura 4.1.
Figura 4.1: As sete pontes de Ko¨nigsberg
Era prática corrente para cada habitante da cidade, tentar encontrar um trajeto
que percorresse todas as pontes uma única vez e que regressasse ao ponto de partida.
As tentativas foram muitas e todas sem sucesso. Foi então que decidiram colocar o
problema a Euler.
Euler, através da construção de um grafo, baseado nas sete pontes deKo¨nigsberg,
provou que era impossível criar um caminho que atravessasse cada uma das sete pon-
tes uma única vez, como se ilustra na figura seguinte.
Figura 4.2: Grafo criado por Euler para as sete pontes de Ko¨nigsberg
Atualmente, a teoria dos grafos é utilizada em muitas situações, como por exem-
plo, para ordenar as hiperligações num motor de busca, para encontrar o caminho
mais curto para um determinado destino através do GPS, em redes de transportes.
27
28 Grafos
4.1 Alguns conceitos básicos
As notações e terminologias que iremos aplicar são as que a nosso ver são as
mais utilizadas. Sendo a teoria dos grafos relativamente recente, as notações e
terminologias presentes na literatura não são únicas.
Definição 4.1.1. Um grafo G=(V,E) é uma estrutura matemática composta por
dois conjuntos finitos e não vazios V(G) e E(G). Os elementos de V são denominados
de vértices e os elementos de E são denominados de arestas. Denota-se por |V | o
número de vértices do grafo G e por |E| o número de arestas do grafo G.
O número n de vértices do conjunto V , isto é, |V | = n é chamado de ordem do
grafo G.
Observação 4.1.1. A notação deg(vi) representa o grau de cada um dos vértices
do grafo, ou seja, o número de arestas incidentes em cada vértice. A soma de todos
os graus dos vértices do grafo G é igual ao dobro do número de arestas
n∑
i=1
deg(vi) = 2 |E| (4.1)
Como utilizaremos números ou letras maiúsculas ou minúsculas para representar
um vértice, então para representar uma aresta formada pelos vértices a e b, usaremos
a forma ab.
Definição 4.1.2. Uma aresta considera-se simples quando está associada a um
único par de vértices e considera-se múltipla quando está associada duas ou mais
vezes ao mesmo par de vértices. Um grafo que possua só arestas simples é um grafo
simples, enquanto que um grafo que possua pelo menos uma aresta múltipla é um
multigrafo.
Observação 4.1.2. Além destes dois tipos de grafos ainda existem os pseudografos
que ocorrem quando um grafo tem um ou mais loops, ou seja, pelo menos uma das
arestas tem vértices terminais que coincidem.
Figura 4.3: Da esquerda para a direita, grafo simples, multigrafo e pseudografo
4.1 Alguns conceitos básicos 29
Definição 4.1.3. Num grafo G = (V,E), definimos caminho como uma sequência
de vértices ligados entre si.
Definição 4.1.4. Se um caminho de um grafo não repete vértices nem arestas
dizemos que é um caminho simples.
No grafo G, um exemplo de um caminho simples seria d-e-g-f.
Figura 4.4: Um caminho simples do grafo G
Definição 4.1.5. Um caminho aberto define-se como um caminho que começa num
vértice e termina em outro. Quando um caminho começa e termina no mesmo vértice
diz-se que é um caminho fechado.
No grafo G (Figura 4.5), um exemplo de um caminho fechado seria d-e-g-f-d e
de um caminho aberto seria d-e-g.
Figura 4.5: Um caminho fechado do grafo G
Definição 4.1.6. Quando um caminho pode repetir as arestas e os vértices diz-se
que é um passeio.
No grafo G (Figura 4.6), um exemplo de um passeio seria b-c-d-b-c-a-d.
Figura 4.6: Um passeio do grafo G
30 Grafos
Definição 4.1.7. Um caminho que repita os vértices mas não as arestas, chama-se
percurso.
No grafo G (Figura 4.7), um exemplo de um percurso seria e-g-d-f-e-d-c-b-d-a-c.
Figura 4.7: Um percurso do grafo G
Definição 4.1.8. Um percurso que comece e termine no mesmo vértice, chama-se
circuito.
No grafo G (Figura 4.8), um exemplo de um circuito seria e-g-d-f-e.
Figura 4.8: Um circuito do grafo G
Definição 4.1.9. Quando um caminho fechado não repete nem as arestas nem os
vértices (exceto os terminais), diz-se que é um ciclo.
No grafo G (ver Figura 4.9), um exemplo de um ciclo seria a-c-b-d-a.
Figura 4.9: Um ciclo do grafo G
4.2 Grafos especiais 31
Exemplo 4.1.1. Considerando o seguinte grafo G, é possível identificar um caminho
simples, um caminho fechado, um percurso, um passeio, um circuito e um ciclo
(tendo em conta as Figuras 4.4 a 4.9).
Figura 4.10: Grafo G
4.2 Grafos especiais
Existem grafos com características específicas que permitem que os associemos
em grupos. Apresentaremos apenas alguns grafos que direta ou indiretamente estão
relacionados com este trabalho.
Grafo completo
Definição 4.2.1. Um grafo completo, representado porKn, ocorre quando um grafo
de ordem n tem todos os pares de vértices distintos ligados exclusivamente por uma
aresta (vértices adjacentes). Estes grafos de ordem n têm n(n−1)
2
arestas e também
são considerados como grafos regulares, pois todos os vértices têm grau n − 1. A
Figura 4.11 apresenta alguns exemplos.
Figura 4.11: Grafos completos
Grafo cíclico
Definição 4.2.2. Um grafo cíclico, Cn, onde n ≥ 3 representa o número de vértices,
é um grafo simples em que o número de vértices é igual ao número de arestas
(|V | = |E|) e onde cada vértice tem grau 2 (ver Figura 4.12).
32 Grafos
Figura 4.12: Grafos cíclicos
Grafo roda
Definição 4.2.3. Um grafo roda, Wn, onde n ≥ 4 representa o número de vértices
e 2(n− 1) representa o número de arestas, é obtido quando um vértice é adicionado
a um grafo cíclico e conectado aos restantes vértices (ver Figura 4.13).
Figura 4.13: Grafos roda
Grafo nulo
Definição 4.2.4. Um grafo nulo, Nn, onde n representa o número de vértices, é um
grafo que não tem arestas (ver Figura 4.14).
Figura 4.14: Grafos nulos
Grafo caminho
Definição 4.2.5. Um grafo caminho, Pn, com n ≥ 2, é um grafo simples onde
|V | = |E|+ 1 (exemplos na Figura 4.15).
Figura 4.15: Grafos caminho
4.2 Grafos especiais 33
Grafo bipartido
Definição 4.2.6. Um grafo bipartido ocorre quando os vértices se podem separar
em dois subconjuntos V1 e V2, de forma a que V = V1 ∪ V2, ou seja, as arestas têm
um vértice em V1 e outro em V2, mas nunca no mesmo subconjunto (Figura 4.16).
Figura 4.16: Grafo bipartido
Observação 4.2.1. Outra forma de verificar que as arestas não ligam vértices do
mesmo subconjunto é colorir os vértices do subconjunto V1 de branco e os vértices
do subconjunto V2 de preto. Assim verifica-se que as arestas não ligam vértices da
mesma cor (Figura 4.17).
Figura 4.17: Grafo bipartido com vértices de cores diferentes
Grafo bipartido completo
Definição 4.2.7. Um grafo bipartido é considerado completo quando todos os vér-
tices do subconjunto V1 estão ligados a todos os vértices do subconjunto V2. Se
considerarmos que o número de vértices do subconjunto V1 é n e do subconjunto V2
é m, então o número total de vértices do grafo bipartido completo será de n+m e o
número total de arestas será de n×m. Um grafo bipartido completo será denotado
por Kn,m.
Figura 4.18: Grafo bipartido completo
34 Grafos
Grafo Conexo
Definição 4.2.8. Um grafo diz-se conexo se existir um caminho que una dois quais-
quer vértices. Caso contrário, diz-se desconexo.
Figura 4.19: Grafo conexo e grafo desconexo
4.2.1 Grafo Euleriano
Definição 4.2.9. Um circuito de Euler ocorre quando um caminho fechado percorre
todas as arestas de um grafo, sem as repetir. Quando um grafo tem um circuito de
Euler denomina-se por grafo de Euler ou grafo Euleriano.
No grafo da Figura 4.20, o circuito de Euler é a-e-b-a-f-b-c-f-g-d-c-a.
Teorema 4.2.1. Um grafo conexo é Euleriano se, e só se, todos os seus vértices
têm grau par.
4.2.2 Grafo Hamiltoniano
Em 1857, o matemático Hamilton apresentou um problema e a respetiva solução.
O problema, designado por viagem à volta do mundo, consistia em percorrer todos os
vértices de um dodecaedro em que cada vértice correspondia a uma cidade (Londres,
Paris, Roma, etc). A finalidade era percorrer todas as cidades uma única vez e
regressar à cidade da partida, sendo que só era possível ir de uma cidade a outra se
existisse uma aresta entre os respetivos vértices. Este problema originou o ciclo de
Hamilton.
Definição 4.2.10. Um ciclo de Hamilton ocorre quando um caminho percorre todos
os vértices de um grafo, onde só os vértices terminais podem se repetir. Quando
um grafo tem um ciclo de Hamilton denomina-se por grafo de Hamilton ou grafo
Hamiltoniano.
No grafo da Figura 4.20, o ciclo de Hamilton é a-c-d-g-f-b-e-a.
4.2 Grafos especiais 35
Exemplo 4.2.1. O seguinte grafo é de Euler e de Hamilton.
Figura 4.20: Um grafo de Euler e de Hamilton
Verificar a existência de um ciclo de Hamilton não é fácil. Existem teoremas com
condições que permitem identificar a existência de um tal ciclo.
Teorema 4.2.2 (Teorema de Dirac1 - 1951). Quando um grafo G simples tem um
número de vértices superior ou igual a três (n ≥ 3) e o grau de cada um desses
vértices é maior ou igual ao número de vértices a dividir por dois (deg(v) ≥ n
2
),
então G é um grafo Hamiltoniano.
Teorema 4.2.3 (Teorema de Ore2 - 1960). Quando um grafo G simples tem um
número de vértices superior ou igual a três (n ≥ 3) e a soma dos graus de dois
vértices não adjacentes é maior ou igual ao número de vértices (deg(v)+deg(u)≥n),
então G é um grafo Hamiltoniano.
4.2.3 Grafo Planar
Definição 4.2.11. Quando um grafo pode ser representado sem que as suas arestas
se cruzem, denomina-se de grafo planar (ver Figura 4.21).
Figura 4.21: Representação do grafo K4 na forma planar
Definição 4.2.12. Quando um grafo é planar, o seu desenho divide o plano em
faces. A face de um grafo planar representa-se por fi. Ao número de arestas que
cada face contém chamamos grau da face e representa-se por deg(fi). Temos que a
soma do grau de cada uma das faces é igual ao dobro do número de arestas
m∑
i=1
deg(fi) = 2 |E| (4.2)
1Paul Adrien Maurice Dirac, 1902-1984, físico britânico
2∅ystein Ore, 1899-1968, matemático norueguês
36 Grafos
Através da fórmula de Euler (4.3), é possível relacionar num grafo planar o
número de vértices, de arestas e de faces.
Teorema 4.2.4 (Fórmula de Euler). Quando um grafo é conexo e planar o seu
número de vértices menos o seu número de arestas mais o seu número de faces é
igual a dois, ou seja,
|V | − |E|+ |f | = 2 (4.3)
Corolário 4.2.4.1. Quando um grafo é simples, conexo, planar e o seu número
de vértices é superior a dois (|V | > 2), então o seu número de arestas tem de ser
menor ou igual ao triplo do número de vértices menos seis
|E| ≤ 3 |V | − 6 (4.4)
Exemplo 4.2.2. Utilizando o grafo planar da Figura 4.21 verifica-se que:
|V | = 4
|E| = 6
|E| ≤ 3 |V | − 6⇐⇒ 6 ≤ 3× 4− 6⇐⇒ 6 ≤ 12− 6⇐⇒ 6 ≤ 6
Corolário 4.2.4.2. Quando um grafo é bipartido, conexo e planar o seu número de
arestas tem de ser menor ou igual ao dobro do número de vértices menos quatro
|E| ≤ 2 |V | − 4 (4.5)
Exemplo 4.2.3. Se considerarmos um grafo G conexo e planar em que
7∑
i=1
deg(fi) = 22
é possível calcular o número de vértices e de arestas e ainda construir o grafo G (ver
Figura 4.22). Assim, neste exemplo, sabe-se que o grafo é constituído por sete faces
e por onze arestas.
7∑
i=1
deg(fi) = 22⇔
7∑
i=1
deg(fi) = 2 |E| ⇔ 22 = 2 |E| ⇔ |E| = 11
Através da fórmula de Euler, descobre-se que o número de vértices é igual a seis,
porque
|V | − |E|+ |f | = 2⇔ |V | − 11 + 7| = 2⇔ |V | = 6
Com estas caraterísticas, o grafo G pode ser representado da seguinte forma:
Figura 4.22: Grafo G conexo e planar
4.3 Matriz de Incidência 37
Grafo Poliédrico
Definição 4.2.13. Um grafo planar, simples e conexo é poliédrico se o grau de
todos os seus vértices e de todas as suas faces for maior ou igual a três (deg(vi) ≥ 3
e deg(fi) ≥ 3).
Observe-se que o grafo G da Figura 4.22 é um grafo poliédrico.
4.3 Matriz de Incidência
Definição 4.3.1. A matriz de incidência, IG, de um grafo G é uma matriz em que
as linhas representam os vértices, as colunas representam as arestas e os elementos
da matriz IG = (aij) são definidos por:
aij=

0, quando vi não é vértice terminal em ej
1, quando vi é vértice terminal em ej
2, quando vi é vértice terminal duma aresta ej em loop
Proposição 4.3.1. A soma dos elementos de cada linha de IG é igual ao grau do
vértice correspondente e a soma dos elementos de cada coluna de IG é igual a 2.
Exemplo 4.3.1. Considerando o grafo G da Figura 4.23
Figura 4.23: Grafo G
a sua matriz de incidência será a seguinte:
Figura 4.24: Matriz de incidência do grafo G
4.4 Matriz de Adjacência
Definição 4.4.1. A matriz de adjacência, AG, de um grafo G é uma matriz em que
tanto as linhas como as colunas representam os vértices, ou seja, a matriz AG é uma
38 Grafos
matriz quadrada de ordem n. Os elementos da matriz AG = (aij) determinam-se da
seguinte forma:
• se os vértices vi e vj não estão ligados por uma aresta, aij = 0
• se i 6= j, aij é igual ao número de arestas entre vi e vj
• se i = j, aij corresponde ao número de loops em vi
Exemplo 4.4.1. Considerando o grafo G (ver Figura 4.25).
Figura 4.25: Grafo G
A sua matriz de adjacência será a seguinte:
Figura 4.26: Matriz de adjacência do grafo G
4.5 Matching Perfeito
Definição 4.5.1. Um matching é um subconjunto de arestas em que estas não são
adjacentes, ou seja, não têm os mesmos vértices terminais. Considera-se que um
matching, M , é perfeito quando todos os vértices estão presentes em apenas uma
das arestas.
O número de arestas de M é igual a metade do número de vértices do grafo
|M | = |V |
2
(4.6)
Então, só existe matching perfeito quando o número de vértices do grafo é par.
4.6 Árvore Geradora 39
Exemplo 4.5.1. Considerando o grafo G (Figura 4.27), verifica-se que existe mat-
ching perfeito, pois M satura todos os vértices.
M = {12, 34, 56, 78}
Figura 4.27: Grafo G com matching perfeito
4.6 Árvore Geradora
Definição 4.6.1. Um grafo simples, conexo e sem ciclos denomina-se por árvore e
representa-se por T . Uma árvore de um grafo G denomina-se de árvore geradora se
for um subgrafo que contém todos os vértices do grafo G.
Teorema 4.6.1 (Teorema de Cayley 3). O número de árvores geradoras de um grafo
completo de ordem n é igual a r(Kn) = nn−2.
Exemplo 4.6.1. Considerando um grafo completo K6, pelo Teorema de Cayley
sabe-se que o número de árvores deste grafo é 1296.
r(K6) = 6
6−2 = 64 = 1296
Figura 4.28: Grafo completo K6
Das 1296 árvores geradoras do grafo completoK6, a Figura 4.29 representa alguns
exemplos.
3Arthur Cayley, 1821-1895, matemático inglês.
40 Grafos
Figura 4.29: Exemplos de árvores geradoras do grafo completo K6
4.6.1 Teorema da árvore-matriz
Teorema 4.6.2 (Teorema da árvore-matriz). Seja G = (V,E) um grafo sem loops,
com V = {v1, v2, ..., vn}. Sejam AG a matriz adjacência de G, S a matriz diagonal
com Sii = deg(vi) e Q = S − AG. Então, para qualquer 1 ≤ i ≤ n, o determinante
da matriz que se obtém de Q ao retirar a i−ésima linha e coluna, é igual ao número
de árvores geradoras do grafo G. Este número será denotado por T (G).
Observação 4.6.1. Quando o grafo G for completo, G = Kn, é usual utilizar a
notação r(Kn) ao invés de T (Kn) para designar o número de árvores geradoras de
Kn.
Exemplo 4.6.2. Considerando o grafo G da Figura 4.30 com quatro vértices,
Figura 4.30: Grafo G com quatro vértices
a matriz de adjacência é a seguinte:
Figura 4.31: Matriz de adjacência do grafo G
A matriz S é a seguinte:
Figura 4.32: Matriz S do grafo G
4.7 Número Cromático 41
Assim, subtraindo a matriz AG à matriz S, calcula-se a seguinte matriz Q:
Q = S − AG =

2 0 −1 −1
0 2 −1 −1
−1 −1 3 −1
−1 −1 −1 3

Se considerarmos i = 4, então a quarta linha e a quarta coluna serão retiradas,
e o determinante da matriz resultante é
T (G) =
∣∣∣∣∣∣
2 0 −1
0 2 −1
−1 −1 3
∣∣∣∣∣∣ = 2
∣∣∣∣ 2 −1−1 3
∣∣∣∣ − 1 ∣∣∣∣ 0 2−1 −1
∣∣∣∣ = 8
Conclui-se que o grafo G tem oito árvores geradoras.
4.7 Número Cromático
Em 1912 Birkhoff4 desenvolveu o polinómio cromático (ver Definição 4.7.1) ape-
nas para grafos planares, como ferramenta para tentar provar o famoso teorema
das quatro cores5. A generalização para quaisquer grafos surgiu em 1932 com os
matemáticos Whitney6 e Tutte7 .
Definição 4.7.1. O polinómio cromático, PG(k), de um grafo G é uma função que
determina o número de colorações de G, ou seja, o número de possibilidades de
colorir os vértices de G, com k diferentes cores.
Definição 4.7.2. Um grafo é k−colorável quando os vértices são coloridos por k
cores, de modo a que vértices adjacentes tenham cores distintas.
Definição 4.7.3. O número cromático de um grafo G sem loops, χ(G), é o menor
inteiro positivo k de cores utilizado para o grafo G ser k−colorável.
Exemplo 4.7.1. Cálculo de χ(G).
Figura 4.33: Grafo 4−colorável
4George David Birkhoff, 1884-1944, matemático americano.
5Teorema (das 4 cores): Seja um mapa plano, dividido em regiões, quatro cores são suficientes
para colori-lo de forma a que regiões vizinhas não partilhem a mesma cor (demonstrado por Appel
e Haken em 1976).
6Hassler Whitney, 1907-1989, matemático americano
7William Thomas Tutte, 1917-2002, matemático britânico
42 Grafos
Assim,
χ(G) = 4 porque aos vértices a, c, f, k corresponde a cor vermelha, aos vértices
b, d corresponde a cor verde, aos vértices e, g, h, j corresponde a cor azul e ao vértice
i a cor preta.
4.7.1 Polinómio Cromático
Enquanto que para alguns grafos com número reduzido de vértices e de arestas é
simples identificar o seu número cromático, para outros mais complexos, o contrário
acontece. Nestes casos, uma das possibilidades para obter o polinómio cromático
PG(k) é utilizar o Teorema 4.7.1.
Definição 4.7.4. Dado um grafo G e uma aresta uv ∈ E(G), a contração de uv
que se representa por G/uv corresponde a substituir os vértices u e v por um único
vértice que se denota u, v eliminando a aresta uv. A eliminação da aresta uv que se
representa por G− uv corresponde a suprimir a aresta uv (ver Figura 4.34).
Figura 4.34: Eliminação e contração da aresta 23 do grafo G
Teorema 4.7.1. Sejam G um grafo simples e planar e e uma aresta qualquer de
G. Então: PG(k) = PG−e(k) − PG/e(k) com G − e (eliminação da aresta e), G/e
(contração da aresta e).
Exemplo 4.7.2. Calculemos o polinómio cromático associado ao grafo G (Figura
4.35):
Figura 4.35: Grafo G
4.7 Número Cromático 43
Figura 4.36: Cálculo do polinómio cromático do grafo G
PG(K) = k
4 − 3k3 + 3k2 − k
k = 1→ PG(1) = 0 (impossível colorir os vértices de G com apenas 1 cor)
k = 2→ PG(2) = 24 − 3× 23 + 3× 22 − 2 = 2→ χ(G) = 2
Desta forma, utilizando o polinómio cromático, conclui-se que existem duas pos-
sibilidades de colorir o grafo G, com duas cores (valor que torna PG(k) 6= 0), porque
para k = 1 existe zero formas de colorir os vértices de G. Para k = 2 é o menor
inteiro positivo que satisfaz PG(k) > 0, sendo por isso o número cromático do grafo
G, isto é, χ(G) = 2.
O cálculo do polinómio cromático também pode ser apresentado utilizando um
diagrama (Figura 4.37).
44 Grafos
Figura 4.37: Polinómio cromático do grafo G
PG(k) = k
4 − 3k3 + 3k2 − k
4.7.2 Coloração de alguns grafos especiais
Grafo k−crítico
Definição 4.7.5. Um grafo G é k−crítico se χ(G) = k e χ(G − v) < k para cada
vértice v de G.
Figura 4.38: Grafo k−crítico
O grafo G da Figura 4.38 é 3−crítico pois χ(G) = 3 e χ(G−v1) = 2 = χ(G−v2) =
χ(G− v3) < 3 = k
4.8 Digrafos 45
Grafos completos
No caso dos grafos completos, o seu número cromático é sempre igual ao seu
número de vértices, isto é,
χ(Kn) = n (4.7)
Grafos cíclicos
No caso dos grafos cíclicos, o seu número cromático é igual a dois se o seu número
de vértices for par, ou igual a três se o seu número de vértices for ímpar, isto é,
χ(Cn) =
{
2 se n for par
3 se n for ímpar
(4.8)
Grafos roda
No caso dos grafos roda, o seu número cromático é igual a três se o seu número
de vértices for ímpar, ou igual a quatro se o seu número de vértices for par, ou seja,
χ(Wn) =
{
3 se n for ímpar
4 se n for par
(4.9)
4.8 Digrafos
Definição 4.8.1. Um digrafo D é um grafo orientado, ou seja, é constituído por
vértices e arestas direcionadas, designadas por arcos. Quando um arco é ab significa
que está direcionado de a para b, em que a é a cauda (t) do arco e b é a cabeça (h).
Para cada vértice de um digrafo definem-se o grau de entrada e o grau de saída.
O grau de entrada (degE(v)) é o número de arcos direcionados para o vértice e o
grau de saída (degS(v)) é o número de arcos direcionados para fora do vértice em
questão, ou seja, o número de arcos que saem do vértice.
Considera-se que se trata de um digrafo simples quando não tem arcos múlti-
plos nem loops. É loop-digrafo quando tem loops e multidigrafo quando tem arcos
múltiplos.
A matriz de incidência dos digrafos é construída de forma semelhante à dos gra-
fos. Contudo, quando o vértice é extremidade final do arco coloca-se o número 1 na
matriz e, quando o vértice é extremidade inicial do arco coloca-se o número −1 na
matriz.
A matriz de adjacência dos digrafos, por outro lado, é construída exatamente da
mesma forma que nos grafos. O mesmo também acontece na coloração dos vértices.
Nos digrafos, o número cromático é calculado da mesma forma que nos grafos.
Considera-se um digrafo fortemente conexo quando para cada par de vértices u,
v existe um caminho orientado de u para v. Para verificar se existe um circuito
direto de Euler nos digrafos segue-se a mesma lógica utilizada nos grafos, tendo em
46 Grafos
atenção a direção dos arcos. No caso do ciclo de Hamilton utiliza-se a adaptação
dos teoremas de Dirac e de Ore aos digrafos (ver Teoremas 4.8.1 e 4.8.2).
Teorema 4.8.1 (Teorema de Dirac (para digrafos)). Seja D um digrafo fortemente
conexo com n vértices. Se degS(v) ≥ n2 e degE(v) ≥ n2 para todo o v de D, então D
é hamiltoniano.
Teorema 4.8.2 (Teorema de Ore (para digrafos)). Seja D um digrafo simples com
n vértices. Se degS(u) + degE(v) ≥ n para todo o par de vértices não adjacentes u e
v de D, então D é hamiltoniano.
Exemplo 4.8.1. Considera-se o digrafo D com seis vértices e onze arcos:
Figura 4.39: Digrafo D com seis vértices
Através da representação do digrafo D (Figura 4.39) é possível construir uma ta-
bela (ver Tabela 4.1) indicando o grau de entrada e de saída de cada um dos vértices.
Tabela 4.1: Grau de entrada e de saída de cada um dos vértices
Vértices a b c d e f
Grau de entrada 0 1 2 1+1 (loop) = 2 3 3
Grau de saída 4 2 2 1+1 (loop) = 2 1 0
Considerando a tabela anterior, verifica-se que não existe circuito direto de Eu-
ler, pois existem vértices em que o seu grau de entrada é diferente do seu grau de
saída. Também não existe ciclo de Hamilton, porque, por exemplo, o vértice a só
tem graus de saída e o vértice f só tem graus de entrada.
A matriz de incidência deste digrafo é representada da seguinte forma:
Figura 4.40: Matriz de incidência do digrafo D com seis vértices
4.9 Polinómio de Tutte 47
4.9 Polinómio de Tutte
Em 1948, William Tutte, na sua tese de doutoramento, criou uma generalização
a R2 do polinómio cromático de um grafo que, anos mais tarde, serviu de base
para muitos estudos por parte de outros matemáticos, tais como, Vaughan Jones e
Renfrey Potts. Atualmente, o polinómio de Tutte é, principalmente, utilizado em
ciências da computação.
Definição 4.9.1. O polinómio de Tutte depende de duas variáveis, x e y, é definido
a partir de um grafo G não direcionado e representa-se por TG(x, y) ou T (G;x, y).
O polinómio de Tutte, de um grafo composto por mais que uma aresta, é calcu-
lado da seguinte forma:
TG(x, y) =

xTG−e , se a aresta e for uma ponte8
yTG/e , se a aresta e for um loop
1 , se E(G) = ∅
TG−e + TG/e , caso contrário
Observação 4.9.1. Utiliza-se este polinómio para se obter, por exemplo, informação
sobre as diferentes ligações de um grafo G.
Figura 4.41: Polinómio de Tutte do grafo completo K3
Assim, o polinómio de Tutte para o grafo completo de três vértices (ver Figura 4.41)
é
Tk3(x, y) = T (k3;x, y) = x
2 + x+ y (4.10)
8
Definição 4.9.2. Seja G conexo. Designa-se por ponte uma aresta que, ao ser eliminada, faz com
que G deixe de ser conexo.
48 Grafos
4.9.1 Polinómio de Tutte em grafos bipartidos
O polinómio de Tutte para grafos bipartidos completos Kn,2 é definido por:
Tn(x, y) = x
2(x+ 1)n−1 +
n−1∑
i=1
(x+ y)i(x+ 1)n−1−i , n ≥ 1 (4.11)
Ao trabalharmos com a equação (4.11), descobrimos uma nova expressão para
Tn(x, y):
Tn (x, y) =

(
n
0
)
xn+1 +
((
n
1
)− 1)xn + (n
2
)
xn−1 + ...+
(
n
n
)
x
+
(
n
2
)
xn−2
1∑
i=1
yi +
(
n
3
)
xn−3
2∑
i=1
yi +
(
n
4
)
xn−4
3∑
i=1
yi + ...+
(
n
n−1
)
x
n−2∑
i=1
yi
+
n−1∑
i=1
yi
(4.12)
Vamos provar que as duas fórmulas para Tn(x, y) são equivalentes para n ≥ 1,
utilizando o método de Indução Matemática em n:
x2 (x+ 1)n−1 +
n−1∑
i=1
(x+ y)i (x+ 1)n−1−i =
=

(
n
0
)
xn+1 +
((
n
1
)− 1)xn + (n
2
)
xn−1 + ...+
(
n
n
)
x
+
(
n
2
)
xn−2
1∑
i=1
yi +
(
n
3
)
xn−3
2∑
i=1
yi +
(
n
4
)
xn−4
3∑
i=1
yi + ...+
(
n
n−1
)
x
n−2∑
i=1
yi
+
n−1∑
i=1
yi
Indução Matemática em n:
n = 1, x2 (x+ 1)0 =
(
1
0
)
x2 +
((
1
1
)
− 1
)
x1 ⇔ x2 = x2
Hipótese de Indução
x2 (x+ 1)n−1 +
n−1∑
i=1
(x+ y)i (x+ 1)n−1−i =
(
n
0
)
xn+1 +
((
n
1
)
− 1
)
xn +
(
n
2
)
xn−1+
...+
(
n
n
)
x+
(
n
2
)
xn−2
1∑
i=1
yi +
(
n
3
)
xn−3
2∑
i=1
yi +
(
n
4
)
xn−4
3∑
i=1
yi+
...+
(
n
n− 1
)
x
n−2∑
i=1
yi +
n−1∑
i=1
yi
4.9 Polinómio de Tutte 49
Tese de Indução
x2 (x+ 1)n +
n∑
i=1
(x+ y)i (x+ 1)n−i =
(
n+ 1
0
)
xn+2 +
((
n+ 1
1
)
− 1
)
xn+1+
(
n+ 1
2
)
xn + ...+
(
n+ 1
n+ 1
)
x+
(
n+ 1
2
)
xn−1
1∑
i=1
yi +
(
n+ 1
3
)
xn−2
2∑
i=1
yi+
...+
(
n+ 1
n
)
x
n−1∑
i=1
yi +
n∑
i=1
yi
Demonstração
x2 (x+ 1)n +
n∑
i=1
(x+ y)i (x+ 1)n−i = x2 (x+ 1)n︸ ︷︷ ︸
(x+1)n−1(x+1)
+
n−1∑
i=1
(x+ y)i (x+ 1)n−i+
n∑
i=n
(x+ y)i (x+ 1)n−i
=x2 (x+ 1)n−1 (x+ 1) +
n−1∑
i=1
(x+ y)i (x+ 1)n−i︸ ︷︷ ︸
(x+1)n−1−i(x+1)
+ (x+ y)n︸ ︷︷ ︸
n∑
k=0
(nk)xkyn−k
=x2 (x+ 1)n−1 (x+ 1) + (x+ 1)
n−1∑
i=1
(x+ y)i (x+ 1)n−1−i +
n∑
k=0
(
n
k
)
xkyn−k
= (x+ 1)
x2 (x+ 1)n−1 +
n−1∑
i=1
(x+ y)i (x+ 1)n−1−i︸ ︷︷ ︸
Hipótese de Indução
+
n∑
k=0
(
n
k
)
xkyn−k
=(x+ 1)

(
n
0
)
xn+1 +
((
n
1
)− 1)xn + (n
2
)
xn−1 + ...+
(
n
n
)
x+
(
n
2
)
xn−2
1∑
i=1
yi+(
n
3
)
xn−3
2∑
i=1
yi + ...+
(
n
n−1
)
x
n−2∑
i=1
yi +
n−1∑
i=1
yi
+
n∑
k=0
(
n
k
)
xkyn−k
50 Grafos
=
(
n
0
)
︸︷︷︸
(n+10 )
xn+2 +
((
n
1
)
− 1
)
xn+1 +
(
n
2
)
xn + ...+
(
n
n
)
x2 +
(
n
2
)
xn−1
1∑
i=1
yi+
(
n
3
)
xn−2
2∑
i=1
yi + ...+
(
n
n− 1
)
x2
n−2∑
i=1
yi + x
n−1∑
i=1
yi +
(
n
0
)
xn+1+
((
n
1
)
− 1
)
xn +
(
n
2
)
xn−1 + ...+
(
n
n
)
︸︷︷︸
(n+1n+1)
x+
(
n
2
)
xn−2
1∑
i=1
yi +
(
n
3
)
xn−3
2∑
i=1
yi+
...+
(
n
n− 1
)
x
n−2∑
i=1
yi +
n−1∑
i=1
yi +
n∑
k=0
(
n
k
)
xkyn−k
=
(
n+ 1
0
)
xn+2 +
(
n
1
)
xn+1︸ ︷︷ ︸
∗
−xn+1︸︷︷︸
∗
+
(
n
2
)
xn︸ ︷︷ ︸
∗∗
+...+
(
n
n
)
︸︷︷︸
(n+1n+1)
x2 +
(
n
2
)
xn−1
1∑
i=1
yi+
(
n
3
)
xn−2
2∑
i=1
yi + ...+
(
n
n− 1
)
x2
n−2∑
i=1
yi + x
n−1∑
i=1
yi +
(
n
0
)
xn+1︸ ︷︷ ︸
∗
+
(
n
1
)
xn︸ ︷︷ ︸
∗∗
−xn+
(
n
2
)
xn−1 + ...+
(
n+ 1
n+ 1
)
x+
(
n
2
)
xn−2
1∑
i=1
yi +
(
n
3
)
xn−3
2∑
i=1
yi+
...+
(
n
n− 1
)
x
n−2∑
i=1
yi +
n−1∑
i=1
yi +
n∑
k=0
(
n
k
)
xkyn−k
=
(
n+ 1
0
)
xn+2 +

∗︷ ︸︸ ︷(
n
1
)
+
(
n
0
)
︸ ︷︷ ︸
(n+11 )
−1
xn+1 +

∗∗︷ ︸︸ ︷(
n
2
)
+
(
n
1
)
︸ ︷︷ ︸
(n+12 )
xn+
. . .+
(
n+ 1
n+ 1
)
x2 +
(
n
2
)
xn−1y +
(
n
3
)
xn−2
(
y + y2
)
+
. . .+
(
n
n− 1
)
x2
n−2∑
i=1
yi + x
n−1∑
i=1
yi − xn +
(
n
2
)
xn−1+
...+
(
n+ 1
n+ 1
)
x+
(
n
2
)
xn−2
1∑
i=1
yi +
(
n
3
)
xn−3
2∑
i=1
yi+
...+
(
n
n− 1
)
x
n−2∑
i=1
yi +
n−1∑
i=1
yi +
(
n
0
)
yn +
(
n
1
)
xyn−1 +
(
n
2
)
x2yn−2 + ...+
(
n
n
)
xn
4.9 Polinómio de Tutte 51
=
(
n+ 1
0
)
xn+2 +
((
n+ 1
1
)
− 1
)
xn+1 +
(
n+ 1
2
)
xn + . . .+
(
n+ 1
n+ 1
)
x+(
n+ 1
2
)
xn−1
1∑
i=1
yi +
(
n+ 1
3
)
xn−2
2∑
i=1
yi + . . .+
(
n+ 1
n
)
x
n−1∑
i=1
yi +
n∑
i=1
yi
A partir da demonstração, constata-se a igualdade das expressões seguintes:
Tn (x, y) = x
2(x+ 1)n−1 +
n−1∑
i=1
(x+ y)i(x+ 1)n−1−i
Tn (x, y) =

(
n
0
)
xn+1 +
((
n
1
)− 1)xn + (n
2
)
xn−1 + ...+
(
n
n
)
x
+
(
n
2
)
xn−2
1∑
i=1
yi +
(
n
3
)
xn−3
2∑
i=1
yi +
(
n
4
)
xn−4
3∑
i=1
yi + ...+
(
n
n−1
)
x
n−2∑
i=1
yi
+
n−1∑
i=1
yi
Estas fórmulas levaram-nos à construção de um novo triângulo, que passamos a
descrever. Calculamos os polinómios de Tutte Tn(x, y) de grafos bipartidos comple-
tos, com 2 ≤ n ≤ 9, e organizamos em três níveis, ou seja, em primeiro lugar os
termos em x, em segundo lugar os termos em xy e por fim, os termos em y.
Exemplo 4.9.1. Vamos exemplificar as duas fórmulas, nos casos em que n = 3 e
n = 4.
Para
∗︷ ︸︸ ︷
n = 3:
x2 (x+ 1)2 +
2∑
i=1
(x+ y)i (x+ 1)2−i =
(
3
0
)
x4 +
((
3
1
)
− 1
)
x3 +
(
3
2
)
x2+
(
3
3
)
x+
(
3
2
)
x
1∑
i=1
yi︸ ︷︷ ︸
y
+
2∑
i=1
yi︸ ︷︷ ︸
y+y2
=
(
3
0
)
︸︷︷︸
1
x4 +
(31
)
︸︷︷︸
3
−1
x3 + (32
)
︸︷︷︸
3
x2 +
(
3
3
)
︸︷︷︸
1
x+
(
3
2
)
︸︷︷︸
3
xy + y + y2
=x4 + 2x3 + 3x2 + x+ 3xy + y + y2
52 Grafos
Para n = 4:
x2 (x+ 1)3 +
3∑
i=1
(x+ y)i (x+ 1)3−i =
(
4
0
)
x5 +
((
4
1
)
− 1
)
x4 +
(
4
2
)
x3+
(
4
3
)
x2 +
(
4
4
)
x+
(
4
2
)
x2
1∑
i=1
yi︸ ︷︷ ︸
y
+
(
4
3
)
x
2∑
i=1
yi︸ ︷︷ ︸
y+y2
+
3∑
i=1
yi︸ ︷︷ ︸
y+y2+y3
Por seu lado, temos
x2 (x+ 1)3 +
3∑
i=1
(x+ y)i (x+ 1)3−i = x2 (x+ 1)3︸ ︷︷ ︸
(x+1)2(x+1)
+
2∑
i=1
(x+ y)i (x+ 1)3−i+
3∑
i=3
(x+ y)i (x+ 1)3−i
=x2 (x+ 1)2 (x+ 1) +
2∑
i=1
(x+ y)i (x+ 1)3−i︸ ︷︷ ︸
(x+1)2−i(x+1)
+ (x+ y)3︸ ︷︷ ︸
3∑
k=0
(3k)xky3−k
=x2 (x+ 1)2 (x+ 1) + (x+ 1)
2∑
i=1
(x+ y)i (x+ 1)2−i +
3∑
k=0
(
3
k
)
xky3−k
= (x+ 1)
(
x2 (x+ 1)2 +
2∑
i=1
(x+ y)i (x+ 1)2−i
)
+
3∑
k=0
(
3
k
)
xky3−k
∗︷︸︸︷
= (x+ 1)
((
3
0
)
x4 +
((
3
1
)
− 1
)
x3 +
(
3
2
)
x2 +
(
3
3
)
x+
(
3
2
)
x
1∑
i=1
yi +
2∑
i=1
yi
)
+
3∑
k=0
(
3
k
)
xky3−k
=
(
3
0
)
︸︷︷︸
(40)
x5 +
((
3
1
)
− 1
)
x4 +
(
3
2
)
x3 +
(
3
3
)
x2 +
(
3
2
)
x2
1∑
i=1
yi + x
2∑
i=1
yi +
(
3
0
)
x4+
((
3
1
)
− 1
)
x3 +
(
3
2
)
x2 +
(
3
3
)
x+
(
3
2
)
x
1∑
i=1
yi︸ ︷︷ ︸
y
+
2∑
i=1
yi︸ ︷︷ ︸
y+y2
+
3∑
k=0
(
3
k
)
xky3−k︸ ︷︷ ︸
(30)y3+(
3
1)xy2+(
3
2)x2y+(
3
3)x3
4.9 Polinómio de Tutte 53
=
(
4
0
)
x5 +
(
3
1
)
x4︸ ︷︷ ︸
∗
− x4︸︷︷︸
∗
+
(
3
2
)
x3︸ ︷︷ ︸
∗∗
+
(
3
3
)
x2︸ ︷︷ ︸
∗∗∗
+
(
3
2
)
︸︷︷︸
3
x2y + xy + xy2 +
(
3
0
)
x4︸ ︷︷ ︸
∗
+
(
3
1
)
x3︸ ︷︷ ︸
∗∗
−x3 +
(
3
2
)
x2︸ ︷︷ ︸
∗∗∗
+
(
3
3
)
︸︷︷︸
(44)
x+
(
3
2
)
︸︷︷︸
3
xy + y + y2 +
(
3
0
)
y3 +
(
3
1
)
︸︷︷︸
3
xy2+
(
3
2
)
︸︷︷︸
3
x2y +
(
3
3
)
︸︷︷︸
1
x3
=
(
4
0
)
x5 +

∗︷ ︸︸ ︷(
3
1
)
+
(
3
0
)
︸ ︷︷ ︸− 1
(41)
x4 +

∗∗︷ ︸︸ ︷(
3
2
)
+
(
3
1
)
︸ ︷︷ ︸
(42)
x3 +

∗∗∗︷ ︸︸ ︷(
3
3
)
+
(
3
2
)
︸ ︷︷ ︸
(43)
x2+
(
4
4
)
x+ 6x2y + 4xy2 + 4xy + y + y2 + y3
=
(
4
0
)
︸︷︷︸
1
x5 +
(41
)
︸︷︷︸
4
−1
x4 + (42
)
︸︷︷︸
6
x3 +
(
4
3
)
︸︷︷︸
4
x2 +
(
4
4
)
︸︷︷︸
1
x+ 6x2y + 4xy2 + 4xy+
y + y2 + y3
=x5 + 3x4 + 6x3 + 4x2 + x+ 6x2y + 4xy2 + 4xy + y + y2 + y3
Os polinómios de Tutte para grafos bipartidos completos, com n ∈ N e 2 ≤ n ≤ 9
são dados por:
T2 (x, y) = x
2 (x+ 1)1 +
1∑
i=1
(x+ y)i (x+ 1)1−i =
{
x3 + x2 + x
y
T3(x, y) = x
2(x+ 1)2 +
2∑
i=1
(x+ y)i(x+ 1)2−i =

x4 + 2x
3
+ 3x2 + x
3xy
y2 + y
T4(x, y) = x
2(x+ 1)3 +
3∑
i=1
(x+ y)i(x+ 1)3−i =

x5 + 3x
4
+ 6x
3
+ 4x2 + x
6x2y + 4xy2 + 4xy
y3 + y
2
+ y
54 Grafos
T5 (x, y) = x
2 (x+ 1)4 +
4∑
i=1
(x+ y)i (x+ 1)4−i =

x6 + 4x
5
+ 10x
4
+ 10x
3
+ 5x2 + x
10x3y + 10x2y 2 + 10x2y + 5xy3
+ 5xy2 + 5xy
y4 + y
3
+ y
2
+ y
T6 (x, y) = x
2 (x+ 1)5 +
5∑
i=1
(x+ y)i (x+ 1)5−i =

x7 + 5x6 + 15x5 + 20x4 + 15x3
+6x2 + x
15x4y + 20x3y 2 + 20x3y
+15x2y3 + 15x2y2 + 15x2y
+6xy4 + 6xy3 + 6xy2 + 6xy
y5 + y4 + y
3
+ y
2
+ y
T7 (x, y) = x
2 (x+ 1)6 +
6∑
i=1
(x+ y)i (x+ 1)6−i =

x8 + 6x7 + 21x6 + 35x5 + 35x4
+21x3 + 7x2 + x
21x5y + 35x4y2 + 35x4y + 35x3y3
+35x3y2 + 35x3y + 21x2y4
+21x2y3 + 21x2y2 + 21x2y + 6xy4
+6xy4 + 6xy3 + 6xy2 + 6xy
y6 + y5 + y4 + y3 + y2 + y
T8 (x, y) = x
2 (x+ 1)7 +
7∑
i=1
(x+ y)i (x+ 1)7−i =

x9 + 7x
8
+ 28x7 + 56x6 + 70x5
+56x4 + 28x3 + 8x2 + x
28x6y + 56x5y2 + 56x5y + 70x4y3
+70x4y2 + 70x4y + 56x3y4 + 56x3y3
+56x3y2 + 56x3y + 28x2y5 + 28x2y4
+28x2y3 + 28x2y2 + 28x2y + 8xy6
+8xy5 + 8xy4 + 8xy3 + 8xy2 + 8xy
y7 + y6 + y5 + y4 + y
3
+ y
2
+ y
T9(x, y) = x
2(x+ 1)8 +
8∑
i=1
(x+ y)i(x+ 1)8−i =

x10 + 8x9 + 36x8 + 84x7 + 126x6
+126x5 + 84x4 + 36x3 + 9x2 + x
36x7y + 84x6y2 + 84x6y + 126x5y3
+126x5y2 + 126x5y + 126x4y4
+126x4y3 + 126x4y2 + 126x4y
+84x3y5 + 84x3y4 + 84x3y3 + 84x3y2
+84x3y + 36x2y6 + 36x2y5 + 36x2y4
+36x2y3 + 36x2y2 + 36x2y + 9xy7
+9xy6 + 9xy5 + 9xy4 + 9xy3 + 9xy2
+9xy
y8 + y7 + y6 + y5 + y4 + y3 + y2 + y
4.9 Polinómio de Tutte 55
Analisando os coeficientes dos termos em x do polinómio de Tutte de grafos bi-
partidos completos Kn,2, ou seja, os coeficientes dos polinómios:
T2(x, y)→ x3 + x2 + x
T3(x, y)→ x4 + 2x3 + 3x2 + x
T4(x, y)→ x5 + 3x4 + 6x3 + 4x2 + x
T5(x, y)→ x6 + 4x5 + 10x4 + 10x3 + 5x2 + x
...
observamos que seguem um determinado padrão dispostos em triângulo. Acrescen-
tando duas linhas para n = 0 e n = 1 (iguais às do triângulo de Pascal), encontramos
uma nova construção que designamos por triângulo de Tutte (ver Figura 4.42).
Figura 4.42: Triângulo de Tutte de grafos bipartidos
T0,0
T1,0 T1,1
T2,0 T2,1 T2,2
T3,0 T3,1 T3,2 T3,3
T4,0 T4,1 T4,2 T4,3 T4,4
T5,0 T5,1 T5,2 T5,3 T5,4 T5,5
...
Assim, analisando o triângulo de Tutte, conclui-se que a relação de recorrência
que define o triângulo de Tutte é a seguinte:
Tn,0 = Tn,n = T2,1 = 1 (cor amarela) n ≥ 0
Tn,1 = Tn−1,1 + 1 (cor laranja) n ≥ 3
Tn,2 = Tn−1,1 + Tn−1,2 + 1 (cor azul) n ≥ 3
Tn,k = Tn−1,k−1 + Tn−1,k (cor verde) n > k, n ≥ 4, k ≥ 3
56 Grafos
Exemplo 4.9.2. Para T9,5
T9,5 = T8,4 + T8,5
= T7,3 + T4,7 + T7,4 + T7,5
= T7,3 + 2T7,4 + T7,5
= T6,2 + T6,3 + 2(T6,3 + T6,4) + T6,4 + T6,5
= T6,2 + 3T6,3 + 3T6,4 + T6,5
= T5,1 + T5,2 + 1 + 3(T5,2 + T5,3) + 3(T5,3 + T5,4) + T5,4 + T5,5
= T5,1 + 4T5,2 + 6T5,3 + 4T5,4 + T5,5︸︷︷︸
1
+1
= T4,1 + 1 + 4(T4,1 + T4,2 + 1) + 6(T4,2 + T4,3) + 4(T4,3 + T4,4︸︷︷︸
1
) + 2
= 5T4,1 + 10T4,2 + 10T4,3 + 11
= 5(T3,1 + 1) + 10(T3,1 + T3,2 + 1) + 10(T3,2 + T3,3︸︷︷︸
1
) + 11
= 15T3,1 + 20T3,2 + 46
= 15(T2,1︸︷︷︸
1
+1) + 20(T2,1︸︷︷︸
1
+ T2,2︸︷︷︸
1
+1) + 46
= 30 + 60 + 36
= 126
A parte do triângulo de Tutte, que colorimos a verde,
Tn,k = Tn−1,k−1 + Tn−1,k, n > k, n ≥ 4, k ≥ 3
coincide com o triângulo de Pascal, isto é,
Tn,k = Tn−1,k−1 + Tn−1,k
=
(
n− 1
k − 1
)
+
(
n− 1
k
)
Verificamos ainda que os termos dos quadrados azuis, para n ≥ 4, são iguais à
soma de três parcelas, amarelo + laranja + azul,
Tn,2 = Tn−1,0︸ ︷︷ ︸
amarelo
+Tn−1,1︸ ︷︷ ︸
laranja
+Tn−1,2︸ ︷︷ ︸
azul
= 1 + Tn−1,1 + Tn−1,2, n ≥ 4
e percebemos que o triângulo de Tutte completo é semelhante ao triângulo de Pascal.
Capítulo 5
Triângulo DNG
O triângulo DNG representa a relação entre as três estruturas deste trabalho: os
Designs, os Números e os Grafos. Desta forma, o triângulo DNG é a utilização de um
determinado tipo de números para estabelecer pontes de ligação entre os designs e
os grafos, ou entre os grafos e os designs. Após algumas tentativas, umas não foram
completamente bem sucedidas (ver Anexos B, C, D e E). Este trabalho passou a
focar-se mais nos números Eulerianos (Secção 3.6), nos grafos completos (Definição
4.2.1), nos grafos bipartidos (Subsecção 4.2) e no polinómio de Tutte (Secção 4.9).
5.1 Grafos completos e BIBDs
Para estabelecer a ligação entre um grafo completo Kn = (V,E), com n ≥ 3, e
um (v, b, r, k, λ)−BIBD é necessário, em primeiro lugar, considerar que:
|X| = |V | = n = v → número de vértices, ou seja, o conjunto X corresponde aos
vértices do grafo;
|A| = |E| = n(n−1)
2
= b → número de arestas, ou seja, o conjunto A indica as
arestas do grafo;
deg(vi) = n− 1 = r → grau de cada vértice;
k = 2 pois cada aresta liga somente dois vértices. Assim, segundo a inequação
de Fisher (equação (2.3)), n > 2, pois 2 ≤ k < v ⇔ 2 < v;
λ = 1 pois cada par de vértices está ligado somente por uma aresta.
Para qualquer grafo completo Kn = (V,E) (Definição 4.2.1), com n ≥ 3, o seu
(v, b, r, k, λ)−BIBD correspondente é da forma
Kn →
(
n,
n(n− 1)
2
, n− 1, 2, 1
)
− BIBD (5.1)
Para garantir a existência de um BIBD temos que vr = bk (equação (2.1)) e que
57
58 Triângulo DNG
λ(v − 1) = r(k − 1) (equação (2.2)), então
r =
λ(v − 1)
k − 1 =
1(n− 1)
1
= n− 1 (5.2)
b =
vr
k
=
n(n− 1)
2
(5.3)
Analisemos os seguintes grafos completos Kn, com n ≥ 3 (Figuras 5.1 a 5.4), e
os seus BIBDs correspondentes.
Quando n = 3 (Figura 5.1), existem três vértices (v = 3), três arestas (b = 3), o
grau de cada vértice é dois (r = 2), cada uma das arestas liga somente dois vértices
(k = 2) e cada par de vértices é ligado somente por uma aresta (λ = 1).
(v, b, r, k, λ) = (3, 3, 2, 2, 1)
Figura 5.1: Grafo completo K3
Se n = 4 (ver Figura 5.2), existem quatro vértices (v = 4), seis arestas (b = 6), o
grau de cada vértice é três (r = 3), cada uma das arestas liga somente dois vértices
(k = 2) e cada par de vértices é ligado somente por uma aresta (λ = 1).
(v, b, r, k, λ) = (4, 6, 3, 2, 1)
Figura 5.2: Grafo completo K4
Para n = 5 (Figura 5.3), existem cinco vértices (v = 5), dez arestas (b = 10),
o grau de cada vértice é quatro (r = 4), cada uma das arestas liga somente dois
vértices (k = 2) e cada par de vértices é ligado somente por uma aresta (λ = 1).
(v, b, r, k, λ) = (5, 10, 4, 2, 1)
Figura 5.3: Grafo completo K5
5.1 Grafos completos e BIBDs 59
No caso de n = 6 (ver Figura 5.4), existem seis vértices (v = 6), quinze arestas
(b = 15), o grau de cada vértice é cinco (r = 5), cada uma das arestas liga somente
dois vértices (k = 2) e cada par de vértices é ligado somente por uma aresta (λ = 1).
(v, b, r, k, λ) = (6, 15, 5, 2, 1)
Figura 5.4: Grafo completo K6
Resumindo:
Tabela 5.1: BIBDs correspondentes aos grafos completos
n Kn v b r k λ
3 K3 → 3 3 2 2 1
4 K4 → 4 6 3 2 1
5 K5 → 5 10 4 2 1
6 K6 → 6 15 5 2 1
...
...
...
...
...
...
...
n Kn → n n(n−1)2 n− 1 2 1
Considerando a sequência dos valores de b,
b3 = 3
b4 = 6 = b3 + 3
b5 = 10 = b4 + 4
b6 = 15 = b5 + 5
...
obtemos a seguinte relação de recorrência:
b3 = 3
bn = bn−1 + n− 1, n > 3 → bn = n(n−1)2 , n ≥ 3
60 Triângulo DNG
Iremos provar esta relação de recorrência utilizando o princípio de Indução Ma-
temática (versão forte):
b3 = 3
bn = bn−1 + n− 1︸ ︷︷ ︸
(1)
, n > 3 → bn = n(n− 1)
2︸ ︷︷ ︸
(2)
, n ≥ 3
Hipótese de Indução: Verifica-se para b3 e b4 e ... e bn
Tese de Indução: Provar que: bn+1 = (n+1)n2
Demonstração
bn+1
(1)︷︸︸︷
= bn + n
(2)︷︸︸︷
=
n(n− 1)
2
+ n
=
n(n− 1) + 2n
2
=
n(n+ 1)
2
∴ bn =
n(n− 1)
2
, n ≥ 3
Em todos os exemplos verifica-se a seguinte relação entre os grafos completos Kn
e os BIBDs
Kn →
(
n,
n(n− 1)
2
, n− 1, 2, 1
)
5.1.1 Grafo Conexo, Euleriano, Hamiltoniano e Planar
Os grafos Kn são conexos, pois todos os seus vértices estão ligados entre si por
um caminho (ver Definição 4.2.8). No entanto, estes grafos só são Eulerianos quando
o grau de todos os seus vértices é par (ver Teorema 4.2.1). Como o grau de cada
vértice nestes grafos é (n−1), então os grafosKn Eulerianos são aqueles em que o nú-
mero de vértices é ímpar, ou seja, quando o elemento v do BIBD é um número ímpar.
Para verificar se os grafos Kn são Hamiltonianos (Subsecção 4.2.2) podemos
utilizar o Teorema de Dirac (ver Teorema 4.2.2) ou o de Ore (ver Teorema 4.2.3).
Através do Teorema de Dirac, para n ≥ 3, verifica-se que:
deg(v) ≥ n
2
⇔ n− 1 ≥ n
2
⇔ 2n− 2 ≥ n⇔ n ≥ 2
Através do Teorema de Ore, para n ≥ 3, verifica-se que:
deg(v) + deg(u) ≥ n⇔ (n− 1) + (n− 1) ≥ n⇔ 2n− 2 ≥ n⇔ n ≥ 2
5.1 Grafos completos e BIBDs 61
Em ambos os teoremas verifica-se que os grafos Kn são Hamiltonianos quando
n ≥ 3 e para qualquer i, deg(vi) = n− 1, com vi ∈ V e Kn = (V,E).
Como os grafos Kn são simples e conexos, a inequação |E| ≤ 3 |V |−6 (ver (4.4))
pode ser utilizada para verificar se o grafo é ou não planar (Corolário 4.2.4.1).
|E| ≤ 3 |V | − 6⇔ n(n− 1)
2
≤ 3n− 6⇔ n(n− 1) ≤ 6n− 12⇔ n2 − 7n+ 12 ≤ 0
⇔ n ≤ 4 ∧ n ≥ 3⇔ 3 ≤ n ≤ 4
Como 3 ≤ n ≤ 4 e n ∈ N, então os grafos Kn são planares para n = 3 e n = 4.
Desta forma, sabendo que os grafos K3 e K4 são conexos e planares, usando a
fórmula de Euler (4.3), é possível calcular o número de faces destes grafos e por (4.2)
pode-se calcular a soma do grau de cada uma das faces.
Exemplo 5.1.1. Para K3:
Figura 5.5: Grafo K3
Analisando o grafo da Figura 5.5, sabe-se que |V | = 3 e |E| = 3, ou seja,
|V | − |E|+ |f | = 2⇔ 3− 3 + |f | = 2⇔ |f | = 2, donde, temos duas faces: f1 e f2.
Desta forma, sabendo que deg(f1) = deg(f2) (Definição 4.2.12), os graus de cada
uma das faces são os seguintes
m∑
i=1
deg(fi) = 2 |E| ⇔
2∑
i=1
deg(fi) = 2× 3⇔
2∑
i=1
deg(fi) = 6
⇔ deg(f1) = deg(f2) = 3
Como os graus das duas faces do grafo K3 são maiores ou iguais a três e o grau
dos vértices é menor do que três então, pela Definição 4.2.13, considera-se que o
grafo K3 não é poliédrico.
Para K4:
Figura 5.6: Grafo K4
62 Triângulo DNG
Analisando o grafo da Figura 5.6, sabe-se que |V | = 4 e |E| = 6, ou seja,
|V | − |E|+ |f | = 2⇔ 4− 6 + |f | = 2⇔ −2 + |f | = 2⇔ |f | = 4, logo,
o grafo K4 tem 4 faces: f1, f2, f3 e f4.
Desta forma, sabendo que deg(f1) = deg(f2) = deg(f3) = deg(f4) (Definição
4.2.12), os graus de cada uma das faces são os seguintes:
m∑
i=1
deg(fi) = 2 |E| ⇔
4∑
i=1
deg(fi) = 2× 6⇔
4∑
i=1
deg(fi) = 12
⇔ deg(f1) + deg(f2) + deg(f3) + deg(f4) = 12⇔ 4deg(f1) = 12
⇔ deg(f1) = deg(f2) = deg(f3) = deg(f4) = 3
Como os graus das quatro faces do grafo K4 são maiores ou iguais a três e o
grau de todos os vértices é igual a três então, pela Definição 4.2.13, o grafo K4 é
poliédrico.
5.1.2 Matrizes de incidência e de adjacência
Na matriz de incidência (Secção 4.3) dos grafos Kn a soma de cada linha é igual
a n− 1, pois este é o grau de todos os vértices. Como o elemento k = 2 (cada aresta
liga só dois vértices), então a soma de cada coluna da matriz de incidência dos grafos
Kn é igual a dois.
Figura 5.7: Matriz de incidência dos grafos Kn
Na matriz de adjacência (Secção 4.4), como todos os vértices estão ligados entre
si e não existem loops, a diagonal da matriz de adjacência dos grafos Kn é igual a
zero e os restantes elementos iguais a um.
Figura 5.8: Matriz de adjacência dos grafos Kn
5.1 Grafos completos e BIBDs 63
5.1.3 Bloco Complementar
Sabendo que o bloco complementar de um (v, b, r, k, λ)−BIBD, com k ≤ v − 2,
é da forma (v, b, b− r, v − k, b− 2r + λ)−BIBD (ver Teorema 2.2.1), então o bloco
complementar de um (n, n(n−1)
2
, n− 1, 2, 1)−BIBD de um grafo Kn é da forma
(n,
n(n− 1)
2
,
n(n− 1)
2
− (n− 1), n− 2, n(n− 1)
2
− 2(n− 1) + 1)− BIBD (5.4)
Assim:
(
n,
n(n− 1)
2
, n− 1, 2, 1
)
→
(
n,
n(n− 1)
2
,
(n− 2)(n− 1)
2
, n− 2, (n− 4)(n− 1) + 2
2
)
Como o bloco complementar só existe se k ≤ v − 2 e dado que k = 2 vem
2 ≤ n − 2 ⇔ n ≥ 4, ou seja, apenas os grafos Kn com n ≥ 4 poderão ter blocos
complementares. Por outro lado, tendo em conta (5.4), só poderá ser n = 4.
Conclui-se então que só o grafo completo K4 é que tem associado um BIBD
complementar.
5.1.4 Matching Perfeito
Nos grafos Kn, com n ≥ 4, existe matching perfeito M (Secção 4.5) quando o
número de vértices é par, pois |M | = n
2
.
Exemplo 5.1.2. Considerando os grafos K4 e K5, temos que:
Figura 5.9: Matching perfeito do grafo K4
Para K4 existe um matching perfeito M (ver Figura 5.9), pois M satura todos
os vértices uma vez que M = {12, 34}.
No exemplo da Figura 5.10 confirmamos que em K5 não existe matching perfeito
(note-se que n = 5 = |V | é ímpar).
Figura 5.10: Matching perfeito do grafo K5
64 Triângulo DNG
5.1.5 Árvore Geradora
Através do Teorema de Cayley (ver Teorema 4.6.1) sabe-se que o número de
árvores geradoras de um grafo Kn, com n ≥ 3 é igual a r(Kn) = nn−2.
O Teorema de Cayley pode ser obtido através do Teorema 4.6.2 da árvore-matriz,
da forma que se segue.
Consideremos o caso particular de n = 4, ou seja, K4 (ver Figura 5.11):
Figura 5.11: Grafo completo K4
A matriz de adjacência é a seguinte:
Figura 5.12: Matriz de adjacência do grafo completo K4
A matriz S é a seguinte:
Figura 5.13: Matriz S do grafo completo K4
Assim, subtraindo a matriz AK4 à matriz S, calcula-se a seguinte matriz Q:
Q = S − AK4 =

(n− 1) −1 −1 −1
−1 (n− 1) −1 −1
−1 −1 (n− 1) −1
−1 −1 −1 (n− 1)

Se considerarmos i = 4, então serão retiradas a quarta linha e a quarta coluna,
para depois ser calculado o determinante da matriz resultante.
5.1 Grafos completos e BIBDs 65
T (K4) =
∣∣∣∣∣∣
(n− 1) −1 −1
−1 (n− 1) −1
−1 −1 (n− 1)
∣∣∣∣∣∣ = (n− 1)
∣∣∣∣(n− 1) −1−1 (n− 1)
∣∣∣∣
+1
∣∣∣∣−1 −1−1 (n− 1)
∣∣∣∣− 1 ∣∣∣∣−1 (n− 1)−1 −1
∣∣∣∣ = n3 − 3n2 = n2(n− 3)
Como n = 4, então 2 = n− 2 e 3 = n− 1, logo
n2(n − 3) = nn−2(n − (n − 1)) = nn−2(n − n + 1) = nn−2 = r(Kn), tal como
indica o Teorema de Cayley.
5.1.6 Digrafos
Nesta secção vamos considerar os digrafos completos, logo o correspondente BIBD
será (n, n(n−1)
2
, n− 1, 2, 1), onde r é a soma dos graus de entrada e saída.
Sabendo que um digrafo é um grafo orientado (ver Definição 4.8) e considerando a
orientação das setas do menor número para o maior, então para o (4, 6, 3, 2, 1)−BIBD,
o correspondente digrafo é representado como podemos ver na Figura 5.14.
Figura 5.14: Digrafo de um (4, 6, 3, 2, 1)−BIBD
Ao analisar este digrafo percebe-se que um dos vértices só tem saídas e outro
vértice só tem entradas (ver Tabela 5.2).
Tabela 5.2: Graus de entrada e de saída de cada um dos vértices
Vértices 1 2 3 4
Grau de entrada 0 1 2 3
Grau de saída 3 2 1 0
Assim, é possível concluir que, para o
(
n, n(n−1)
2
, n− 1, 2, 1
)
− BIBD, os graus
de entrada e de saída dos vértices são da forma indicada na Tabela 5.3:
66 Triângulo DNG
Tabela 5.3: Graus de entrada e de saída de cada um dos vértices de um digrafo
completo
Vértices 1 2 ... n
Grau de entrada n− n = 0 n− (n− 1) = 1 ... n− 1
Grau de saída n− 1 n− 2 ... n− n = 0
5.2 Grafos especiais e BIBDs
Num grafo caminho, cíclico ou roda existe um BIBD correspondente apenas nos
seguintes casos:
Para o grafo caminho P2 (ver Definição 4.2.5), o BIBD correspondente será igual
ao BIBD do grafo completo K2, ou seja, P2 → (2, 1, 1, 2, 1).
Para o grafo cíclico C3 (ver Definição 4.2.2), o BIBD correspondente será igual
ao BIBD do grafo completo K3, ou seja, C3 → (3, 3, 3, 2, 1).
Para o grafo roda W4 (ver Definição 4.2.3), o BIBD correspondente será igual ao
BIBD do grafo completo K4, ou seja, W4 → (4, 6, 3, 2, 1).
5.3 Multigrafos e BIBDs
A construção de um multigrafo completo a partir de um BIBD faz-se de forma
análoga à exposta no início deste Capítulo, para os grafos completosKn. No entanto,
como se trata de um multigrafo completo, os pares de vértices podem estar ligados
por duas ou mais arestas (ver Definição 4.1.2), o que significa que o parâmetro λ
do BIBD pode ser qualquer número natural maior do que um. Note-se que k = 2
porque cada aresta liga somente dois vértices.
Sabemos que se um (v, b, r, k, λ)−BIBD existe, então vr = bk (equação (2.1)) e
λ(v − 1) = r(k − 1) (equação (2.2)).
Temos:
r =
λ(v − 1)
k − 1 =
λ(n− 1)
1
= λ(n− 1), logo
b =
vr
k
=
nλ(n− 1)
2
Obtém-se (n, nλ(n−1)
2
, λ(n− 1), 2, λ)−BIBD.
Se cada par de vértices estiver ligado por duas arestas, ou seja, λ = 2, então
(n, n(n− 1), 2(n− 1), 2, 2)− BIBD (5.5)
5.4 Grafos completos e BIBDs simétricos 67
Exemplo 5.3.1. Para v = 4 = n e λ = 2 obtemos o seguinte multigrafo (ver Figura
5.15).
Figura 5.15: Multigrafo do (4, 12, 6, 2, 2)−BIBD
No caso de v = 4 = n e de λ = 3, o multigrafo que se obtém é:(
n,
3n(n− 1)
2
, 3(n− 1), 2, 3
)
− BIBD
Figura 5.16: Multigrafo do (4, 18, 9, 2, 3)−BIBD
5.4 Grafos completos e BIBDs simétricos
Para um BIBD ser simétrico, é necessário que v = b (ou r = k) (ver Definição
2.1.3). Sabendo que para ser possível a construção de um grafo completo a partir
de um BIBD, este terá de ser da forma
(
n, nλ(n−1)
2
, λ(n− 1), 2, λ
)
, então:
v = b ou r = k
⇔ n = nλ(n−1)
2
⇔ 2n = nλ(n− 1)
⇔ 2 = λ(n− 1)
⇔ λ = 2
n−1
Tem-se λ = 2
n−1 e λ ∈ N, então n = 2 ∨ n = 3. Como v > 2⇒ v = 3 = n.
λ = 2
3−1 = 1
68 Triângulo DNG
b = 3×1(3−1)
2
= 3 = v
r = 1(3− 1) = 2 = k
Assim, um BIBD simétrico de um grafo, com n = 3, é da forma (3, 3, 2, 2, 1), ou
seja, é o mesmo BIBD associado ao grafo completo K3 (Figura 5.17).
Figura 5.17: Grafo do BIBD simétrico (3, 3, 2, 2, 1)
5.5 Números Eulerianos e BIBDs
Tal como foi visto anteriormente, na fórmula (3.6),
E (n, k) =
k∑
j=0
(−1)j
(
n+ 1
j
)
(k + 1− j)n, n > k, n ∈ N, k ∈ N0
Utilizaremos k = λ; esta escolha prende-se com a ligação entre E(n, λ) e os
BIBDs, que iremos abordar.
E (n, λ) =
λ∑
j=0
(−1)j
(
n+ 1
j
)
(λ+ 1− j)n
Para λ = 1:
E (n, 1) =
1∑
j=0
(−1)j
(
n+ 1
j
)
(1 + 1− j)n
= (−1)0
(
n+ 1
0
)
(2− 0)n + (−1)1
(
n+ 1
1
)
(2− 1)n
=
(
n+ 1
0
)
︸ ︷︷ ︸
1
2n −
(
n+ 1
1
)
︸ ︷︷ ︸
n+1
1n
= 2n − (n+ 1)
Assim
E (n, 1) = 2n − (n+ 1)→
(
n,
n2 − n
2
, n− 1, 2, 1
)
− BIBD (5.6)
Para cada n o BIBD resultante de E(n, 1) (ver Tabela 5.4) é o mesmo BIBD
resultante dos grafos completos Kn (ver expressão (5.1)). A Figura 5.2 é do grafo
completo particular K4.
5.5 Números Eulerianos e BIBDs 69
Tabela 5.4: BIBD resultante de E(n, 1)
E(n, λ) v b r k λ Kn
E(3, 1) = 4 3 3 2 2 1 K3
E(4, 1) = 11 4 6 3 2 1 K4
E(5, 1) = 26 5 10 4 2 1 K5
E(6, 1) = 57 6 15 5 2 1 K6
E(7, 1) = 120 7 21 6 2 1 K7
E(8, 1) = 247 8 28 7 2 1 K8
...
...
...
...
...
...
...
E(n, 1) = 2n − (n+ 1) n n2−n
2
n− 1 2 1 Kn, n ≥ 3
Para λ = 2:
E (n, 2) =
2∑
j=0
(−1)j
(
n+ 1
j
)
(2 + 1− j)n
= (−1)0
(
n+ 1
0
)
(3− 0)n + (−1)1
(
n+ 1
1
)
(3− 1)n + (−1)2
(
n+ 1
2
)
(3− 2)n
=
(
n+ 1
0
)
3n −
(
n+ 1
1
)
2n +
(
n+ 1
2
)
1n
= 3n − (n+ 1)2n + (n+ 1)n
2
= 3n − 2n(n+ 1) + n
2 + n
2
Assim
E (n, 2) = 3n − (n+ 1)2n + (n+ 1)n
2
→ (n, n(n− 1), 2(n− 1), 2, 2)− BIBD (5.7)
Para cada n, este BIBD, resultante de E(n, 2) (ver Tabela 5.5), é o mesmo BIBD
resultante do grafo completo com arestas duplas, exemplificado na Figura 5.15, para
n = 4, através da expressão (5.5).
Tabela 5.5: BIBD resultante de E(n, 2)
E(n, λ) v b r k λ Kn
E(3, 2) = 11 3 6 4 2 2 2K3
E(4, 2) = 11 4 12 6 2 2 2K4
E(5, 2) = 66 5 20 8 2 2 2K5
E(6, 2) = 302 6 30 10 2 2 2K6
E(7, 2) = 1191 7 42 12 2 2 2K7
E(8, 2) = 4293 8 56 14 2 2 2K8
...
...
...
...
...
...
...
E(n, 2) = 3n − 2n(n+ 1) + n2+n
2
n n2 − n 2(n− 1) 2 2 2Kn, n ≥ 3
70 Triângulo DNG
Para λ = 3:
E (n, 3) =
3∑
j=0
(−1)j
(
n+ 1
j
)
(3 + 1− j)n
= (−1)0
(
n+ 1
0
)
(4− 0)n + (−1)1
(
n+ 1
1
)
(4− 1)n + (−1)2
(
n+ 1
2
)
(4− 2)n+
(−1)3
(
n+ 1
3
)
(4− 3)n
=
(
n+ 1
0
)
4n −
(
n+ 1
1
)
3n +
(
n+ 1
2
)
2n −
(
n+ 1
3
)
1n
= 4n − 3n(n+ 1) + 2n
(
n+ 1
2
)
−
(
n+ 1
3
)
= 4n − 3n(n+ 1) + 2nn
2 + n
2
− n
3 − n
6
Assim
E (n, 3) =
1
6
n+22n+
1
2
2nn−3nn+1
2
2nn2−3n−1
6
n3 →
(
n,
3n(n− 1)
2
, 3(n− 1), 2, 3
)
(5.8)
Tabela 5.6: BIBD resultante de E(n, 3)
E(n, λ) v b r k λ Kn
E(4, 3) = 1 4 18 9 2 3 3K4
E(5, 3) = 26 5 30 12 2 3 3K5
E(6, 3) = 302 6 45 15 2 3 3K6
E(7, 3) = 2416 7 63 18 2 3 3K7
E(8, 3) = 15619 8 84 21 2 3 3K8
E(9, 3) = 88234 9 108 24 2 3 3K9
...
...
...
...
...
...
...
E(n, 3) = 4n − 3n(n+ 1) + 2n n2+n
2
− n2−n
6
n 3n(n−1)
2
3(n− 1) 2 3 3Kn, n ≥ 3
Resumindo:
E (n, 1)→
(
n,
n(n− 1)
2
, n− 1, 2, 1
)
− BIBD
E (n, 2)→
(
n,
2n(n− 1)
2
, 2(n− 1), 2, 2
)
− BIBD
E (n, 3)→
(
n,
3n(n− 1)
2
, 3(n− 1), 2, 3
)
− BIBD
E (n, 4)→
(
n,
4n(n− 1)
2
, 4(n− 1), 2, 4
)
− BIBD
5.6 Polinómio de Tutte e BIBDs 71
...
E (n, λ)→
(
n,
λn(n− 1)
2
, λ(n− 1), 2, λ
)
, n ≥ 3 e λ < n (5.9)
r =
λ(v − 1)
k − 1 =
λ(n− 1)
1
= λ(n− 1)
b =
vr
k
=
nλ(n− 1)
2
Comprovar que
λn(n−1)
2 é sempre um número natural, é equivalente a provar
que:
λn2−λn
2 ∈ N, ∀n≥3∀λ<n ⇔ λn2 − λn é múltiplo de 2, ∀n≥3∀λ<n
∀n≥3, ∀λ<n,∃t∈N : λn2 − λn = 2t
Vamos fazer a demonstração recorrendo ao método de Indução Matemática:
Para n = 3 : λ32 − λ3 = 2t⇔ 6λ = 2t⇔ t = 3λ ∈ N
Hipótese de Indução: ∃t∈N: λn2 − λn = 2t
Tese de Indução: ∃s∈N: λ(n+ 1)2 − λ(n+ 1) = 2s
Demonstração
λ(n+ 1)2 − λ(n+ 1) = λn2 + 2λn+ λ− λn− λ
= λn2 − λn︸ ︷︷ ︸
H.I.
+2λn
= 2t+ 2λn
= 2(t+ λn)︸ ︷︷ ︸
∈N
, pois t, λ, n ∈ N
basta considerar s = t+ λn ∈ N e teremos o pretendido
∴ ∃t∈N : λn2 − λn = 2t
5.6 Polinómio de Tutte e BIBDs
Para estabelecer uma ligação entre o polinómio de Tutte de grafos bipartidos
completos (equação (4.11)), com n ≥ 3, e os BIBDs, vamos considerar que o número
de parcelas em x no polinómio de Tutte é equivalente ao valor v no BIBD, que o
número de parcelas em xy no polinómio de Tutte é equivalente ao valor λ no BIBD
e que o número de parcelas em y no polinómio de Tutte é equivalente ao valor k no
BIBD.
72 Triângulo DNG
De seguida, a partir dos valores de v, λ e k, calculámos os valores de b e r através
das equações (2.1) e (2.2).
Para chegarmos à fórmula exata de como passar de um polinómio de Tutte de
grafos bipartidos completos, com n ≥ 3, para um BIBD foi necessário descobrir os
BIBDs para os primeiros polinómios de Tutte de grafos bipartidos, com n ≥ 3, e
descobrir a relação entre eles:
Tn(x, y) =

v = n+ 1 = número de parcelas em x
k = n− 1 = número de parcelas em y
λ = (n−1)(n−2)
2
= número de parcelas em xy
,
Exemplo 5.6.1. Considera-se os polinómios de Tutte de grafos bipartidos, em que
3 ≤ n ≤ 6.
Para n = 3→ T3(x, y) =

x4 + 2x
3
+ 3x2 + x
3xy
y2 + y
,
temos

quatro termos em x, ou seja, v = 4
um termo em xy, ou seja, λ = 1
dois termos em y, ou seja, k = 2
Assim,
λ (v − 1) = r (k − 1)⇔ 1 (4− 1) = r (2− 1)⇔ r = 3
vr = bk ⇔ 4r = 2b⇔ 4×3
2
= b⇔ b = 6
Para n = 4→ T4(x, y) =

x5 + 3x
4
+ 6x
3
+ 4x2 + x
6x2y + 4xy2 + 4xy
y3 + y
2
+ y
,
temos

cinco termos em x, ou seja, v = 5
três termos em xy, ou seja, λ = 3
três termos em y, ou seja, k = 3
Assim,
λ (v − 1) = r (k − 1)⇔ 3 (5− 1) = r (3− 1)⇔ 3×4
2
= r ⇔ r = 6
vr = bk ⇔ 5r = 3b⇔ 5×6
3
= b⇔ b = 10
Para n = 5→ T5(x, y) =

x6 + 4x
5
+ 10x
4
+ 10x
3
+ 5x2 + x
10x3y + 10x2y 2 + 10x2y + 5xy3 + 5xy2 + 5xy
y4 + y
3
+ y
2
+ y
,
5.6 Polinómio de Tutte e BIBDs 73
temos

seis termos em x, ou seja, v = 6
seis termos em xy, ou seja, λ = 6
quatro termos em y, ou seja, k = 4
Assim,
λ (v − 1) = r (k − 1)⇔ 6 (6− 1) = r (4− 1)⇔ 6×5
3
= r ⇔ r = 10
vr = bk ⇔ 6r = 4b⇔ 6×10
4
= b⇔ b = 15
Para n = 6→ T6(x, y) =

x7 + 5x6 + 15x
5
+ 20x
4
+ 15x
3
+ 6x2 + x
15x4y + 20x3y 2 + 20x3y + 15x2y 3 + 15x2y 2+
15x2y + 6xy 4 + 6xy 3 + 6xy 2 + 6xy
y5 + y4 + y
3
+ y
2
+ y
,
temos

sete termos em x, ou seja, v = 7
dez termos em xy, ou seja, λ = 10
cinco termos em y, ou seja, k = 5
Assim,
λ (v − 1) = r (k − 1)⇔ 10 (7− 1) = r (5− 1)⇔ 10×6
4
= r ⇔ r = 15
vr = bk ⇔ 7r = 5b⇔ 7×15
5
= b⇔ b = 21
Vamos agora tentar obter uma fórmula recursiva para os valores de v, k, e λ.
74 Triângulo DNG
Considerando a sequência de λ, em que:
a3 = 1
a4 = 3 = a3 + 2
a5 = 6 = a4 + 3
a6 = 10 = a5 + 4
...
an = an−1 + n− 2, n ≥ 4
obtemos a relação de recorrência completa não homogénea com coeficientes cons-
tantes:
a3 = 1
an = an−1 + n− 2, n ≥ 4
Ao aplicarmos um dos métodos para resolver uma relação de recorrência não
homogénea com coeficientes constantes (Exemplo 3.5.2) temos:
Equação homogénea associada:
an − an−1 = 0
↓ an = λn
Equação característica:
⇔ λn − λn−1 = 0
⇔ λn−1(λ− 1) = 0
⇔ λ = 1
Assim,
ah = C1
n = C, C ∈ R
Solução particular:
ap = An
2 +Bn
↓ an − an−1 = n− 2
⇔ An2 +Bn− (A(n− 1)2 +B(n− 1)) = n− 2
⇔ An2 +Bn− An2 + 2An− A−Bn+B = n− 2
5.6 Polinómio de Tutte e BIBDs 75
⇔ 2An− A+B = n− 2
⇔
{
2A = 1
−A+B = −2
⇔
{
A = 1
2
B = −3
2
Assim,
ap =
1
2
n2 − 3
2
n
Como a3 = 1 (condição inicial), e
an = ah + ap ⇔ an = C + 1
2
n2 − 3
2
n
Então,
a3 = 1⇔ C + 12 × 32 − 32 × 3 = 1⇔ C = 1
an = 1 +
1
2
n2 − 3
2
n =
n2 − 3n+ 2
2
=
(n− 2)(n− 1)
2
Podemos provar isto, utilizando o princípio de Indução Matemática (versão
forte):
a3 = 1
an = an−1 + n− 2︸ ︷︷ ︸
(1)
, n ≥ 4 → an = (n− 2)(n− 1)
2︸ ︷︷ ︸
(2)
, n ≥ 3
Hipótese de Indução: Verifica-se para a3 e a4 e ... e an
Tese de Indução: Provar que an+1 = (n−1)n2
Demonstração
an+1
(1)︷︸︸︷
= an + n− 1
(2)︷︸︸︷
=
(n− 2)(n− 1)
2
+ n− 1
=
(n− 2)(n− 1) + 2(n− 1)
2
=
(n− 1)n
2
∴ λ = (n− 2)(n− 1)
2
, n ≥ 3
76 Triângulo DNG
Em resumo,
Tabela 5.7: Ligação entre o polinómio de Tutte de grafos bipartidos completos e os
BIBDs
termos em x b = vr
k
r = λ(v−1)
k−1 termos em y termos em xy
v b r k λ
T3 4 6 3 2 1
T4 5 10 6 3 3
T5 6 15 10 4 6
T6 7 21 15 5 10
...
...
...
...
...
...
Tn n+ 1 n− 1 (n−2)(n−1)2
Desta forma, podemos calcular os valores de b e de r
λ (v − 1) = r (k − 1)⇔ (n− 1)(n− 2)(n+ 1− 1)
2
= r(n− 1− 1)
⇔ n(n− 1)(n− 2)
2
= r(n− 2)⇔ r = n(n− 1)
2
(5.10)
vr = bk ⇔ (n+ 1)n(n− 1)
2
= b(n− 1)⇔ b = (n+ 1)n
2
(5.11)
Assim, para cada polinómio de Tutte Tn(x, y) de um grafo bipartido completo
Kn,2, com n ≥ 3, o (v, b, r, k, λ)−BIBD correspondente é da forma
Tn(x, y)→
(
n+ 1,
n(n+ 1)
2
,
n(n− 1)
2
, n− 1, (n− 1)(n− 2)
2
)
(5.12)
Capítulo 6
Aplicações
6.1 Problema do Carteiro Chinês
O problema do carteiro chinês consiste em determinar o percurso que um carteiro
faz numa determinada zona da cidade, em que começa e acaba no mesmo ponto,
passando uma única vez em cada uma das ruas. Para se construir um digrafo, a
partir do mapa dessa zona, considera-se que os arcos representam as ruas e os vér-
tices representam os cruzamentos. Assim, para que este percurso seja possível, é
necessário que o digrafo construído, a partir dessa zona da cidade, seja Euleriano.
Para relacionarmos os digrafos com os BIBDs, para este problema específico,
supusemos que:
• O digrafo em questão tem de ser completo, para existir um BIBD que seja da
forma
(v, b, r, k, λ)→
(
n,
n(n− 1)
2
, n− 1, 2, 1
)
tal como foi visto na expressão (5.1).
• Para existir um BIBD associado, o parâmetro r (que indica o grau de cada
vértice num grafo) no caso dos digrafos o seu valor será igual à soma dos graus
de entrada e de saída de cada um dos vértices, ou seja,
r = deg
E
vi + degSvi
• Para existir um circuito direto de Euler, temos que ter r par, o que implica
que
deg
E
vi = degSvi
logo n = r + 1 é um número ímpar. Assim, concluímos que existe circuito
direto de Euler somente quando n é um número ímpar.
• A existência de um ciclo de Hamilton depende da orientação dos arcos do
digrafo, ou seja, do número de graus de entrada e de saída de cada um dos
vértices.
77
78 Aplicações
• Se, por exemplo, um vértice do digrafo só tiver graus de entrada, e outro
vértice só tiver graus de saída, então nesse digrafo não existe circuito direto
de Euler, nem ciclo de Hamilton.
A Figura 6.1 representa um exemplo de um digrafo completo, com número
par de vértices, em que não existe ciclo de Hamilton. Isto acontece porque um
dos vértices só tem graus de entrada e outro só tem graus de saída (ver Tabela
6.1).
Figura 6.1: Digrafo sem ciclo de Hamilton
Tabela 6.1: Graus de entrada e de saída de cada um dos vértices do digrafo sem
ciclo de Hamilton
Vértices 1 2 3 4
Grau de entrada 3 0 1 2
Grau de saída 0 3 2 1
Desta forma, um digrafo possível para retratar o problema do carteiro chinês,
seria o seguinte:
Figura 6.2: Digrafo Euleriano e Hamiltoniano
Tabela 6.2: Graus de entrada e de saída de cada um dos vértices do digrafo Euleriano
e Hamiltoniano
Vértices 1 2 3 4 5
Grau de entrada 2 2 2 2 2
Grau de saída 2 2 2 2 2
r = deg
E
vi + degSvi 4 4 4 4 4
6.1 Problema do Carteiro Chinês 79
Assim, analisando o digrafo da Figura 6.2, conclui-se que um exemplo do cir-
cuito orientado de Euler, na zona de distribuição, é o circuito 1 − 2 − 3 − 4 − 5 −
1−3−5−2−4−1 e um exemplo de ciclo orientado de Hamilton é 1−2−3−4−5−1.
O BIBD associado a este digrafo é da forma (5, 10, 4, 2, 1).
Após estudarmos este exemplo e apesar de já sabermos que se v é par não existe
circuito orientado de Euler, achámos interessante investigar o que teríamos de acres-
centar ao digrafo para que fosse euleriano.
Ao escolhermos, por exemplo, um (6, 15, 5, 2, 1)−BIBD, é possível construir um
digrafo através deste BIBD, pois já sabemos que:
v = 6→ existem seis rotundas ou cruzamentos.
b = 15→ existem quinze estradas com sentidos únicos.
r = 5→ não é possível construir um circuito direto de Euler, pois r é um número
ímpar.
Assim, o digrafo construído a partir do (6, 15, 5, 2, 1)−BIBD, poderia ser como
se ilustra na Figura 6.3:
Figura 6.3: Digrafo associado ao (6, 15, 5, 2, 1)−BIBD
Tabela 6.3: Graus de entrada e de saída de cada vértice do digrafo associado ao
(6, 15, 5, 2, 1)−BIBD
Vértices 1 2 3 4 5 6
Grau de entrada 2 2 2 3 3 3
Grau de saída 3 3 3 2 2 2
r = deg
E
vi + degSvi 5 5 5 5 5 5
Apesar do circuito direto de Euler não ser possível neste digrafo, o ciclo de
Hamilton já o é, ou seja, existe um caminho que passa por todos os cruzamentos
uma única vez, voltando ao ponto de partida (ver Definição 4.2.10) e pode ser o
seguinte: 1− 2− 3− 4− 5− 6− 1.
80 Aplicações
Desta forma, para o circuito direto de Euler ser possível neste digrafo, é necessário
que os graus de entrada e de saída de cada um dos vértices sejam iguais e também
que a sua soma seja um número par. Assim, e analisando os graus de entrada e
de saída de cada um dos vértices (ver Tabela 6.3), reparámos que, para tornar o
digrafo euleriano bastaria acrescentar os arcos 41, 52 e 63 e passaríamos a ter um
multidigrafo. Desta forma, o digrafo teria um circuito direto de Euler, mas deixava
de estar associado a um BIBD, pois o número de arcos aumentaria para dezoito e
deixaria de ser quinze e o valor de λ não seria fixo.
Figura 6.4: Digrafo adaptado a Euleriano
Tabela 6.4: Graus de entrada e de saída do digrafo adaptado a Euleriano
Vértices 1 2 3 4 5 6
Grau de entrada 3 3 3 3 3 3
Grau de saída 3 3 3 3 3 3
r = deg
E
vi + degSvi 6 6 6 6 6 6
6.2 Ciências da Computação
Atualmente, devido ao avanço da internet e dos aparelhos eletrónicos, como os
smartphones e os tablets, as ligações entre os diferentes servidores são visíveis para
todos os utilizadores.
É percetível que quando pesquisamos um determinado produto num motor de
busca, como o Google, depois dessa pesquisa irá aparecer publicidade a esse produto
quando navegamos noutros sites. Por conseguinte, existe uma ligação evidente entre
o motor de busca em que pesquisamos o produto e outro site em que este produto
seja publicitado.
Exemplo 6.2.1. Imaginemos um utilizador que pretende comprar uma máquina
de lavar roupa. Para comparar os preços e as diferentes características, pesquisa no
Google por máquinas de lavar roupa e analisa as que são sugeridas.
Após esta pesquisa ao utilizar a rede social Facebook, nota que apareceu uma
publicação patrocinada de uma máquina de lavar roupa. Posteriormente, na rede
social Instagram o mesmo acontece. As várias publicações patrocinadas são de
6.2 Ciências da Computação 81
sites diferentes, relacionados com a venda de eletrodomésticos, como, por exemplo,
Rádio Popular, Worten e Conforama. Além de todas as publicações patrocinadas
serem de máquinas de lavar roupa, são todas com os preços mais competitivos de
cada loja, dentro do orçamento que o utilizador tinha pesquisado.
É percetível a existência de uma ligação óbvia entre todos estes sites, ou seja,
é possível construir um grafo que represente estas ligações entre os diferentes sites,
como o da Figura 6.5:
Figura 6.5: Grafo que relaciona os diferentes sites
Este grafo (Figura 6.5), que representa as ligações entre os diferentes sites, é um
grafo completo, pois todos os sites estão ligados entre si. Desta forma, é possível
construir um BIBD através deste grafo. Através da expressão (5.1), sabe-se que o
BIBD associado a este grafo completo é o (6, 15, 5, 2, 1)−BIBD.
Se não tivéssemos construído o grafo completo, poderíamos do mesmo modo
identificar o BIBD associado a este exemplo, pois com os dados fornecidos é possível
identificar que:
v = 6→ existem seis sites.
b = 15→ existem quinze ligações.
r = 5→ cada site está ligado aos restantes cinco.
Pela expressão (5.6), sabe-se que o BIBD resultante de E(n, 1) é o mesmo BIBD
resultante do grafo completo Kn. Desta forma, calcula-se o número Euleriano do
grafo que relaciona os diferentes sites (grafo K6).
E(6, 1) = 26 − (6 + 1) = 64− 7 = 57, existem 57 permutações com 6 elementos
com precisamente 1 ascendente.
82 Aplicações
6.3 Relações entre as Pessoas
Através da teoria dos grafos é possível estabelecer relações entre as pessoas seja
através de uma árvore genealógica, em que estão estabelecidas as relações familiares
entre as pessoas e as várias gerações, seja através da organização hierárquica dentro
de uma empresa, ou ainda através das relações existentes entre todos os habitantes
de uma cidade.
Exemplo 6.3.1. Considerando a família Bernoulli:
Figura 6.6: Parte da árvore genealógica da família Bernoulli, fonte: Picado [PG08]
As ligações dentro desta família, em grafo, podem ser representadas como se
ilustra na Figura 6.7:
Figura 6.7: Grafo das relações de parentesco da família Bernoulli
Este grafo, que representa as diferentes relações de parentesco entre cada um dos
elementos da família, é um grafo completo pois todos os elementos da família estão
ligados entre si. Desta forma, é possível construir um BIBD através deste grafo.
Através da expressão (5.1), sabe-se que o BIBD associado a este grafo completo é o
(10, 45, 9, 2, 1)−BIBD.
6.3 Relações entre as Pessoas 83
Se não tivéssemos construído o grafo completo, poderíamos na mesma identificar
o BIBD associado a este exemplo, pois com os dados fornecidos identificávamos que:
v = 10→ existem dez elementos da família Bernoulli.
b = 45→ existem 45 relações de parentesco.
r = 9→ cada elemento da família está relacionado com os restantes nove.
Pela expressão (5.6), sabe-se que o BIBD resultante de E(n, 1) é o mesmo BIBD
resultante do grafo completo Kn. Desta forma, calcula-se o número Euleriano do
grafo que relaciona os diferentes elementos da família Bernoulli (grafo K10).
E(10, 1) = 210− (10 + 1) = 1024− 11 = 1013, existem 1013 permutações com 10
elementos da família Bernoulli com 1 ascendente.
84 Aplicações
Capítulo 7
Conclusão
Esta dissertação, que teve como objetivo a construção de ligações entre a teoria
dos designs combinatórios, a teoria dos números e a teoria dos grafos, não poderia
ter sido realizada sem o auxílio teórico da bibliografia consultada.
Sabemos que, com os cálculos apresentados no Capítulo 5, existem diversas apli-
cações do triângulo DNG em tantas situações do nosso quotidiano, muitas das quais
com certeza nem referimos no Capítulo 6. Desta forma, sentimos que esta disser-
tação poderá funcionar como um incentivo a futuras investigações no âmbito do
triângulo DNG. A sequência de Prüfer, as árvores ótimas, o algoritmo de Dijkstra, o
algoritmo de Welsh-Powell e o algoritmo de Floyd-Warshall são exemplos que podem
ser utilizados em estudos futuros sobre o triângulo DNG.
No âmbito das aplicações do triângulo DNG, tal como referimos anteriormente,
algumas foram bem sucedidas, mas outras não. Nos Anexos B, C, D e E encontram-
se os resultados das tentativas das aplicações da teoria dos grafos no problema do
caixeiro-viajante, na coloração de mapas, nas ciências como a biologia e a química
e na resolução de crimes.
Foi de especial interesse reparar como tantos assuntos, diferentes entre si, da área
da matemática se encontram interligados. De um conhecimento mais básico, a outro
de nível mais avançado, todos foram necessários para a realização desta dissertação.
Tendo em conta que a minha formação foi em ciências sociais, mais especifica-
mente em economia, foi interessante reparar como uma ciência exata pode ser a base
de tudo o que nos rodeia.
85
86 Conclusão
Bibliografia
[Axe16] Maria Axenovich. Lecture Notes Graph Theory. 2016.
[BC11] RA Bailey e Peter J Cameron. Using graphs to find the best block designs.
arXiv preprint arXiv:1111.3768, 2011.
[Bra15] Madeline Brandt. The Tutte Polynomial. TACO seminar, 2015.
[Bru09] Richard A Brualdi. Introductory combinatorics. Pearson Education In-
dia, 2009.
[Bur11] David M Burton. Elementary number theory. Tata McGraw-Hill Educa-
tion, 2011.
[BW05] Edward A Bender e S Gill Williamson. Foundations of Combinatorics
with Applications. 2005.
[Cla03] W Edwin Clark. Elementary Number Theory. South Florida University,
2003.
[Di 66] Jane W Di Paola. Block designs and graph theory. Vol. 1. 1. Journal of
Combinatorial Theory in Academic Press, 1966, pp. 132–148.
[Ell18] Jo Ellis-Monaghan. The Tutte Polynomial A Mathematical Catalyst. Saint
Michael’s College, 2018.
[EM11] Joanna A Ellis-Monaghan e Criel Merino. Graph polynomials and their
applications I: The Tutte polynomial. Springer, 2011, pp. 219–255.
[GYA19] Jonathan L Gross, Jay Yellen e Mark Anderson. Graph theory and its
applications. CRC press, 2019.
[HHM08] John Michael Harris, Jeffry L Hirst e Michael J Mossinghoff. Combina-
torics and graph theory. Vol. 2. Springer, 2008.
[HM20] Stephen Huggett e Iain Moffatt. Types of embedded graphs and their Tutte
polynomials. Vol. 169. 2. Cambridge University Press, 2020, pp. 255–297.
[Hol15] Derek Holton. Graph theory – A guide for teachers (Years 11–12). 2015.
[Hwa16] Michael Hwang. Application of Balanced Incomplete Block Designs in Er-
ror Detection and Correction. Out. de 2016. doi: 10.4135/9781473941977.
[Maq19] Gabriel Lima Maquengo. Teoria dos Grafos e Aplicações: Redes Eléctri-
cas e de Transportes Rodoviário. Universidade de Évora, 2019.
[Mar15] Nuno Martins. Algebra Linear. Instituto Superior Técnico, 2015.
[Mes14] Mariusz Meszka. Combinatorial Designs. 2014 PhD Summer School in
Discrete Mathematics, 2014, p. 35.
87
88 BIBLIOGRAFIA
[Nos13] Mohammad Noshad. Applications of Balanced Incomplete Block Designs
to Communication Systems. University of Virginia, dez. de 2013.
[Oli10] Teresa Oliveira. BIB designs with repeated blocks: review and perspec-
tives. Zeinab Amin e Ali, S, Hadi, The American University in Cairo,
2010, pp. 82–96.
[PB15] Alexander M Porter e Barry Balof. The Tutte polynomial and applicati-
ons. Whitman College, 2015.
[Per13] Sandra Maria Pereira dos Santos. Aplicações da teoria dos grafos. Uni-
versidade de Aveiro, 2013.
[PG08] Jorge Picado e Armando Gonçalves. Estruturas Discretas - Textos de
apoio - Capítulo 3.2. Árvores. Universidade de Coimbra - Departamento
de Matemática, fev. de 2008.
[Ros11] Kenneth H Rosen. Elementary number theory. Pearson Education, 2011.
[Ros99] Kenneth H Rosen. Handbook of discrete and combinatorial mathematics.
CRC press, 1999.
[RS13] Awad Rashmi e Banerjee Shakti. A review of literature relating to Ba-
lance Incomplete Block designs with Repeated Blocks. Vol. 2320. Research
Journal of Mathematical e Statistical Sciences _ ISSN, 2013, p. 6047.
[Sil+09] Paula Cecılia dos Santos Leitão Caetano Alves Silva et al. Modelos de
planos em blocos incompletos: revisão e perspectivas. FCT-UNL, 2009.
[Sil06] Joseph H Silverman. A friendly introduction to number theory. Vol. 10.
Am Math Compet, 2006, p. 12.
[SIT95] Kyoko Sekine, Hiroshi Imai e Seiichiro Tani. Computing the Tutte poly-
nomial of a graph of moderate size. Springer, 1995, pp. 224–233.
[Sti07] Douglas Stinson. Combinatorial designs: constructions and analysis. Sprin-
ger Science & Business Media, 2007.
[Van09] Paul Van Dooren. Graph theory and applications. Dublin. https://perso.
uclouvain. be/paul. vandooren/DublinCourse. pdf, 2009, p. 110.
[Wel99] Dominic Welsh. The tutte polynomial. Vol. 15. 3-4. Random Structures
& Algorithms in Wiley Online Library, 1999, pp. 210–228.
[Wil03] Robin Wilson. The early history of block designs. Vol. 9. Rend. Sem. Mat.
Messina Ser. II, 2003, pp. 267–276.
[XTH12] Tingyao Xiong, Hung-ping Tsao e Jonathan Hall. General Eulerian Num-
bers and Eulerian Polynomials. Vol. 2013. Journal of Mathematics, jul. de
2012. doi: 10.1155/2013/629132.
Apêndice A
Álgebra linear
A.1 Matrizes
Considerando uma matriz A de dimensãom×n, ou seja comm linhas e n colunas,
o elemento aij está situado na linha i e na coluna j da matriz A.
A =

a11 a12 · · · a1n
a21 a22 · · · a2n
...
... . . .
...
am1 am2 · · · amn

m×n
A.1.1 Matriz quadrada
Definição A.1.1. Uma matriz quadrada consiste numa matriz de dimensão n× n,
ou de ordem n, ou seja, uma matriz com igual número de linhas e de colunas, neste
caso n linhas e n colunas.
A =

a11 a12 · · · a1n
a21 a22 · · · a2n
...
... . . .
...
an1 an2 · · · ann

n×n
Exemplo A.1.1. A =

5 −1 2 −5
7 2 6 3
−4 3 2 1
1 −6 5 4

4×4
é uma matriz quadrada de dimensão
4× 4, ou de ordem 4.
A.1.2 Matriz diagonal
Definição A.1.2. Uma matriz diagonal é uma matriz quadrada em que todos os
elementos fora da diagonal principal são iguais a zero.
89
90 Álgebra linear
A =

a11 0 · · · 0
0 a22 · · · 0
...
... . . .
...
0 0 · · · ann

n×n
Exemplo A.1.2. A =
2 0 00 5 0
0 0 1

3×3
é uma matriz diagonal de ordem 3.
A.1.3 Matriz identidade
Definição A.1.3. Uma matriz identidade é uma matriz quadrada de ordem n,
representa-se por In, e caracteriza-se por ter todos os elementos da diagonal principal
iguais a um e os restantes iguais a zero.
In =

1 0 · · · 0
0 1 · · · 0
...
... . . .
...
0 0 · · · 1

n×n
Exemplo A.1.3. I4 =

1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

4×4
é a matriz identidade de ordem 4.
A.1.4 Matriz transposta
Definição A.1.4. A matriz transposta de uma matriz A = (aij)m×n é da forma
AT = (aji)n×m, ou seja, a matriz transposta obtém-se da matriz A trocando as
linhas pelas colunas, isto é,
AT =

a11 a12 · · · a1m
a21 a22 · · · a2m
...
... . . .
...
an1 an2 · · · anm

T
m×n
=

a11 a21 · · · an1
a12 a22 · · · an2
...
... . . .
...
a1m a2m · · · anm

n×m
Exemplo A.1.4. AT =
[
4 −2 7 5
−3 1 6 −1
]T
2×4
=

4 −3
−2 1
7 6
5 −1

4×2
A.1.5 Soma de matrizes
Duas matrizes podem ser somadas quando são da mesma dimensão, isto é, as
matrizes A e B podem ser somadas se A = (aij)m×n e B = (bij)m×n. A soma destas
A.1 Matrizes 91
duas matrizes vai originar uma nova matriz C = (aij + bij)m×n.

a11 a12 · · · a1n
a21 a22 · · · a2n
...
... . . .
...
am1 am2 · · · amn

m×n
+

b11 b12 · · · b1n
b21 b22 · · · b2n
...
... . . .
...
bm1 bm2 · · · bmn

m×n
=

a11 + b11 a12 + b12 · · · a1n + b1n
a21 + b21 a22 + b22 · · · a2n + b2n
...
... . . .
...
am1 + bm1 am2 + bm2 · · · amn + bmn

m×n
=

c11 c12 · · · c1n
c21 c22 · · · c2n
...
... . . .
...
cm1 cm2 · · · cmn

m×n
Exemplo A.1.5. Sabendo que:
A =
 2 4 −31 6 2
−8 5 4

3×3
e B =
 1 3 6−3 5 −1
4 7 2

3×3
então
A+B =
 2 + 1 4 + 3 −3 + 61− 3 6 + 5 2− 1
−8 + 4 5 + 7 4 + 2

3×3
=
 3 7 3−2 11 1
−4 12 6

3×3
A.1.6 Multiplicação de matrizes
Duas matrizes podem ser multiplicadas quando o número de colunas da primeira
matriz for igual ao número de linhas da segunda matriz, ou seja, as matrizes A e
B podem ser multiplicadas se A = (aij)m×n e B = (bij)n×p. A multiplicação destas
duas matrizes vai originar a matriz C = AB.
C = (ai1b1j + ...+ ainbnj)m×p =
(
n∑
k=1
aikbkj
)
m×p
92 Álgebra linear

a11 · · · a1n
... . . .
...
ai1 · · · a2n
... . . .
...
am1 · · · amn

m×n
b11 · · · b1j · · · b1p... . . . ... . . . ...
bn1 · · · bnj · · · bnp

n×p
=

n∑
k=1
a1kbk1 · · ·
n∑
k=1
a1kbkj · · ·
n∑
k=1
aikbkp
...
...
n∑
k=1
aikbk1 · · ·
n∑
k=1
aikbkj · · ·
n∑
k=1
aikbkp
...
...
n∑
k=1
amkbk1 · · ·
n∑
k=1
amkbkj · · ·
n∑
k=1
amkbkp

m×p
Exemplo A.1.6. Considerando que:
A =

7 3 4
6 −9 −2
0 8 −2
6 −8 −4
5 2 8

5×3
e B =
 7 5 3 5 −3−6 −9 3 −7 6
−6 0 5 −7 1

3×5
então
AB = C =

7 8 50 −14 1
108 111 −19 107 −74
−36 −72 14 −42 46
114 102 −26 114 −70
−25 7 61 −45 5

5×5
A.2 Determinantes
Definição A.2.1. Determinante é uma função matricial que associa a cada matriz
quadrada um escalar, ou seja, é uma função que transforma uma matriz quadrada
num número real. Representa-se por det A o determinante de uma matriz A.
A.2.1 Matriz de dimensão 2× 2
det A =
∣∣∣∣a11 a12a21 a22
∣∣∣∣ = a11a22 − a12a21
Exemplo A.2.1. Considerando que:
A.2 Determinantes 93
A =
[−4 1
7 4
]
então
det A =
∣∣∣∣−4 17 4
∣∣∣∣ = −4× 4− 1× 7 = −23
A.2.2 Matriz de dimensão 3× 3
det A =
∣∣∣∣∣∣
a11 a12 a13
a21 a22 a23
a31 a32 a33
∣∣∣∣∣∣ = a11
∣∣∣∣a22 a23a32 a33
∣∣∣∣− a12 ∣∣∣∣a21 a23a31 a33
∣∣∣∣+ a13 ∣∣∣∣a21 a22a31 a32
∣∣∣∣
= a11a22a33 + a12a23a31 + a13a21a32 − a13a22a31 − a12a21a33 − a11a23a32
Exemplo A.2.2. Considerando que:
A =
 8 −2 7−4 1 0
6 3 −1

então
det A =
∣∣∣∣∣∣
8 −2 7
−4 1 0
6 3 −1
∣∣∣∣∣∣ = 8
∣∣∣∣1 03 −1
∣∣∣∣− (−2) ∣∣∣∣−4 06 −1
∣∣∣∣+ 7 ∣∣∣∣−4 16 3
∣∣∣∣
= 8× 1× (−1)− 2× 0× 6 + 7× (−4)× 3− 7× 1× 6 + 2× (−4)× (−1)− 8× 0× 3
= −92− 34 = −126
94 Álgebra linear
Anexo A
Matriz de Hadamard do
(11,22,10,5,4)-BIBD
Para (11, 22, 10, 5, 4)−BIBD:
X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
A =

124510, 125911, 126811, 127810, 13456, 13579, 136811, 137810, 14679,
1491011, 23458, 235711, 236910, 236910, 246711, 24789, 3471011, 348911,
456810, 56810, 56789, 5671011, 5891011, 3469, 3478, 4589, 5678, 5679

e a sua matriz de incidência é a seguinte:
95
96 Matriz de Hadamard do (11,22,10,5,4)-BIBD
Figura A.1: Matriz de incidência do design (11,22,10,5,4)
97
Assim, seguindo o procedimento anteriormente descrito, na Subsecção 2.3.1, a
matriz de Hadamard é da seguinte forma:
H121 =

1 1 1 1 1 1 1 1 1 1 1 −1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 −1 −1 −1 −1 −1 −1 1
1 −1 −1 −1 −1 1 1 1 1 −1 −1 1
1 1 −1 −1 −1 1 −1 −1 −1 1 1 1
1 1 1 −1 −1 1 1 −1 −1 −1 −1 −1
1 −1 −1 1 −1 1 −1 1 −1 1 −1 −1
1 −1 −1 −1 1 −1 1 −1 1 1 −1 1
1 −1 −1 1 1 −1 −1 1 1 −1 −1 −1
1 −1 1 −1 −1 −1 1 −1 −1 1 −1 −1
1 1 −1 −1 1 −1 −1 −1 1 −1 1 −1
1 −1 1 1 −1 −1 −1 1 −1 −1 1

e H122 =

1 1 1 1 1 1 1 1 1 1 1 1
1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1 −1
1 1 1 1 1 1 −1 −1 −1 −1 −1 −1
1 1 1 1 −1 −1 1 1 −1 −1 −1 −1
1 −1 −1 −1 1 1 1 1 1 −1 −1 −1
1 1 −1 −1 −1 −1 −1 −1 1 1 1 1
1 −1 1 1 1 −1 −1 −1 1 1 1 −1
1 1 −1 −1 1 1 1 −1 −1 1 1 −1
1 −1 −1 −1 −1 1 −1 1 1 1 −1 1
1 −1 1 1 −1 1 −1 −1 −1 1 −1 1
1 −1 1 1 −1 −1 1 −1 1 −1 1 1
1 1 −1 −1 1 −1 1 1 −1 −1 1 1

H121H
T
121
+H122H
T
122
=
=

24 0 0 0 0 0 0 0 0 0 0 0
0 24 0 0 0 0 0 0 0 0 0 0
0 0 24 0 0 0 0 0 0 0 0 0
0 0 0 24 0 0 0 0 0 0 0 0
0 0 0 0 24 0 0 0 0 0 0 0
0 0 0 0 0 24 0 0 0 0 0 0
0 0 0 0 0 0 24 0 0 0 0 0
0 0 0 0 0 0 0 24 0 0 0 0
0 0 0 0 0 0 0 0 24 0 0 0
0 0 0 0 0 0 0 0 0 24 0 0
0 0 0 0 0 0 0 0 0 0 24 0
0 0 0 0 0 0 0 0 0 0 0 24

= 24I12
98 Matriz de Hadamard do (11,22,10,5,4)-BIBD
Anexo B
Problema do Caixeiro-viajante
O problema do caixeiro-viajante consiste em determinar o menor percurso que
um caixeiro-viajante faz ao passar uma única vez em cada ponto do seu trajeto,
sendo o ponto de partida igual ao ponto de chegada, ou seja, o percurso encontrado
trata-se de um ciclo de Hamilton. Este problema é implementado em várias situ-
ações do quotidiano, não só para determinar a viagem com menor distância, como
também para determinar a viagem com menor custo ou menor tempo de deslocação.
Para descobrir a solução para este problema, podem ser utilizados dois métodos.
O primeiro é o método do vizinho mais próximo, que consiste em deslocar-se
sempre para a cidade mais próxima de onde se está. No entanto, pode não ser o
mais correto e levar a um trajeto que não seja o de menor distância no total.
O segundo é o método exaustivo, que consiste em encontrar todos os ciclos de
Hamilton, e assim escolher o de menor distância total. No entanto, torna-se impra-
ticável este método para um grafo de ordem elevada com vários ciclos de Hamilton.
Exemplo B.0.1. Para exemplificar o problema do caixeiro-viajante será utilizado
o método exaustivo.
Considerando a cidade do Funchal e as suas diferentes freguesias, será calculado o
trajeto do caixeiro-viajante sabendo os valores (fictícios), em euros, de dar a volta à
cidade, partindo da freguesia de Santa Maria Maior e regressando no final do trajeto
à mesma.
99
100 Problema do Caixeiro-viajante
Figura B.1: Grafo que demonstra os diferentes trajetos que o caixeiro-viajante po-
deria escolher no concelho do Funchal
Analisando o grafo, percebe-se que existem três ciclos de Hamilton.
Tabela B.1: Ciclos de Hamilton no concelho do Funchal
Ciclos de Hamilton Custo da viagem
(em euros)
Santa Maria Maior → São Gonçalo → Monte → São Roque →
→ Santo António → Imaculado Coração de Maria → Santa Luzia →
→ São Pedro → São Martinho → Sé → Santa Maria Maior 812
Santa Maria Maior → São Gonçalo → Monte → São Roque →
→ Santa Luzia → Imaculado Coração de Maria → Santo António →
→ São Pedro → São Martinho → Sé → Santa Maria Maior 671
Santa Maria Maior → São Gonçalo → Monte → Santa Luzia →
→ São Roque → Santo António → Imaculado Coração de Maria →
→ São Pedro → São Martinho → Sé → Santa Maria Maior 724
101
Assim, através da tabela anterior conclui-se que o ciclo de Hamilton com menor
custo é o seguinte:
Figura B.2: Ciclo de Hamilton com menor custo dos diferentes trajetos que o
caixeiro-viajante poderia escolher no concelho do Funchal
102 Problema do Caixeiro-viajante
Anexo C
Coloração de Mapas
O Teorema da coloração de mapas, demonstrado em 1976, comprova que é pos-
sível colorir um mapa com apenas quatro cores, considerando que duas regiões com
fronteira comum têm cores distintas.
Para colorir os mapas, com o auxílio da teoria dos grafos, transforma-se um mapa
num grafo, sabendo que os vértices correspondem às diferentes regiões, e as arestas
simbolizam as fronteiras entre as regiões. Assim, para colorir os vértices do grafo, é
utilizado, por exemplo, o número cromático (ver Secção 4.7).
Exemplo C.0.1. Para exemplificar a coloração dos mapas, considera-se o mapa da
Ilha da Madeira, transformando-o no seguinte grafo.
Figura C.1: Mapa da Ilha da Madeira representado na forma de grafo
Assim, utilizando o número cromático (ver Secção 4.7), obtém-se a seguinte
coloração de vértices.
Figura C.2: Coloração do grafo que representa o mapa da Ilha da Madeira
Desta forma, conclui-se que o mapa da Ilha da Madeira pode ser colorido utili-
zando apenas três cores.
103
104 Coloração de Mapas
Anexo D
Aplicação nas Ciências
D.1 Os Grafos na Biologia
Na área da biologia a teoria dos grafos é utilizada, por exemplo, na construção
de cadeias e teias alimentares. Uma cadeia alimentar, utilizando a teoria dos grafos,
seria, por exemplo, da seguinte forma:
Figura D.1: Exemplo de uma cadeia alimentar
Por outro lado, a rede alimentar, que consiste num conjunto de várias cadeias
alimentares interligadas, utilizando a teoria dos grafos, poderia ser representada da
seguinte forma:
Figura D.2: Exemplo de uma rede alimentar
105
106 Aplicação nas Ciências
D.2 Os Grafos na Química
Na área da química, um exemplo onde se utiliza a teoria dos grafos é na formação
de moléculas, através da junção de átomos.
Os grafos podem representar moléculas simples, como a da água (H2O), que só tem
três átomos (ver Figura D.3),
Figura D.3: Grafo representativo da molécula da água
como também podem ser utilizados para representar moléculas mais complexas,
como a da cafeína (C8H10N4O2), em que existem 24 átomos (Figura D.4).
Figura D.4: Grafo representativo da molécula da cafeína
Desta forma, através da teoria dos grafos, fica simplificada a relação entre cada
um dos átomos numa molécula.
Anexo E
Aplicação na resolução de crimes
Exemplo E.0.1. Considere-se um crime onde estão envolvidos quatro suspeitos. O
suspeito a incrimina o suspeito c, o suspeito b diz que não é culpado, o suspeito c
também diz que não é culpado e o suspeito d incrimina o suspeito a. Com estas
informações, é possível construir um digrafo com quatro vértices em que a direção
dos arcos corresponde a quem o suspeito incriminou.
Como os suspeitos b e c afirmam que não são culpados, considera-se que desta forma
estão a ilibar-se e a culpar os restantes. Além do testemunho de cada suspeito,
também sabe-se que apenas um deles está a dizer a verdade.
Assim, o digrafo que representa este exemplo tem a forma:
Figura E.1: Digrafo que representa os testemunhos dos suspeitos
A partir do digrafo sabe-se quais são os graus de entrada de cada um dos vértices
(ver Tabela E.1):
Tabela E.1: Graus de entrada de cada um dos vértices
Vértices a b c d
Grau de entrada 3 1 2 2
Como apenas um dos suspeitos está a dizer a verdade, então o suspeito b é o
culpado. Se três dos sujeitos estivessem a dizer a verdade o culpado seria o suspeito
a, e se dois dos suspeitos estivessem a dizer a verdade então o culpado seria o sujeito
c ou o sujeito d, ou seja, nem o sujeito a nem o sujeito b seriam culpados.
107