Introdução à teoria dos grafos autor Edson Prestes

Prévia do material em texto

Introdução à Teoria dos Grafos
Edson Prestes
2020
Dedico este livro à minha famı́lia e amigos.
O importante é o ser e não o vir a ser; um não é o oposto do outro, havendo
o oposto ou a oposição, cessa o ser. Ao findar o esforço para vir-a-ser, surge
a plenitude do ser, que não é estático; não se trata de aceitação; o vir-a-ser
depende do tempo e do espaço. O esforço deve cessar; disso nasce o ser que
transcende os limites da moral e da virtude social, e abala os alicerces da
sociedade. Esta maneira de ser é a própria vida, não mero padrão social.
Lá, onde existe vida, não existe perfeição; a perfeição é uma idéia, uma
palavra; o próprio ato de viver e existir transcende toda forma de
pensamento e surge do aniquilamento da palavra, do modelo, do padrão.
Jiddu Krishnamurti (1895-1986)
Prefácio
Este livro é resultado das minhas notas de aulas da cadeira de Teoria dos
Grafos e Análise Combinatória que ministro desde 2005 no Instituto de In-
formática na Universidade Federal do Rio Grande do Sul. Ao longo dos anos,
tenho observado a necessidade de um livro nesta área escrito em português
com linguagem acesśıvel. Assim nas minhas horas vagas detive-me a escrever
este livro. Esta primeira versão demorou vários anos para ser finalizada de-
vido aos meus inúmeros compromissos dentro e fora do Páıs. Ela contou com
o apoio dos meus alunos Renata Neuland e Gean Stein, à Jéssica Dagostini,
Vińıcius Lazzari no processo de revisão.
Espero que este livro motive os alunos da graduação em ciência da com-
putação e também de áreas correlatas a se interessarem pela área de teoria
dos grafos. É claro que esta área é muito mais ampla e densa do que o
conteúdo discutido nas páginas seguintes, porém penso neste livro como um
passaporte de entrada para esta área magńıfica. Além das notas, este livro
foi ancorado em obras magńıficas listadas abaixo :
• F. Harary. Graph Theory. Addison-Wesley Publishing Company,
1969.
• J. A. Bondy e U.S.R. Murty. Graph Theory with Applications.
Elsevier Science Ltd/North-Holland. 1979.
• J. Clark e D.A. Holton. A First Look at Graph Theory. World
Scientific Pub Co Inc. 1991.
• D. West. Introduction to Graph Theory. Prentice-Hall, Inc. 1996.
• R. Diestel. Graph Theory. Springer-Verlag. 2005.
• J. M. Harris, J. L. Hirst e M. J. Mossinghoff. Combinatorics and
Graph Theory.Springer Science+Business Media, LLC. 2005.
• J. Bang-Jensen e G. Gutin. Digraphs - Theory, Algorithms and
Applications . Springer-Verlag. 2008.
v
Além de oferecer aos estudantes um livro com linguagem acesśıvel, eu
o ofereço como um presente a todos aqueles que precisam adquirir conheci-
mento nesta área e muitas vezes não possuem ou conhecimento básico ade-
quado ou recursos financeiros. Por isso tentei ser o mais didático posśıvel
neste texto e escrevi este trabalho sob a poĺıtica do Creative Commons.
Acredito que qualquer pessoa mereça acesso ao conhecimento. Assim barrei-
ras precisam ser quebradas e uma das formas de fazermos isso é através de
publicações abertas. Já fui um estudante de graduação e sei a dificuldade
que é adquirir uma obra na área.
Espero que apreciem o trabalho, e desfrutem dele sem moderação :)
Edson Prestes
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
vi
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
Conteúdo
1 Fundamentação Teórica 1
1.1 Conceitos Básicos . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Relação de Vizinhança . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Matrizes de Adjacência e de Incidência . . . . . . . . . . . . . 11
1.4 Passeios e Circuitos . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Grafos Eulerianos e Hamiltonianos . . . . . . . . . . . . . . . 18
1.6 Isomorfismo e Automorfismo . . . . . . . . . . . . . . . . . . . 22
1.7 Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.7.1 Associação de Tarefas . . . . . . . . . . . . . . . . . . 26
1.7.2 Robótica . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.7.3 Nichos Ecológicos . . . . . . . . . . . . . . . . . . . . . 27
1.7.4 Rede de Telefonia Móvel . . . . . . . . . . . . . . . . . 28
1.7.5 Reconhecedores de sentenças . . . . . . . . . . . . . . . 29
1.7.6 Redes Neurais Artificiais . . . . . . . . . . . . . . . . . 29
1.8 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2 Tipos de Grafos e Operações 35
2.1 Grafos Especiais . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2 Operações com grafos . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.1 União . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.2 Junção . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2.3 Intersecção . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2.4 Produto . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2.5 Complemento . . . . . . . . . . . . . . . . . . . . . . . 41
2.2.6 Remoção . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.2.7 Contração . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.2.8 Supressão e Subdivisão . . . . . . . . . . . . . . . . . . 44
2.2.9 Decomposição . . . . . . . . . . . . . . . . . . . . . . . 45
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
viii CONTEÚDO
2.2.10 Operador Linha L . . . . . . . . . . . . . . . . . . . . 46
2.3 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3 Conectividade 51
3.1 Relação de Vizinhança Estendida e Fechamento Transitivo . . 52
3.2 Grafos Conexos e Desconexos . . . . . . . . . . . . . . . . . . 55
3.3 Vértice de Corte . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.4 Aresta de Corte . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.5 Conectividade em Dı́grafos . . . . . . . . . . . . . . . . . . . . 61
3.6 Cálculo de Componentes . . . . . . . . . . . . . . . . . . . . . 67
3.7 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4 Relacionamentos V-A 73
4.1 Clique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.2 Conjunto Independente . . . . . . . . . . . . . . . . . . . . . . 77
4.3 Cobertura de Vértices . . . . . . . . . . . . . . . . . . . . . . 81
4.4 Conjunto Dominante . . . . . . . . . . . . . . . . . . . . . . . 84
4.5 Emparelhamento . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.6 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5 Enumeração 97
5.1 Método de Maghout . . . . . . . . . . . . . . . . . . . . . . . 97
5.2 Enumeração em Grafos . . . . . . . . . . . . . . . . . . . . . . 101
5.2.1 Coberturas de Vértices e Conjuntos Independentes . . 101
5.2.2 Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.2.3 Conjuntos dominantes . . . . . . . . . . . . . . . . . . 104
5.2.4 Emparelhamentos . . . . . . . . . . . . . . . . . . . . . 106
5.3 Enumeração em Dı́grafos . . . . . . . . . . . . . . . . . . . . . 111
5.3.1 Coberturas de Vértices e Conjuntos Independentes . . 111
5.3.2 Coberturas de Fonte e Sumidouro . . . . . . . . . . . . 114
5.3.3 Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.3.4 Conjuntos Dominantes . . . . . . . . . . . . . . . . . . 116
5.3.5 Emparelhamentos . . . . . . . . . . . . . . . . . . . . . 121
5.4 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6 Árvores 125
6.1 Conceitos Básicos . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.2 Árvores Enraizadas . . . . . . . . . . . . . . . . . . . . . . . . 128
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
CONTEÚDO ix
6.3 Árvores de Espalhamento . . . . . . . . . . . . . . . .. . . . 133
6.4 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7 Planaridade 147
7.1 Multigrafos Planares . . . . . . . . . . . . . . . . . . . . . . . 147
7.2 Teorema de Euler . . . . . . . . . . . . . . . . . . . . . . . . . 150
7.3 Teorema de Kuratowski . . . . . . . . . . . . . . . . . . . . . 154
7.4 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
8 Coloração 157
8.1 Grafos Coloŕıveis . . . . . . . . . . . . . . . . . . . . . . . . . 157
8.2 Grafos Aresta-Coloŕıveis . . . . . . . . . . . . . . . . . . . . . 162
8.3 Polinômio Cromático . . . . . . . . . . . . . . . . . . . . . . . 163
8.4 O teorema das quatro cores . . . . . . . . . . . . . . . . . . . 168
8.5 Exerćıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
x CONTEÚDO
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
Caṕıtulo 1
Fundamentação Teórica
A Teoria dos Grafos surgiu com os trabalhos de L. Euler, G. Kirchhoff e A.
Cayley. O primeiro e mais famoso problema, chamado o problema das pontes
de Königsberg foi enunciado por Euler em 1736. Na cidade de Königsberg Problema das
Pontes de
Königsberg
(antiga Prússia), existiam sete pontes que cruzavam o rio Pregel estabele-
cendo ligações entre diferentes partes da cidade e as ilhas Kneiphof e Lomse
(ver Figura 1.1). O problema consistia em determinar se era posśıvel ou não
fazer um passeio pela cidade começando e terminando no mesmo lugar, cru-
zando cada ponte exatamente uma única vez. Veremos na Seção 1.5 que a
resposta para esta pergunta é não.
A Teoria dos Grafos possui aplicação direta em áreas como f́ısica, qúımica,
engenharias, psicologia, etc. Em particular, ela é de fundamental importância
aos cursos de Ciência e Engenharia da Computação. Isto se deve a inúmeros
motivos, entre eles, o fato de servir de modelo matemático para alguns dos
problemas mais importantes e dif́ıceis da computação. Estes problemas estão
associados à classe de problemas NP-Completos, cuja solução em tempo po-
linomial por uma máquina de turing determińıstica não é conhecida.
Vários problemas do mundo real podem ser analisados usando a Teoria
dos Grafos, por exemplo, o escalonamento de processos pode ser visualizado
como um aplicação direta do problema de coloração de grafos; o problema de
reconhecimento de padrões pode ser visto como uma instância do problema
de isomorfismo em grafos; o problema de roteamento é o problema de verificar
se um grafo é Hamiltoniano ou não, e se for determinar o ciclo hamiltoniano
de custo mı́nimo.
Este livro introduz a base teórica da área de Teoria dos Grafos, apresen-
tando os principais conceitos (definições, propriedades, classes, teoremas) e
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
2 Fundamentação Teórica
problemas. Exemplificaremos sempre que posśıvel o uso destes conceitos em
problemas do mundo real. Além disso, será dada ênfase ao aspecto combina-
torial da área apresentando o uso da análise combinatória em problemas de
enumeração e contagens.
Figura 1.1: Pontes de Königsberg
1.1 Conceitos Básicos
Definição 1.1. Um grafo simples G = (V,A) é uma estrutura discreta for-Grafo Simples
mada por um conjunto não vazio de vértices V e um conjunto de arestas
A ⊆ P(V ), onde P(V ) = {{x, y} : x, y ∈ V } é o conjunto de todos os pares
não ordenados1 não necessariamente distintos gerados a partir de V . Cada
aresta {x, y} ∈ A é formada por um par de vértices distintos, i.e., x 6= y.
Para cada par de vértices existe no máximo uma aresta associada.
Dois vértices x e y são adjacentes se e somente se existe uma aresta
{x, y} ∈ A. Neste caso, dizemos que a aresta {x, y} é incidente aos vérticesVértices Adja-
centes x e y. Quando um vértice não é adjacente a outro, dizemos que ele é um
vértice isolado.
Um grafo deixa de ser simples quando possui múltiplas arestas entre o
mesmo par de vértices e/ou quando possui uma aresta, chamada laço, inci-
dente a um par de vértices não distintos. Se o grafo possuir múltiplas arestas
e não possuir laços então ele é chamado multigrafo , caso contrário, se eleMultigrafo
possuir laços então é chamado de pseudografo. A existência de múltiplasPseudografo
1Um par não ordenado formado pelos vértices x e y é representado por {x, y}, onde
{x, y} = {y, x}. Se x = y, então {x, y} = {x, x} = {x}.
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.1 Conceitos Básicos 3
arestas, leva à definição da função φ : A → P(V ), chamada de função de Função de In-
cidênciaincidência do grafo, que mapeia cada aresta ao par de vértices associado.
Isto permite distinguir cada aresta individualmente. Baseado nisto, temos a
seguinte definição que inclui multigrafos, pseudografos e grafos simples.
Definição 1.2. Um grafo G = (V,A, φ) é um conjunto não vazio de vértices
V , um conjunto de arestas A, e uma função de mapeamento φ : A → P(V )
que mapeia cada aresta a um par não ordenado formado pelos vértices de G.
O número de vértices de G, denotado por |V | indica a ordem de G, enquanto
que o número de arestas, denotado por |A|, indica o tamanho de G2.
(a) (b)
Figura 1.2: Exemplos de (a) grafo simples e (b) pseudografo
A Figura 1.2 mostra um (a) grafo simples e um (b) pseudografo, onde as li-
nhas representam as arestas e os ćırculos escuros representam os vértices. Em
(a), cada aresta une um par de vértices distintos e não existem múltiplas ares-
tas unindo um mesmo par. Logo, cada aresta é representada pelos vértices
os quais incide, por exemplo, a aresta unindo os vértices 1 e 2 é representada
por {1, 2}. Assim, φ({1, 2}) = {1, 2}, i.e., φ({x, y}) = {x, y}, ∀{x, y} ∈ A.
Em (b) existem múltiplas arestas unido os vértices 1 e 2, e os vértices 3 e 4.
Para distingui-las, as arestas são rotuladas com as letras de a a h. Observe
que φ(f) = φ(g) = φ(h) = {3, 4} e φ(a) = φ(b) = {1, 2}, porém f 6= g 6= h
2Alguns autores usam |G| e ||G|| para indicar a ordem e o tamanho de G, respectiva-
mente
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
4 Fundamentação Teórica
e a 6= b. Quando um dado par de vértices está associado a k arestas distin-
tas, dizemos que ele possui multiplicidade igual a k, i.e., µ(x, y) = k. NesteMultiplicidade
de Arestas caso, a multiplicidade do par {3, 4} é igual a µ(3, 4) = 3, enquanto que a
multiplicidade do par {1, 2} é igual a µ(1, 2) = 2. Em um grafo simples a
multiplicidade de cada par de vértices é no máximo igual a 1. Em (a), existe
um vértice isolado representado pelo vértice 5, enquanto que em (b), existe
um laço representado pela aresta e. Se (b), não possúısse o laço e, então seria
um multigrafo. A existência de laço indica que o grafo é um pseudografo.
Neste livro iremos apenas distinguir o grafo simples dos demais grafos, que
serão chamados apenas por grafos.
Para este exemplo, o grafo da Figura 1.2(a) é representado por Ga =
(Va, Aa, φa) ou apenas por Ga = (Va, Aa), pois como ele é simples, a função
φa(.) se torna a função identidade podendo ser suprimida. Os conjuntos de
vértices e arestas são definidos por Va = {1, 2, 3, 4, 5} e Aa = {{1, 2}, {1, 3},
{3, 2}, {3, 4}}, respectivamente. Por outro lado, o grafo da Figura 1.2(b) é
definido por Gb = (Vb, Ab, φb) com Vb = {1, 2, 3, 4}, Ab = {a, b, c, d, e, f, g, h}
e
φb =
(
a b c d e f g h
{1, 2} {1, 2} {1, 3} {2, 3} {2} {3, 4} {3, 4} {3, 4}
)
Se retirarmos os laços e todas as múltiplas arestas entre cada par de
vértice, mantendoapenas uma, transformaremos um pseudografo em umGrafo Subja-
cente a Pseudo-
grafos e Multi-
grafos
grafo simples. O mesmo pode ser feito no caso de multigrafos, porém não
existem laços para serem removidos. O grafo simples encontrado é chamado
de grafo simples subjacente, ou apenas, grafo subjacente ao multigrafo ou
ao pseudografo. Realizando este procedimento no grafo da Figura 1.3(a),
encontramos o grafo simples mostrado em (b).
As arestas de um grafo possuem a função de indicar o relacionamento
entre os elementos que o grafo representa, que podem ser do mundo real
ou não, de forma simétrica. Este relacionamento pode corresponder a uma
propriedade espacial, comportamental, temporal ou outra. Em diversas si-
tuações esta relação não é simétrica, por exemplo, o sentido do fluxo de carros
nas ruas de uma cidade. Se representarmos cada entrocamento (cruzamento)
desta cidade como sendo um vértice em um grafo e o fluxo permitido como
sendo a relação entre os entrocamentos, veremos que em diversas situações
a ida de um entrocamento A para o entroncamento B não implica a volta,
ou seja, a ida do entroncamento B para o entrocamento A. Nesta situação
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.1 Conceitos Básicos 5
(a) (b)
Figura 1.3: Exemplo de (a) pseudografo e seu (b) grafo simples subjacente.
precisamos ter uma forma de indicar esta restrição no grafo. Isto é feito
determinando uma direção para cada aresta.
A inserção desta informação faz com que o grafo se torne orientado. As-
sociando pares ordenados de vértices às arestas do grafo, teremos um grafo
direcionado ou d́ıgrafo. Cada par ordenado3 (x, y) define um arco com ori-
gem em (ou adjacente em) x e destino em (ou adjacente para) y, ou seja,
(x, y) 6= (y, x). É comum dizermos que o vértice x domina y, e que o vértice
y é dominado por x. De forma similar ao exposto anteriormente para grafos, Dominância
um d́ıgrafo pode conter laços e múltiplos arcos entre um mesmo par ordenado
de vértices. Quando um d́ıgrafo não possui laços tão pouco múltiplos arcos
entre um mesmo par ordenado de vértices, ele é chamado d́ıgrafo simples ou
grafo direcionado simples. Quando um d́ıgrafo possui múltiplos arcos de um Dı́grafo Simples
vértice a outro, então ele é chamado de multigrafo direcionado. Quando k Multigrafo Dire-
cionadoarcos têm origem no vértice x e destino no vértice y, então dizemos que o
arco (x, y) tem multiplicidade igual a k, i.e., µ(x, y) = k. Em pseudografos e
multigrafos, µ(x, y) = µ(y, x), o que não é garantido nos casos de multigrafos
direcionados. Quando o d́ıgrafo não possui laços, múltiplas arestas entre um
mesmo par ordenado de vértices, nem pares simétricos de arcos então ele é
chamado de grafo orientado. Quando laços são permitidos laços, o d́ıgrafo é Grafo Orientado
chamado de pseudografo direcionado. Pseudografo Di-
recionado
Definição 1.3. Um d́ıgrafo D = (Vd, Ad, φd) é um conjunto não vazio de
vértices Vd, um conjunto de arcos Ad, e uma função de mapeamento φd :
Ad → Vd × Vd que mapeia cada arco a um par ordenado formado pelos
3Um par ordenado formado pelos vértices x e y é representado de maneira tradicional
por (x, y), onde, (x, y) 6= (y, x).
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
6 Fundamentação Teórica
vértices de D. De forma similar à definição usada para grafos, o número
de vértices de D, denotado por |Vd| indica a ordem de D, enquanto que o
número de arcos, denotado por |Ad|, indica o tamanho de D4.
A Figura 1.4(a) ilustra um grafo orientado, enquanto que (b) ilustra um
pseudografo direcionado. (b) possui múltiplos arcos entre um mesmo par
ordenado, entre eles podemos destacar, os arcos a e b que têm origem no
vértice 1 e destino no vértice 2. Além disso, ele possui o laço e. Se este
d́ıgrafo não possúısse os arcos b, g e e, ele seria classificado como d́ıgrafo
simples. Se removêssemos desse d́ıgrafo simples o arco h ou f , estaŕıamos
eliminando o único par simétrico existente, e este d́ıgrafo passaria a ser um
grafo orientado. Neste livro iremos apenas distinguir o grafo orientado dos
demais d́ıgrafos, os quais serão chamados apenas por d́ıgrafos.
(a) (b)
Figura 1.4: Exemplos de (a) d́ıgrafo simples e (b) pseudografo direcionado
De forma similar aos grafos, um d́ıgrafo possui um grafo subjacente. EleGrafo Subja-
cente ao Dı́grafo é obtido substituindo cada arco por uma aresta, i.e., removendo a orientação
de cada arco. Por exemplo, a Figura 1.2(b) mostra o grafo subjacente ao
d́ıgrafo ilustrado na Figura 1.4(b).
Definição 1.4. Um grafo G1 = (V1, A1) é um subgrafo de G2 = (V2, A2),
denotado por G1 ⊆ G2 se e somente se V1 ⊆ V2 e A1 ⊆ A2. Neste caso
4Alguns autores usam |D| e ||D|| para indicar a ordem e o tamanho de D, respectiva-
mente
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.2 Relação de Vizinhança 7
G2 é supergrafo de G1.(definição similar para sub- e superd́ıgrafos, porém
considerando a orientação dos arcos).
Se G1 é subgrafo de G2, então G2 é supergrafo de G1. Quando G1 6= G2, Subgrafo e
Subd́ıgrafo de
Espalhamento
então G1 é um subgrafo próprio de G2. Quando V1 = V2, então G1 é chamado
subgrafo gerador ou subgrafo de espalhamento de G2. Para um d́ıgrafo D1,
um subd́ıgrafo D2 que contém um conjunto de vértices igual ao conjunto de
vértices do d́ıgrafo original é chamado de subd́ıgrafo de espalhamento ou fator Fator
do d́ıgrafo.
Considerando um grafo G = (V,A) e um subconjunto não vazio Sv ⊆ V ,
um subgrafo de G induzido por Sv, denotado por G[Sv], é aquele que tem Grafo Induzido
como conjunto de vértices Sv e como conjunto de arestas todas as arestas de
G que possuam ambas extremidades em Sv. Se Sa ⊆ A é um subconjunto
não vazio de arestas, G[Sa] é um subgrafo de G induzido por Sa que tem
como conjunto de arestas Sa e como conjunto de vértices as extremidades
das arestas de Sa(Os mesmo conceitos se aplicam aos d́ıgrafos, porém temos
a expressão d́ıgrafo induzido). A Figura 1.5 ilustra (a) um grafo G e os
subgrafos induzidos (b) G[Sv] e (c) G[Sa], assumindo Sv = {0, 4, 5, 6} e Sa =
{{0, 4}, {0, 5}, {0, 1}, {2, 6}}.
(a) (b) (c)
Figura 1.5: Exemplo de grafo induzido por vértices e por arestas. (a) grafo G,
(b) grafo induzido G[Sv] por um conjunto de vértices Sv e (c) grafo induzido
G[Sa] por um conjunto de arestas Sa
1.2 Relação de Vizinhança
Tanto as arestas de um grafo quando os arcos de um d́ıgrafo definem uma
relação de vizinhança entre os vértices. Para um grafo G = (V,A, φ), o
conjunto de vértices adjacentes a um vértice v ∈ V é definido pela função Função Multiva-
lorada de Vizi-
nhança
multivalorada de vizinhança, τ : V ; 2V ,
τ(v) = {w : {v, w} = φ(e) ∧ e ∈ A}
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
8 Fundamentação Teórica
onde v pode ou não ser igual a w. Quando v = w teremos v ∈ τ(v). O
conjunto 2V é chamado conjunto das partes e contém todos os subconjuntos
que podem ser formados usando os elementos de V . Se V = {1, 2, 3} então
2V = {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}. Portanto |2V | = 2|V |.
Para um d́ıgrafo D = (Vd, Ad, φd), as funções multivaloradas de vizinhança
direta τ+ : Vd ; 2
Vd e inversa τ− : Vd ; 2
Vd são definidas porFunções Multi-
valoradas de Vi-
zinhança Direta
e Inversa
τ+(v) = {w : (v, w) = φd(e) ∧ e ∈ Ad}
e
τ−(v) = {w : (w, v) = φd(e) ∧ e ∈ Ad}.
A função τ+(v) retorna todos os vértices atinǵıveis diretamente a partir de v
através dos arcos que têm origem em v, enquanto que τ−(v) retorna todos os
vértices que atingem diretamente v através dos arcos que têm como destino
v. Lembrando que φ(e)= e (ou φd(e) = e) para o caso de não existirem
múltiplas arestas(ou arcos) entre um mesmo par de vértices.
A quantidade de vizinhos de um vértice permite determinar o que é cha-
mado grau de um vértice. Para um grafo simples, o grau de qualquer vértice
v, denotado por d(v), é definido por d(v) = |τ(v)|5. Para um grafo qualquerGrau
G = (V,A), o grau de um vértice v é definido pela quantidade n de arestas
que unem v aos outros vértices do grafo(exceto ele próprio) e pela quantidade
p de laços em v, ou seja,
d(v) = n+ 2p.
Quando um vértice v é isolado, ou seja, τ(v) = ∅, seu grau d(v) = 0. A partir
dáı, podemos definir o menor e maior graus dentre todos os seus vérticesMenor Grau
Maior Grau como, respectivamente,
∆(G) = max
v∈V
d(v) e δ(G) = min
v∈V
d(v).
Note que
δ(G) ≤ d(v) ≤ ∆(G), ∀v ∈ V.
Na Figura 1.2(a),
d(1) = 2, d(2) = 2, d(3) = 3, d(4) = 1, d(5) = 0, δ(G) = 0 e ∆(G) = 3.
Enquanto que na Figura 1.2(b),
d(1) = 3, d(2) = 5, d(3) = 5, d(4) = 3, δ(G) = 3 e ∆(G) = 5.
5O grau de um vértice é denotado por d devido a palavra grau ser em inglês chamada
degree.
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.2 Relação de Vizinhança 9
Teorema 1.1 (Handshaking Problem). Para um grafo G=(V,A), temos∑
v∈V
d(v) = 2|A|
Em um d́ıgrafo qualquer, cada vértice v possui um grau de entrada, d−(v), Graus de En-
trada e de Sáıdae um grau de sáıda, d+(v). O grau de entrada de um vértice v é o definido
pelo número de arcos que possuem como destino v (incluindo o laço) en-
quanto que o grau de sáıda é o número de arcos que possuem como origem v
(incluindo o laço). Um laço em vértice v é contado uma única vez no grau de
entrada de v e uma única vez no grau de sáıda de v. Para d́ıgrafos simples
(e grafos orientados), podemos usar as funções de vizinhança τ−(v) e τ+(v)
para calcular os graus de sáıda e de entrada de cada vértice. Neste caso, para
qualquer vértice v temos d−(v) = |τ−(v)| e d+(v) = |τ+(v)|.
De forma similar ao exposto anteriormente, podemos definir para um
d́ıgrafo D os graus de entrada máximo e mı́nimo, ∆−(D) e δ−(D), respecti-
vamente, e os graus de sáıda máximo e mı́nimo, ∆+(D) e δ+(D), respectiva-
mente. Na Figura 1.4(a), o d́ıgrafo tem
d−(1) = 1, d−(2) = 2, d−(3) = 0, d−(4) = 1, δ−(D) = 0,∆−(D) = 2,
d+(1) = 1, d+(2) = 0, d+(3) = 3, d+(4) = 0, δ+(D) = 0,∆+(D) = 3.
Enquanto que na Figura 1.4(b), o d́ıgrafo tem
d−(1) = 1, d−(2) = 3, d−(3) = 2, d−(4) = 2, δ−(D) = 1,∆−(D) = 3
d+(1) = 2, d+(2) = 2, d+(3) = 3, d+(4) = 1, δ+(D) = 1,∆+(D) = 3.
Teorema 1.2. Para um d́ıgrafo D = (Vd, Ad) temos∑
v∈Vd
d−(v) =
∑
v∈Vd
d+(v) = |Ad|
Quando um vértice v de um d́ıgrafo possui grau d−(v) = 0, ele é chamado
de vértice fonte e quando ele possui grau de sáıda d+(v) = 0, ele é chamado
de vértice sumidouro . A Figura 1.4(a) mostra um vértice fonte represen- Vértices Fonte e
Sumidourotado pelo vértice 3 e dois vértices sumidouros representados pelos vértices
2 e 4. Se este d́ıgrafo está associado à uma rede de transmissão de dados,
podemos relacionar o vértice fonte a um emissor que não é receptor, pois
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
10 Fundamentação Teórica
ele apenas emite informações sem ter a capacidade de recebê-las de volta.
Por outro lado, o vértice sumidouro é um receptor que não é emissor, ou
seja, ele apenas recebe informações, porém sem ser capaz de propagá-la adi-
ante para outros computadores. Os outros vértices conseguem tanto receber
informações quanto propagá-la adiante.
A seqüência não crescente d(G) = d1, d2, . . . , dn, com di ≥ dj para j ≥ i
formada pelo grau dos vértices de um grafo G de n vértices é chamada deSeqüência de
Graus Seqüência de Graus. Cada grafo possui uma única seqüência de graus, porém
uma mesma seqüência pode estar associada a grafos distintos. A Figura 1.6
mostra dois grafos distintos estruturalmente com a mesma seqüência de graus
igual a 4, 3, 2, 2, 1. Tanto a soma dos elementos desta seqüência quanto a
quantidade de valores ı́mpares são pares.
(a) (b)
Figura 1.6: Grafos com mesma seqüência de graus.
Teorema 1.3. Toda seqüência não negativa d1, d2, . . . , dn é uma seqüência
de graus de um grafo(simples ou não) se e somente se
∑n
i=1 di é par.
Existem seqüências que podem não estar associados a grafos simples.
Por exemplo, com a seqüência 3, 3, 3, 1 não é posśıvel construir um grafo
simples, mesmo tendo a soma de seus termos um valor par (Verifique!). Se
a seqüência permitir a construção de um grafo simples então ela é chamada
seqüência gráfica. Para verificar se uma dada seqüência é gráfica ou nãoSeqüência
Gráfica usamos o seguinte Teorema .
Teorema 1.4 ([1]). Para n > 1, uma seqüência d de inteiros com n elementos
é uma seqüência gráfica se e somente se d′ é uma seqüência gráfica, onde d′ é
obtido a partir de d removendo seu maior elemento ∆ e subtraindo 1 de seus
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.3 Matrizes de Adjacência e de Incidência 11
∆ maiores elementos seguintes. Assumimos que a única seqüência gráfica
com 1 elemento é d1 = 0.
A aplicação do Teorema 1.4 na seqüência s1 = 3, 3, 3, 1 leva aos seguintes
passos. Inicialmente removemos o maior elemento ∆1 = 3 e subtraimos de 1
os ∆1 maiores elementos seguintes. Isto resulta na seqüência s2 = 2, 2, 0. Em
s2, repetimos o processo, removendo o maior elemento ∆2 = 2, e subtraindo
de 1 os ∆2 maiores elementos seguintes. Isto resulta na seqüência s3 = 1,−1,
que não corresponde a uma seqüência gráfica, já que um dos requisitos para
que uma seqüência seja gráfica é que ela seja formada apenas por valores não
negativos.
1.3 Matrizes de Adjacência e de Incidência
Um grafo G = (V,A), com |V | = n e |A| = m, pode ser representado
usando dois tipos de matriz, chamados de matriz de adjacência e matriz de
incidência. A matriz de adjacência é uma matriz M = [mi,j] simétrica n× n
que armazena o relacionamento entre os vértices do grafo. Cada entrada mi,j
é igual a
mi,j =

0 , se i não é adjacente a j
m , se i é adjacente a j (com i 6= j), m corresponde à quantidade
de arestas conectando i e j.
p , se i = j, p é a quantidade de laços incidentes ao vértice i.
Por outro lado, a matriz de incidência B = [bi,j] é uma matriz n×m, que
associa os vértices às arestas de G. Cada entrada bi,j relaciona o vértice i à
aresta j assumindo os seguinte valores
bi,j =
{
0 , se j não é incidente em i
1 , se j é ou não um laço e i é uma de suas extremidades.
As matrizes de adjacência e de incidência para o grafo da Figura 1.2(b) são
mostradas nas Tabelas 1.1 e 1.2.
De forma similar, um d́ıgrafo D pode ser representado usando matrizes de
incidência e de adjacência. A matriz de adjacência é uma matriz A = [ai,j],
não necessariamente simétrica, onde cada entrada ai,j é igual a
ai,j =
{
0 , se i não é adjacente a j
m , onde m é a quantidade de arcos com origem em i e destino em j
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
12 Fundamentação Teórica
1 2 3 4
1 0 2 1 0
2 2 1 1 0
3 1 1 0 3
4 0 0 3 0
Tabela 1.1: Matriz de Adjacência do grafo da Figura 1.2(b).
a b c d e f g h
1 1 1 1 0 0 0 0 0
2 1 1 0 1 1 0 0 0
3 0 0 1 1 0 1 1 1
4 0 0 0 0 0 1 1 1
Tabela 1.2: Matriz de incidência do grafo da Figura 1.2 (b)
A matriz de adjacência para o d́ıgrafo da Figura 1.4(b) é mostrada na ta-
bela 1.3
1 2 3 4
1 0 2 0 0
2 0 1 1 0
3 1 0 0 2
4 0 0 1 0
Tabela 1.3: Matriz de Adjacência do d́ıgrafo da Figura 1.4(b).
Por sua vez, na matriz de incidência B = [bi,j] cada entrada bij relaciona
o vértice i à aresta j assumindoos valores
bi,j =

−1 , se j tem origem em i.
0 , se j não é incidente em i
1 , se j tem destino em i.
A matriz de incidência para o d́ıgrafo da Figura 1.4(b) é mostrada na
Tabela 1.4
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.4 Passeios e Circuitos 13
a b c d e f g h
1 -1 -1 1 0 0 0 0 0
2 1 1 0 -1 1 0 0 0
3 0 0 -1 1 0 1 -1 -1
4 0 0 0 0 0 -1 1 1
Tabela 1.4: Matriz de incidência do d́ıgrafo da Figura 1.4 (b)
Muitas vezes a matriz de adjacência do grafo é esparsa, ou seja, a mai-
oria dos seus elementos é igual a 0. Neste caso, para um grafo que possui
n vértices, estaŕıamos utilizando um espaço de armazenamento proporcional
a n2, sendo que apenas uma pequena quantidade de memória, associadas às
arestas do grafo, estaria efetivamente sendo usada. Para resolver este pro-
blema, podemos representar a matriz de adjacência na forma de uma lista
de adjacência, onde cada elemento desta lista possui referência a um vértice
do grafo e um ponteiro para uma sub-lista contendo todos os vértices adja-
centes associados. Se considerarmos que a maior sub-lista possui tamanho
igual a c << n (ou seja, c é muito menor que n), então no máximo estaremos
usando um espaço de armazenamento proporcional a cn, que é muito menor
que n2. Entretanto, se a matriz não for esparsa, ou seja, δ(G) ≥ n/2, então
a lista de adjacência não é uma boa escolha. Pois neste caso, a verificação da
adjacência entre dois vértices u e v consistirá em realizar uma busca linear
na sub-lista associada a um dos dois vértices. Se o grafo é muito denso, por
exemplo um Kn, isto envolverá no máximo n comparações. Por outro lado,
esta verificação em uma matriz de adjacência consiste em apenas checar a
entrada correspondente. Se a entrada for igual a 0 então os vértices não
são adjacentes, caso contrário são adjacentes. Estes aspectos relacionados à
eficiência valem também para d́ıgrafos.
1.4 Passeios e Circuitos
Definição 1.5. Em um grafo, um passeio entre os vértices v e w é uma
seqüência alternada de vértices e arestas v = v0, a1, v1, a2, v2, . . . , an, vn = w
que começa em v e termina em w, de forma que cada aresta ai é incidente
aos vértices vi−1 e vi. Tanto as arestas quanto os vértices podem ou não ser
distintos. Se apenas as arestas forem distintas, então o passeio é chamado
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
14 Fundamentação Teórica
de trilha. Se tanto as arestas quando os vértices forem distintos então, ele é
chamado de caminho. Observe que
caminhos ⊂ trilhas ⊂ passeios
Se os vértices de origem e destino forem o mesmo, então o passeio é cha-
mado de passeio fechado; a trilha é chamada de circuito; enquanto que oPasseio Fechado
Circuito caminho é chamado apenas de ciclo. Em um grafo simples, um ciclo é des-
Ciclo crito apenas por seus vértices já que a ordem dos vértices define exatamente
que aresta foi visitada. Um d́ıgrafo possui conceitos similares com a restrição
de que orientação dos arcos deve ser obedecida.
É posśıvel entre um mesmo par de vértices em um grafo G existirem
diversos passeios, trilhas e caminhos. Considerando o grafo da Figura 1.2(b),
entre os vértices 1 e 2 podemos ter os seguintes:
• Passeios:(1, c, 3, d, 2), (1, c, 3, g, 4, h, 3, g, 4, f, 3, d, 2), . . .
• Trilhas: (1, c, 3, d, 2),(1, c, 3, g, 4, h, 3, d, 2), . . .
• Caminhos: (1, c, 3, d, 2),(1, b, 2), . . ..
Dois caminhos entre um par de vértices u e v são vértice-disjuntos (ou
apenas disjuntos) se eles compartilharem apenas os vértices u e v e nenhuma
aresta. De forma similar, dois caminhos entre u e v são chamados aresta-
disjuntos se eles não compartilharem aresta (Definição similar se aplica aos
d́ıgrafos). Estes conceitos são importantes quando estivermos analisando a
conectividade de grafos no Caṕıtulo 3.
Definição 1.6. Em um d́ıgrafo, um passeio direcionado entre os vértices
v e w é uma seqüência alternada de vértices e arcos v = v0, a1, v1, a2, v2
, . . . , an, vn = w que começa em v e termina em w, de forma que cada arco
ai tenha origem em vi−1 e destino em vi. Se apenas as arcos forem distintos,
então o passeio direcionado é chamado de trilha direcionada. Se tanto os
arcos quando os vértices forem distintos então, ele é chamado de caminho
direcionado. Note que
caminhos direcionados ⊂ trilhas direcionadas ⊂ passeios direcionados
Se os vértices de origem e destino forem o mesmo, então o passeio direci-Passeio Direci-
onado Fechado,
Circuito Dire-
cionado, Ciclo
Direcionado
onado é chamado de passeio direcionado fechado; a trilha é chamada de
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.4 Passeios e Circuitos 15
circuito direcionado, enquanto que o caminho é chamado apenas de ciclo
direcionado.
Além destas classificações, temos a noção de semi-caminho, semi-passeio
e semi-trilha. Se considerarmos a seqüência alternada de vértices e arcos
v = v0, a1, v1, a2, v2, . . . , an, vn = w que começa em v e termina em w, um
semi-passeio é aquele onde o arco ai tem origem em vi−1 e destino em vi Semi-Passeio
ou tem origem em vi e destino em vi−1. Se apenas as arcos forem distintos,
então o semi-passeio é chamado de semi-trilha. Se tanto os arcos quando Semi-Trilha
os vértices forem distintos então, ele é chamado de semi-caminho. Note que Semi-Caminho
não precisamos enfatizar que eles são direcionados, já que estes conceitos se
aplicam apenas aos d́ıgrafos. Podemos pensar que em todos os casos, esta-
mos desconsiderando a orientação dos arcos e focando apenas nos caminhos,
passeios e trilhas no grafo subjacente ao d́ıgrafo. Analogamente, podemos
definir semi-passeio fechado, semi-circuito e semi-ciclo.
Em vários momentos, passeios, caminhos e trilhas, direcionadas ou não, Passeio de Espa-
lhamento, Cami-
nho de Espalha-
mento, Trilha de
Espalhamento
serão chamadas de passeio de espalhamento, caminho de espalhamento e tri-
lha de espalhamento, respectivamente. Isto ocorrerá quando estiverem sendo
considerados todos os vértices do d́ıgrafo ou grafo. Por exemplo, na Fi-
gura 1.2(b), o caminho 1, a, 2, d, 3, g, 4 possui todos os vértices do grafo sendo,
portanto, um caminho de espalhamento. Passeio fechado, circuito, e ciclo,
direcionado ou não, são de espalhamento, quando considerarem todos os
vértices do grafo ou d́ıgrafo.
O comprimento de um passeio(ou passeio direcionado) é igual a quanti-
dade quantidade de arestas(ou arcos) entre os vértices inicial e final. Um
caminho(ou caminho direcionado) com n vértices possui n − 1 arestas, logo
seu comprimento é igual a n − 1. Por conseguinte, um ciclo(ou ciclo dire-
cionado) composto por n vértices possui comprimento exatamente igual a
n.
Em grafos simples, os ciclos devem ter comprimento ≥ 3 , enquanto que
em multigrafos, este comprimento deve ser ≥ 2, pois podem existir múltiplas
arestas entre um mesmo par de vértices. Em pseudografos, laços são ciclos
especiais de comprimento igual a 1 chamados de ciclos simples. Para que
haja um ciclo, que não seja simples, o número de vértices tem que ser igual
ao número de arestas.
O comprimento do menor ciclo pertencente a um grafo G é chamado
cintura e denotado por g(G). Enquanto que o comprimento do maior ciclo Cintura
é chamado de circunferência sendo denotado por c(G). Um grafo que não Circunferência
possui ciclos, como por exemplo árvores, tem g(G) = ∞ e c(G) = 0. Uma
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
16 Fundamentação Teórica
aresta ou arco que une dois vértices em um ciclo, mas que não pertence ao
ciclo é chamada corda.Corda
Entre um par de vértices v e w em um grafo(ou d́ıgrafo) G = (V,A),podem existir inúmeros caminhos. Cada caminho representa um subgrafo(ou
subd́ıgrafo) de G, ou seja, considerando Pv,w = (Vp, Ap) um caminho entre
os vértices v e w, temos Pv,w ⊆ G. O comprimento de Pv,w, denotado aqui
por |Pv,w| é igual ao seu número de arestas, i.e., |Pv,w| = |Ap|. Se não existe
caminho entre v e w, então |Pv,w| = ∞. Usando esta notação, a distância
entre v e w é igual a
d(v, w) = min
Pv,w⊆G
|Pv,w|
Note que a distância entre v e w é definida pelo comprimento do menor
caminho entre v e w. Este cálculo é muito importante em áreas como a
robótica, já que o robô deve sempre que posśıvel se deslocar no ambiente
seguindo o caminho de menor comprimento. A partir da informação de
distância, podemos calcular o diâmetro de G porDiâmetro
diam(G) = max
v,w∈V
d(v, w)
que corresponde à distância entre os vértices mais afastados de G, e também
a excentricidade de cada vértice v de G que informa a maior distância posśıvelExcentricidade
entre v e todos os outros vértices do grafo,
e(v) = max
w∈V
d(v, w).
Usando a informação sobre a excentricidade dos vértices é posśıvel calcu-
lar o raio de G porRaio
raio(G) = min
v∈V
e(v)
que indica o menor valor de excentricidade presente em um grafo conside-
rando todos os seus vértices; e reescrever a expressão que define o diâmetro
de G como
diam(G) = max
v∈V
e(v)
A partir dáı, definimos um vértice v como sendo central quando seu valor
de excentricidade é igual ao raio do grafo, i.e., e(v) = raio(G). Por conse-Centro de um
Grafo guinte, o centro de um grafo G, denotado por, C(G), é um subgrafo induzido
pelos seus vértices centrais, i.e.,
C(G) = G[V ′], tal que V ′ = {v ∈ V : e(v) = raio(G)}
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.4 Passeios e Circuitos 17
Figura 1.7: Grafo com diam(G) = 4, raio(G) = 2 e C(G) = G[{2}].
Como exemplo, considere o grafo G mostrado na Figura 1.7. Seus vértices
possuem as seguintes excentricidades:
e(1) = 4, e(2) = 2, e(3) = 4, e(4) = 3, e(5) = 3, e(6) = 3 e e(7) = 4.
O diâmetro e o raio deste grafo são iguais a diam(G) = 4 e raio(G) = 2,
respectivamente. O centro é definido apenas pelo vértice 2, i.e., C(G) =
G[{2}]. Fazendo G′ = G − {1, 4}, i.e., eliminando a aresta {1, 4}, o grafo
passa a ter as seguintes excentricidades :
e(1) = 5, e(2) = 3, e(3) = 4, e(4) = 3, e(5) = 3, e(6) = 4 e e(7) = 5.
O diâmetro e o raio de G′ são iguais a diam(G′) = 5 e raio(G′) = 3, respecti-
vamente. O centro é definido pelos vértices 2, 4 e 5, i.e., C(G) = G[{2, 4, 5}].
Estas informações podem ser utilizadas por um administrador de uma
rede de computadores para saber quais são os nós centrais da rede que estão
com sobrecarga de comunicação, ou os nós mais distantes a fim de aproximá-
los através da inserção de outros pontos de comunicação. Note que uma rede
ideal é aquela onde a comunicação entre pares de computadores ocorre dire-
tamente. Em geral, redes com grandes diâmetros são mais lentas do ponto de
vista de comunicação do que redes com baixos diâmetros. Entretanto, uma
rede deste tipo é aceitável se a maioria dos seus computadores se comunicar
através de conexões de curta distância. Portanto, convém avaliar uma rede
não apenas pelo seu diamêtro, mas pela distância média entre pares de com-
putadores. Isto leva ao ı́ndice de Wiener definido para um grafo G = (V,A) Índice
de Wienerpor
W (G) =
∑
u,v∈V
d(u, v)
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
18 Fundamentação Teórica
Este valor não corresponde a uma distância média pois não está sendo
dividido pelo número de pares posśıveis dado por
(
|V |
2
)
. Entretanto, esta
medida é válida pois para redes com mesmo número de nodos, a quantidade
posśıvel de pares é a mesma independente da topologia da rede. Logo, o
número de pares pode ser suprimido do cálculo.
1.5 Grafos Eulerianos e Hamiltonianos
Como visto anteriormente no ińıcio deste caṕıtulo, o primeiro e mais famoso
problema na área de Teoria dos Grafos é chamado o problema das pontes de
Königsberg. Ele foi enunciado por Euler em 1736 e consistia em determinarProblema das
Pontes de
Königsberg
se era posśıvel ou não fazer um passeio pela cidade Königsberg começando e
terminando no mesmo lugar, cruzando cada ponte exatamente uma única vez.
A Figura 1.1 mostra as sete pontes que cruzavam o rio Pregel estabelecendo
ligações entre diferentes partes da cidade e as ilhas Kneiphof e Lomse.
O grafo associado ao mapa mostrado na Figura 1.1 é ilustrado na Fi-
gura 1.8. Note que cada aresta é rotulada com uma das pontes mostradas na
Figura 1.1 enquanto que os vértices de v1 a v4 estão associados às diferentes
partes da cidade. O problema então consiste em determinar se é posśıvel ou
não fazer um circuito pelo grafo cruzando cada aresta uma única vez. Se
isto for posśıvel, então o grafo é chamado de grafo euleriano e ao circuito é
dado o nome de circuito euleriano. A principal caracteŕıstica que define umCircuito Euleri-
ano multigrafo euleriano é dada pelo seguinte Teorema.
Figura 1.8: Multigrafo associado ao mapa mostrado na Figura 1.1.
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.5 Grafos Eulerianos e Hamiltonianos 19
Teorema 1.5 (Teorema dos Multigrafos Eulerianos). Um multigrafo conexo
G = (V,A) é Euleriano sse todos os vértices de G tiverem grau par. Multigrafos Eu-
lerianos
A demonstração deste teorema, deixada como exerćıcio, além de mostrar
que todo multigrafo Euleriano é um multigrafo par, i.e., possui todos os seus Multigrafo Par
vértices com grau par, mostra também que todo multigrafo par pode ser
decomposto em circuitos. O problema de verificar se um multigrafo possui ou
não um circuito Euleriano está intimamente relacionado a outros problemas
na área de teoria dos grafos, como o problema do Carteiro Chinês. Neste Problema do
Carteiro Chinêsproblema, o carteiro deve entregar cartas da forma mais eficiente posśıvel
visitando cada rua apenas uma única vez. Se o grafo subjacente à região de
entrega das cartas for euleriano então qualquer circuito Euleriano escolhido
será ótimo, porém se o grafo não for euleriano, o carteiro deverá encontrar
um passeio fechado de custo mı́nimo revistando algumas das arestas do grafo.
Se mudarmos sutilmente o problema e ao invés de tentarmos encontrar
um circuito euleriano, tentarmos encontrar uma trilha euleriana, ou seja,
uma trilha que começa em um vértice v e termina em um vértice u passando
por cada aresta do multigrafo uma única vez, seremos levados ao seguinte
teorema.
Teorema 1.6 (Teorema de Multigrafos Semi-Eulerianos). Um multigrafo co-
nexo G = (V,A) possui uma trilha euleriana e consequentemente é chamado Multigrafos
Semi-Eulerianosde semi-euleriano sse tem no máximo dois vértices de grau impar.
A Figura 1.9 ilustra em (a) um grafo euleriano e em (b) um grafo semi-
euleriano. Em (b), as trilhas Eulerianas obrigatoriamente começam em um
dos vértices de grau ı́mpar (vértices cinza), e terminam no outro vértice de
grau ı́mpar (Verifique!).
(a) (b)
Figura 1.9: Exemplo de grafo (a) Euleriano e (b) Semi-Euleriano.
De forma similar aos multigrafos não direcionados, um multigrafo dire-
cionado é euleriano se ele tiver um circuito direcionado euleriano. Note que
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
20 Fundamentação Teórica
embora estejamos fazendo referência a multigrafos direcionados, o teorema
se aplica a pseudografos direcionados, já que estes são diferentes dos multi-
grafos direcionados apenas pela presença de laços. Assim, similarmente ao
Teorema 1.5, temos o seguinte teorema
Teorema 1.7 (Teoremados Multigrafos Direcionados Eulerianos). Um mul-
tigrafo direcionado conexo D = (V,A) é euleriano sse para qualquer vértice
v ∈ V , temos d+(v) = d−(v), i.e, o grau de entrada de v é igual ao seu grau
de sáıda.
A Figura 1.10 mostra o pseudografo direcionado euleriano, comumente
chamado de d́ıgrafo de Bruijn.Dı́grafo de
Bruijn
Figura 1.10: Pseudografo direcionado euleriano - d́ıgrafo de Bruijn.
Se ao invés de focarmos nossa atenção nas arestas ou arcos, focarmos
nos vértices, teremos um outro tipo de problema, que embora aparentemente
seja mais simples, já que ele foca na visita dos vértices e não nas visitas das
arestas ou arcos, é muito mais complexo e que não possui solução eficiente.
Este problema é chamado problema do ciclo hamiltoniano.
Definição 1.7. Um multigrafo é hamiltoniano se ele possuir um ciclo hamil-
toniano, ou seja, um ciclo de espalhamento.Ciclo Hamiltoni-
ano
Um ciclo de espalhamento possui todos os vértices do multigrafo, o qualCiclo de Espa-
lhamento pode ser direcionado ou não. No caso do multigrafo direcionado, um ciclo ha-
miltoniano será um ciclo direcionado. A primeira pessoa a estudar este tipo
de estrutura foi o matemático irlandês Sir W. R. Hamilton. A Figura 1.11
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.5 Grafos Eulerianos e Hamiltonianos 21
mostra um exemplo de grafo hamiltoniano, com o ciclo hamiltoniano desta-
cado em vermelho. Este grafo foi a base do jogo chamado Dodecaedro do
Viajante concebido por Sir. Hamilton.
Figura 1.11: Grafo Hamiltoniano.
O problema do ciclo hamiltoniano está intimamente relacionado ao pro-
blema do caixeiro viajante, o qual consiste em encontrar um ciclo de custo Problema do
Caixeiro Via-
jante
mı́nimo que passe por uma série de cidades uma única vez retornando à
cidade de partida. Observe que este problema é muito mais dif́ıcil do que
simplesmente verificar se o grafo associado é hamiltoniano ou não, pois en-
volve a análise de todos os posśıveis ciclos hamiltonianos em busca do ciclo
de menor custo.
Se o multigrafo em análise não contiver um ciclo hamiltoniano, mas con-
tiver um caminho hamiltoniano, ou seja, um caminho que passe por to-
dos vértices do multigrafo porém com o vértice de chegada diferente do
vértice de destino então a este multigrafo é dado o nome de multigrafo
semi-hamiltoniano. Para multigrafos ou pseudografos direcionados, o ca- Multigrafo
Semi-
Hamiltoniano
minho hamiltoniano deve ser direcionado. A Figura 1.12 ilustra um grafo
semi-hamiltoniano. O caminho destacado em vermelho é um caminho ha-
miltoniano. Se existisse uma aresta entre os vértices v e u, este grafo seria
hamiltoniano. Este grafo também é semi-euleriano.
Diferentemente dos grafos eulerianos, não existem condições necessárias
e suficientes para caracterizar um grafo genérico como hamiltoniano ou não.
Alguns resultados são apresentados abaixo
Teorema 1.8 ([2]). Um grafo G = (V,A) com |V | ≥ 3 é hamiltoniano se
δ(G) ≥ |V |/2
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
22 Fundamentação Teórica
Figura 1.12: Grafo Semi-Hamiltoniano.
Teorema 1.9 ([3]). Um grafo G = (V,A) com |V | ≥ 3 é hamiltoniano se
para todo par v e u de vértices não adjacente d(v) + d(u) ≥ |V |.
1.6 Isomorfismo e Automorfismo
Muitas vezes nos deparamos com grafos diferentes mas que possuem a mesma
estrutura, i.e., um poderia estar associado à relação ecológica de diferentes
seres vivos enquanto outro poderia estar associado à relação entre átomos
de um composto qúımico. A identificação e verificação se eles possuem ou
não a mesma estrutura, i.e., se um pode ser mapeado no outro, é muito
relevante para diversos tipos de problemas. Já que se este mapeamento
existe então podemos dizer que estes grafos possuem as mesmas propriedades.
Assim, se um grafo G com propriedades conhecidas consegue ser mapeado
para um grafo D desconhecido, então podemos dizer que D possui as mesmas
propriedades que G. Estas propriedades podem dizer respeito a aspectos
relacionados à planaridade, coloração, cobertura de vértices, entre outros.
Definição 1.8. Dois grafos G1 = (V1, A1) e G2 = (V2, A2) são isomorfos, i.e.,
G1 ∼= G2, se existe uma função bijetora f : V1 → V2, tal que (u, v) ∈ A1 sse
(f(u), f(v)) ∈ A2.
Grafos isomorfos apresentam as mesmas propriedades estruturais que pre-
servam a adjacência entre seus vértices. Por exemplo, os grafos ilustrados
na Figura 1.13 são diferentes entretanto apresentam as mesmas propriedades
estruturais. A Tabela 1.5 mostra um posśıvel mapeamento dos vértices de
G1 para os vértices de G2. Isso faz com que a aresta (0, 5) ∈ A1 seja mapeada
para a aresta (e, d) ∈ A2, e a aresta (0, 4) ∈ A1 seja mapeada para a aresta
(e, c) ∈ A2. Cada aresta em G1 possui uma aresta correspondente em G2
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.6 Isomorfismo e Automorfismo 23
(Verifique!). Se pelo menos uma das aresta de G1 não possuir uma corres-
pondente em G2 então a função escolhida não define o isomorfismo entre G1
e G2. Notem que existem inúmeros mapeamentos posśıveis. Outro mape-
amento posśıvel que garante o isomorfismo entre G1 e G2 é a partir desta
tabela alterar as linhas 3 e 4, associando o vértice 2 ao vértice f e o vértice
3 ao vértice a.
(a) (b)
Figura 1.13: Exemplo de grafos isomorfos. O grafo (a) G1 é isomórfico ao
grafo (b) G2 .
Assim entre os requisitos básicos para que dois grafos sejam isomorfos
é que eles possuam a mesma quantidade de vértices e a mesma quantidade
de arestas, i.e., |V1| = |V2| e |A1| = |A2|. Porém verificar se dois grafos
são ou não isomorfos nem sempre é uma tarefa trivial. Suspeita-se que este
problema seja NP-Completo.
V1 V2
0 e
1 b
2 a
3 f
4 c
5 d
Tabela 1.5: Matriz de incidência do d́ıgrafo da Figura 1.4 (b)
Um fato importante é que a função de isomorfismo define uma relação de
equivalência possui as seguintes propriedades:
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
24 Fundamentação Teórica
• Propriedade reflexiva. Uma permutação da identidade dos vértices de
um grafo G1 leva a um grafo G2 que é isomorfico a G1, i. .e, G1 ∼= G2
• Propriedade simétrica. Sejam G1 = (V1, A1) e G2 = (V2, A2), se a
função f : V1 → V2 é uma função que define o isomorfismo entre
G1 e G2, então f
−1 é a função inversa que define o isomorfismo en-
tre G2 e G1. Logo (u, v) ∈ A1 sse (f(u), f(v)) ∈ A2 e (x, y) ∈ A2 sse
(f−1(x), f−1(y)) ∈ A1.
• Propriedade Transitiva. Sejam G1 = (V1, A1), G2 = (V2, A2) e G3 =
(V3, A3), e as funções f : V1 → V2 e h : V2 → V3 sejam funções que
definam a relação de isomorfismo entre os grafos G1 e G2; e G2 e G3,
respectivamente. Como (u, v) ∈ A1 sse (f(u), f(v)) ∈ A2 e (x, y) ∈ A2
sse (h(x), h(y)) ∈ A3, se (x, y) ∈ A2, então existe uma aresta (u, v) ∈ A1
tal que f(u) = x e f(v) = y. Logo, (u, v) ∈ A1 sse (h(f(u)), h(f(v))) ∈
A3. Portanto, a função composta h ◦ f define a relação de isomorfismo
entre G1 e G3, ou seja, G1 ∼= G3.
Logo, a função de isomorfismo define uma classe de equivalência para um
conjunto de grafos, onde dois grafos pertencem a mesma classe sse eles são
isomorfos. Um exemplo de classe isomórfica é a classe chamada “grafos de
Petersen” . Um grafo pertencente a esta classe é ilustrado na Figura 1.14(a).Grafo de
Petersen Este grafo possui vértices que estão associados a subconjuntos de dois elemen-
tos formado a partir do seguinte conjunto S = {1, 2, 3, 4, 5}. Dois vértices são
adjacentes se seus subconjuntos correspondentes forem disjuntos, por exem-
plo, os vértices associados aos subconjuntos {1, 2} e {3, 4} são adjacentes.
Note que o grafo da Figura 1.14(b) éisomorfo ao grafo (a). Grafos de Pe-
tersen são comumente usados como contra-exemplos em provas de teoremas
devido às suas propriedades, as quais serão apresentadas mais adiante. Note
que os grafos ilustrados na Figura 1.14 são formados por dois ciclos disjuntos
de tamanho 5 destacados em preto e vermelho.
A noção de isomorfismo se aplica a multigrafos direcionados, porém ela é
focada na multiciplidade dos arcos dos grafos envolvidos.
Definição 1.9. Dois multigrafos direcionados M1 = (V1, A1) eM2 = (V2, A2)Isomorfismo de
Multigrafos Di-
recionados
são isomorfos, i.e., M1 ∼= M2, se existe uma função bijetora f : V1 → V2, tal
que µ(u, v) = µ(f(u), f(v)), onde (u, v) ∈ A1, (f(u), f(v)) ∈ A2 e µ(u, v) é a
multiplicidade do arco (u, v).
Outro conceito associado ao isomorfismo é o automorfismo.
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.6 Isomorfismo e Automorfismo 25
(a) (b)
Figura 1.14: Grafo de Petersen. O grafo (a) G1 é isomórfico ao grafo (b) G2.
Definição 1.10. Um automorfismo de um grafo G = (V,A) é uma per- Automorfismo
mutação dos vértices de G definida por uma função f : V → V de forma que
para cada aresta (v, u) ∈ A implica (f(v), f(u)) ∈ A. Ou seja, a permutação
definida por f não muda a adjacência entre os vértices de G.
Considere um grafo G = (V,A), ilustrado a partir de sua matriz de ad-
jacência mostrada na Tabela 1.6, constitúıdo do seguinte conjunto de vértices
V = {1, 2, 3, 4} e do seguinte conjunto de arestas A = {(1, 2), (2, 3), (3, 4)}.
Se permutarmos os vértices de V fazendo com que o vértice 1 passe a ser o
vértice 4, e o vértice 2 passe a ser o vértice 3, teremos a matriz de adjacência
ilustrada na Tabela 1.7. Reordenando as linhas e colunas desta matriz en-
contramos a matriz original mostrada na Tabela 1.6.
Se por ventura permutarmos apenas o vértice 1 com o vértice 4 mantendo
os vértices 2 e 3 como estão não teremos um automorfismo de G. Esta per-
mutação é ilustrada na Tabela 1.8. Se reordenarmos as linhas e colunas desta
matriz não obteremos a matriz original mostrada na Tabela 1.6 (Verifique!).
Embora este mapeamento leve a um grafo isomorfo ao grafo original, ele não
define um automorfismo. Isto decorre do fato que o conjunto de arestas ge-
rado é {(4, 2), (2, 3), (1, 3)} o que é diferente do conjunto de arestas original,
já que o vértice 4 não era adjacente ao vértice 2 no grafo original.
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
26 Fundamentação Teórica
1 2 3 4
1 0 1 0 0
2 1 0 1 0
3 0 1 0 1
4 0 0 1 0
Tabela 1.6: Matriz de adjacência do Grafo G=(V,A), com V = {1, 2, 3, 4},
A = {(1, 2), (2, 3), (3, 4)})
4 3 2 1
4 0 1 0 0
3 1 0 1 0
2 0 1 0 1
1 0 0 1 0
Tabela 1.7: Matriz de adjacência resultante da permutação dos vértices de
grafo ilustrado na Tabela 1.6.
1.7 Aplicações
Esta seção apresenta alguns exemplos de aplicações do mundo real que en-
volvem Grafos.
1.7.1 Associação de Tarefas
Uma empresa precisa distribuir um conjunto de n tarefas T entre seus n
empregados E, considerando que cada empregado j consegue realizar cada
tarefa i em um dado tempo mij. Qual é a melhor associação entre tarefa e
empregado de forma a minimizar o tempo de realização de todas as tarefas.
Uma instância do problema é mostrada no grafo da Figura 1.15(a). Para faci-
litar a visualização os tempos mij não foram apresentados. A Figura 1.15(b)
mostra a associação escolhida através de arestas mais grossas.
Este problema é um t́ıpico problema de emparelhamento, onde tanto as
tarefas quanto os empregados são os vértices do grafo, e as arestas correspon-
dem a associação entre os empregados e as tarefas. Cada aresta é rotulada
com o tempo de realização da tarefa pelo empregado ao qual está associ-
ada. O objetivo é encontrar a melhor associação entre tarefas e empregados
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.7 Aplicações 27
4 2 3 1
4 0 1 0 0
2 1 0 1 0
3 0 1 0 1
1 0 0 1 0
Tabela 1.8: Matriz de adjacência resultante da permutação apenas dos
vértices 1 e 4 de G.
de forma a minimizar a soma dos tempos de realização de todas as tare-
fas. Como não existem arestas entre os empregados nem entre as tarefas,
temos dois conjuntos compostos por vértices não adjacentes entre si. Con-
juntos com esta caracteŕıstica são chamados de conjuntos independentes e
serão discutidos apropriadamente no Caṕıtulo 4.2.
1.7.2 Robótica
Vários problemas da área de robótica estão associados às tarefas de navegação
de robôs em ambientes do tipo escritório. Neste tipo de tarefa, o robô pos-
sui um mapa do ambiente e deve planejar um caminho que o leve de uma
posição a outra evitando colisões com obstáculos. Entre os diversos tipos de
mapas, existe o mapa topológico, que consiste em uma representação do am-
biente utilizando grafos. A Figura 1.16(a) mostra um ambiente e seu grafo
subjacente. Os vértices estão associados às grandes regiões do ambiente e as
arestas indicam como navegar entre estas regiões. Neste exemplo, se o robô
precisar ir da sala A até a sala G, ele pode seguir por vários caminhos, que
podem ser visualizados através dos vértices e arestas do grafo associado. A
Figura 1.16(b) mostra um caminho posśıvel através de arestas mais grossas.
1.7.3 Nichos Ecológicos
Grafos podem ser usados para modelar o relacionamento competitivo en-
tre diferentes espécies de animais em um ecosistema. A competição ocorre
quando indiv́ıduos de uma mesma espécie ou de espécies diferentes disputam
por algum recurso, como por exemplo, alimento. Quando a competição é
grande e desigual, uma espécie pode mudar seus hábitos, migrar para outra
região ou até mesmo ser extinta. Logo, estudar o relacionamento entre as
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
28 Fundamentação Teórica
(a) (b)
Figura 1.15: Associação de tarefas ti ∈ T aos empregados ej ∈ E. (a)
todas as associações (b) a associação escolhida, representada por arestas mais
grossas.
espécies é fundamental para a preservação do ecossistema. Usando grafos,
cada espécie pode ser modelada como um vértice e a competição entre duas
espécies é indicada no grafo através de uma aresta entre os vértices corres-
pondentes. A Figura 1.17 mostra um grafo que modela o relacionamento
competitivo entre diferentes espécies do ecosistema de uma floresta.
1.7.4 Rede de Telefonia Móvel
Veremos no Caṕıtulo 8 que um mapa pode ser desenhado no plano e colorido
propriamente com apenas quatro cores, ou seja, regiões vizinhas possuem
cores diferentes. Para que isto seja posśıvel, as regiões do mapa são associadas
aos vértices do grafo enquanto que a adjacência entre as regiões define as
arestas entre os vértices correspondentes. A partir dáı, cada vértice é colorido
de forma que vértices adjacentes tenham cores distintas. Em um primeiro
instante, pode-se pensar em usar uma cor diferente para cada vértice, porém
problemas de coloração de grafos são problemas de otimização, onde a adição
de uma nova cor implica aumento de custos. Logo, busca-se sempre a menor
quantidade de cores posśıvel.
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.7 Aplicações 29
Em 1982, o Groupe Spécial Mobile (GSM) foi criado para desenvolver um
padrão a ser adotado pela telefonia móvel, e em 1991 surgiu a primeira rede
GSM na Finlândia com o apoio da Ericsson. As redes GSM dividem as suas
regiões de cobertura em células hexagonais. Cada célula possui uma torre de
comunicação que gerencia a conexão dos celulares na sua área de cobertura.Os celulares por sua vez procuram células em sua vizinhança imediata de
acordo com sua freqüência de operação. Células adjacentes que possuem
mesma freqüência devem ser evitadas pois uma gera interferência no sinal
da outra. Este fato faz com que o uso de coloração de grafos, em especial
a coloração de mapas, tenha aplicabilidade direta. Por isso, as redes GSM
usam apenas quatro freqüências diferentes devido serem necessárias apenas
quatro cores para colorir propriamente o mapa das regiões das células. Neste
caso, as cores são representadas pelas freqüências de operação.
1.7.5 Reconhecedores de sentenças
Uma máquina teórica para reconhecer sentenças de uma linguagem, como
autômatos finitos determı́nisticos ou finitos não determińısticos, é represen-
tada graficamente através de um d́ıgrafo. Neste d́ıgrafo os vértices represen-
tam os estados da máquina enquanto que os arcos representam as transições
da máquina de um estado para o outro. Por exemplo, o d́ıgrafo da Figura 1.18
representa um autômato finito determińıstico capaz de reconhecer sentenças
formadas pelos śımbolos a e b com uma quantidade ı́mpar de a’s e uma quan-
tidade ı́mpar de b’s. Os vértices são representados por S1, S2, S3 e S4 e os
arcos têm origem e destino neste conjunto. Note que a seta que não possui
origem em um destes estados e tem destino em S1, tem a função apenas de
indicar o estado inicial da máquina, portanto não é um arco do d́ıgrafo.
1.7.6 Redes Neurais Artificiais
Uma rede neural artificial é um modelo computacional utilizado na área de
Inteligência Artificial para simular o funcionamento do cérebro humano. Ela
é representada graficamente na forma de um d́ıgrafo, onde cada vértice cor-
responde a um neurônio artificial e os arcos representam as conexões entre
os neurônios, chamadas sinapses. As sinapses possuem um peso associado
que pondera o sinal que flui entre os neurônios. Existem inúmeras formas de
organização destes neurônios sendo a mais comum a estrutura multicamada
mostrada na Figura 1.19. Nela a rede é organizada em camada de entrada,
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
30 Fundamentação Teórica
camadas escondidas e camada de sáıda. Na figura, estas camadas são re-
presentadas pelas letras A, B e C, respectivamente. O sinal flui da camada
de entrada até a camada de sáıda de acordo com a orientação das sinapses.
Portanto, o padrão de entrada é fornecido para a rede na camada de entrada
e a rede produz um padrão de sáıda. O padrão de entrada poderia ser a
postura (x, y, θ) de um robô em um ambiente e a sáıda poderia ser a variação
angular ϕ a ser aplicada em suas rodas dianteiras para fazê-lo atingir uma
posição destino.
1.8 Exerćıcios
Exerćıcio 1.1. Mostre usando prova por indução que a soma total dos graus
de todos os vértices de um grafo é sempre par
Exerćıcio 1.2. Mostre que para qualquer grafo, o número de vértices com
grau ı́mpar é par.
Exerćıcio 1.3. Verifique se a seqüência de graus 3, 3, 3, 3, 3, 2, 2, 1 é gráfica.
Se for desenhe o grafo simples correspondente.
Exerćıcio 1.4. Dado um grafo simples G = (V,A), com |V | = n qual é o
significado de
∑n
j=1 ai,j para uma dada linha i da matriz de adjacência de G?
Exerćıcio 1.5. Sendo M a matriz de adjacência de um grafo G, qual é o
significado combinatorial de M2, ou seja, do produto M.M?
Exerćıcio 1.6. Mostre que todo passeio de v até w contém um caminho de
v até w.
Exerćıcio 1.7. Mostre que todo grafo G simples com um caminho de compri-
mento δ(G) ≥ 2 possui um ciclo de comprimento igual a no mı́nimo δ(G)+1.
Exerćıcio 1.8. Mostre que se D é um d́ıgrafo com δ+(D) ≥ 1 (ou δ−(D) ≥
1), então D contém um ciclo.
Exerćıcio 1.9. Mostre que um grafo G de raio(G) ≤ k e ∆(G) ≥ 3 tem um
número de vértices inferior a 1 + ∆(G)
∆(G)−2(∆(G)− 1)
k.
Exerćıcio 1.10. Mostre que com um conjunto de n vértices distintos é
posśıvel gerar 2
(
n
2
)
grafos simples.
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.8 Exerćıcios 31
Exerćıcio 1.11. Mostre que todo d́ıgrafo aćıclico(sem ciclos) possui vértice
fonte e um vértice sumidouro.
Exerćıcio 1.12. Mostre que um grafo simples G = (V,A) com δ(G) > 0 e
|A| < |V | possui pelo menos dois vértices de grau 1.
Exerćıcio 1.13. Mostre que todo grafo com dois ou mais vértices tem pelo
menos dois vértices de mesmo grau.
Exerćıcio 1.14. Mostre que um multigrafo conexo G = (V,A) é Euleriano
sse o grau de todos os vértices de G for par.
Exerćıcio 1.15. Mostre que dois vértices não adjacentes em um grafo de
Petersen tem exatamente 1 vizinho em comum.
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
32 Fundamentação Teórica
(a)
(b)
Figura 1.16: Mapa topológico de um ambiente do tipo escritório. (a) mostra o
ambiente e o mapa topológico na forma de um grafo (b) destacada o caminho
escolhido para ir da sala A até a sala G.
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
1.8 Exerćıcios 33
Figura 1.17: Relacionamento competitivo entre espécies. Figura traduzida
do Livro [4].
Figura 1.18: Representação gráfica de um autômato finito determińıstico
para reconhecer sentenças.
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
34 Fundamentação Teórica
Figura 1.19: Rede neural multicamada composto por 1 camada de entrada,
1 camada oculta e 1 camada de sáıda.
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
Caṕıtulo 2
Tipos de Grafos e Operações
Este caṕıtulo apresenta diversos tipos especiais de grafos e a notação utili-
zada, algumas operações unárias e binárias e exemplos de aplicações. Ini-
cialmente, apresentamos conceitos referentes a grafos completos, vazios, to-
talmente desconexo, entre outros. Em seguida, serão apresentadas algumas
operações como complemento, união, remoção de vértices e arestas.
2.1 Grafos Especiais
Esta seção apresenta algumas classes de grafos comumente usados em diversas
aplicações e também como contra-exemplos.
Grafo Trivial
Um grafo trivial é um grafo com 1 ou nenhum vértice. Quando o grafo não
possui vértices, ele é chamado de grafo vazio. Este tipo de grafo é tipicamente Grafo Vazio
usado como passo inicial em provas por indução e como contra exemplo em
alguns tipos de problemas.
Grafo Totalmente Desconexo
Um grafo totalmente desconexo não possui arestas unindo seus vértices.
Grafo Completo ou Totalmente Conexo
Um grafo completo com n vértices, denotado por Kn, é um grafo simples
que possui uma aresta entre qualquer par de vértices. Devido a isto, este
grafo possui exatamente 1
2
n(n − 1) arestas. A Figura 2.1 mostra alguns
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
36 Tipos de Grafos e Operações
grafos completos com (a) 4 (b) 3 (c) 2 e (d) 1 vértices.
(a) (b) (c) (d)
Figura 2.1: Grafos Completos (a)K4 (b) K3 (c) K2 e (d) K1.
Uma definição similar pode ser aplicada aos d́ıgrafos. Um d́ıgrafo é com-
pleto se para qualquer par de vértices x e y, como x 6= y existem os doisDı́grafo Com-
pleto arcos simétricos (x, y) e (y, x). Vários autores usam a mesma notação de
grafo completo para d́ıgrafo completo, ou seja, Kn para um d́ıgrafo ou grafo
completo com n vértices. Neste livro adotaremos esta prática e enfatizaremos
se Kn refere-se a um d́ıgrafo ou a grafo. Um d́ıgrafo é semicompleto se paraDı́grafo Semi-
completo cada par de vértices distintosx e y, existe ou o arco (x, y) ou o arco (y, x)
ou ambos.
Grafo Regular
Um grafo G = (V,A) é regular de ordem r se todos os seus vértices
tiverem o grau r, ou seja, ∀v ∈ V,
δ(G) = ∆(G) = d(v) = r
Este tipo de grafo também é chamado de grafo r-regular. Note que todo
grafo completo Kn é um grafo (n− 1)-regular.
Grafo caminho
Um grafo G = (V,A) é um grafo caminho, Pn, composto por n vértices
se ele corresponder a exatamente um caminho de comprimento n− 1. Neste
caso, os vértices inicial e final do caminho possuem grau igual a 1, enquanto
que os demais possuem grau igual a 2.
Grafo Ciclo
Um grafo ciclo Cn, com n ≥ 3, é composto por n vértices e n arestas que
juntos formam um ciclo de tamanho n. Todos os vértices de Cn possuem
grau igual a 2, logo, ele é um grafo 2-regular. A Figura 2.1(b) mostra um
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
2.1 Grafos Especiais 37
grafo completo K3 que é também um grafo ciclo C3. A Figura 2.2 mostra os
grafos (a) C4, (b) C5 e (c) C6 .
(a) (b) (c)
Figura 2.2: Grafos Ciclo (a) C4 (b) C5 e (c) C6.
Grafo Roda
Um grafo roda Wn, com n ≥ 3, é igual ao grafo Cn adicionado de mais
um vértice, o qual é adjacente a todos os demais. Um grafo Wn possui n+ 1
vértices e 2n arestas, onde o vértice adicionado ao Cn possui grau igual a n
e os demais vértices grau igual a 3. A Figura 2.3 mostra os grafos (a) W4 e
(b) W5.
(a) (b)
Figura 2.3: Grafos Roda (a) W4 e (b) W5.
Grafo Estrela
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
38 Tipos de Grafos e Operações
Um grafo estrela Sn, com n > 1, é igual a um grafo Wn sem as arestas
que compõem o grafo Cn. Um grafo Sn possui n+1 vértices e n arestas, onde
o vértice central possui grau igual a n, enquanto que os demais vértices grau
possuem igual a 1. A Figura 2.4 mostra os grafos (a) S3 e (b) S5.
(a) (b)
Figura 2.4: Grafos Estrela (a) S3 e (b) S5.
Grafo k-cubo
Um grafo k-cubo, ou hipercubo k-dimensional, denotado por Qk, é um
grafo cujos vértices são formados por seqüências binárias de tamanho k. Dois
vértices são adjacentes neste grafo se suas seqüências correspondentes diferi-
rem em apenas uma posição. Além disso, ele é um grafo regular de grau k.
A Figura 2.5 mostra (a) um grafo Q1 (b) um grafo Q2 e (c) um grafo Q3 .
(a) (b) (c)
Figura 2.5: Grafos k-Cubo (a) Q1 (b) Q2 e (c) Q3.
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
2.2 Operações com grafos 39
2.2 Operações com grafos
Em diversos momentos, é necessário realizar algumas operações em grafos
isolados ou pares de grafos. Elas podem ser desde operações para remoção
de vértice/aresta até contrações. Abaixo, apresentamos as operações co-
mumente utilizadas. Nas definições, utilizaremos os seguintes grafos G =
(V,A, φ), G1 = (V1, A1, φ1) e G2 = (V2, A2, φ2). Como na maioria das vezes,
a função de incidência φ destes grafos será a função identidade, então ela será
omitida por conveniência.
2.2.1 União
Dados dois grafos (ou d́ıgrafos) G1 e G2, definimos a operação de união
por G1 ∪ G2. O grafo resultante G = (V1 ∪ V2, A, φ), tem seu conjunto de
vértices oriundo da união dos conjuntos de vértices dos grafos originais. Por
outro lado, o conjunto de arestas A inicialmente é igual a A1, i.e., A = A1 e
φ(e) = φ1(e) ∀e ∈ A1. Cada aresta e′ ∈ A2 deve analisada cuidadosamente
antes de ser inserida em A, pois uma aresta rotulada e′ pode pertencer tanto
a A2 quanto a A1 com φ1(e) pode ser diferente de φ2(e). Sendo assim, para
cada e′ ∈ A2, temos as seguintes situações
• se e′ /∈ A, adicionamos e′ em A e assumimos φ(e′) = φ2(e′).
• se e′ ∈ A e φ(e′) 6= φ2(e′), criamos uma nova aresta em A para e′, por
exemplo e′′ e a adicionamos em A fazendo φ(e′′) = φ2(e
′).
A Figura 2.6(c) ilustra a união de dois grafos (a) G1 e (b) G2.
(a) (b) (c)
Figura 2.6: A aplicação da operação de união dos grafos (a) G1 e (b) G2
resulta no grafo (c) G = G1 ∪G2.
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
40 Tipos de Grafos e Operações
2.2.2 Junção
A operação de junção, representada por + ou ∗, é efetuada em dois grafos G1
e G2 com conjuntos disjuntos de vértices e gera um novo grafo G = G1 +G2,
onde G = (V,A), V = V1 ∪ V2 e A = A1 ∪ A2 ∪ A3, onde A3 é formado
por todos pares não ordenados {v, w}, onde v ∈ V1 e w ∈ V2. Note que
|V | = |V1|+ |V2| e |A| = |A1|+ |A2|+ |V1||V2|. A Figura 2.7 ilustra a junção
dos grafos G1 e G2 produzindo o grafo G. As arestas mais grossas em (c) são
as arestas novas, enquanto que as arestas mais finas são as arestas originais
de G1 e G2.
(a) (b) (c)
Figura 2.7: A aplicação da operação de junção os grafos (a) G1 e (b) G2
resulta no grafo (c) G = G1 +G2.
2.2.3 Intersecção
A intersecção de dois grafos G1 com G2 é denotada por G1 ∩ G2 e gera
um grafo G = G1 ∩ G2, onde G = (V1 ∩ V2, A1 ∩ A2). Note que G possui
conjuntos de vértices e de arestas que pertencem tanto a G1 quanto a G2. Se
G = ∅ então G é um grafo trivial (ver Seção 2.1), caso contrário se V1 ⊂ V2
e A1 ⊂ A2, então G = G1, tendo G1 como subgrafo de G2. A Figura 2.8
ilustra a intersecção de G1 e G2 produzindo G = G1 ∩G2.
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
2.2 Operações com grafos 41
(a) (b) (c)
Figura 2.8: Operação de intersecção dos grafos (a) G1 e (b) G2 resulta no
grafo (c) G = G1 ∩G2.
2.2.4 Produto
O produto de dois grafos, G1 e G2, é denotado por G1 ×G2 e gera um grafo
G = G1 × G2, onde V = V1 × V2 é o conjunto de todos os pares formados
pelos vértices de V1 e V2 e A é o conjunto de arestas geradas da seguinte
maneira. Considere pi = (ui, wi) e pj = (uj, wj) dois vértices do conjunto V ,
i.e., pi, pj ∈ V , onde ui, uj ∈ V1 e wi, wj ∈ V2. Eles são adjacentes se ui = uj
e (wi, wj) ∈ A2 ou wi = wj e (ui, uj) ∈ A1. O grafo G resultante possui
|V | = |V1||V2| vértices e |A| = |V1||A2|+ |V2||A1| arestas.
A Figura 2.9 mostra (c) o grafo resultante do produto dos grafos (a) e
(b). Note que os vértices em (c) são os pares ordenados dos vértices dos
grafos (a) e (b), enquanto que as arestas foram geradas a partir da análise
dos componentes dos pares associados às suas extremidades. Por exemplo,
a aresta {(u1, w1), (u1, w2)} existe pois os primeiros componentes dos pares
(u1, w1) e (u1, w2) são iguais e existe aresta entre w1 e w2 no grafo mostrado
em (b).
2.2.5 Complemento
O complemento de um grafo G = (V,A), denotado por Ḡ = (V,A1) é um
grafo cujo conjunto de vértices é o mesmo de G, e com um conjunto de arestas
definido da seguinte maneira A1 = {{u, v} : ({u, v} ∈ P(V )−A)∧ (u 6= v)},
ou seja, o conjunto A1 é formado por todas as arestas que correspondem aos
pares não ordenados que não pertencem ao conjunto de arestas de G e não
correspondem a laços. O complemento de um grafo Kn é um grafo com n
vértices totalmente desconexo, e o complemento de um grafo desconexo de n
This work is licensed under CC BY-NC-SA 4.0. To view a copy of this
license, visit https://creativecommons.org/licenses/by-nc-sa/4.0
42 Tipos de Grafos e Operações
(a) (b) (c)
Figura 2.9: Operação de produto. (c) mostra o resultado do produtos dos
grafos em (a) e (b).
vértices é um grafo completo Kn. O complemento dos grafos mostrados nas
Figuras 2.8(b) e (c) é apresentado nas Figuras 2.10 (a) e (b), respectivamente.
(a) (b)
Figura 2.10: Operação de complemento. (a) e (b) mostram o complemento
dos grafos das Figuras 2.8(b) e (c), respectivamente.
Quando um grafo é isomórfico ao seu complemento, então ele é chamado
de grafo autocomplementar. Grafos Isomórficos são discutidos em detalhes no
Caṕıtulo 1.6.