Buscar

Teoria dos Grafos

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Teoria dos Grafos/GrafosA1.pdf
Teoria dos Grafos
Edson Prestes
Teoria dos Grafos
 P. O. Boaventura Netto, “Grafos: Teoria, Modelos e Algoritmos”, 
São Paulo, E. Blucher 2001;
 R. J. Trudeau, “Introduction to Graph Theory”, New York, 
Dover Publications, 1993;
 Kaufmann, Arnold. “Exercices de combinatorique avec 
solutions”. Paris: Dunod, 1969-1972 3v.
 Harary, Frank. “Graph theory”. Reading, Mass.: Addison-
Wesley, c1969. 274 p. : il.
 West, Douglas B.. “Introduction to graph theory”. 2nd ed. 
Upper Saddle River: Prentice Hall, c2001. 588 p. 
Referências
Teoria dos Grafos
 A teoria dos Grafos surgiu com os trabalhos de L. Euler, G. 
Kirchhoff e A. Cayley. 
 Esta teoria tem sido utilizada largamente em diferentes áreas da 
biologia, química e na matemática aplicada. 
 O problema das pontes de Königsberg é o primeiro e mais famoso 
problema em teoria dos grafos resolvido por Euler em 1736. 
Introdução
Teoria dos Grafos
O problema das pontes de Königsberg
 Na cidade de Königsberg existiam sete pontes que cruzavam o rio 
Pregel estabelecendo ligações entre duas ilhas e entre as ilhas e as 
margens opostas do rio. 
 O problema consiste em determinar se é possível ou não fazer um 
passeio pela cidade começando e terminando no mesmo lugar, 
cruzando cada ponte exatamente uma única vez. 
Introdução
Teoria dos Grafos
Introdução
pontes de Königsberg
Teoria dos Grafos
 Um grafo G consiste de um conjunto finito e não vazio de n nós, denotado por, 
V(G) e m arestas, denotado por, A(G). 
 O termo grafo foi criado pelo químico E. Frankland e adotado em 1884. Ele vem 
da contração de notação gráfica.
 Cada aresta corresponde a um par não ordenado de nós. 
Introdução
Teoria dos Grafos
 Os nós constituintes de uma aresta podem ser diferentes ou não. 
 Se não forem diferentes então a aresta forma um laço.
Introdução
Teoria dos Grafos
 Harary define um multigrafo como aquele grafo que possui mais de uma 
aresta conectando dois vértices, mas que não possui loops. 
 Se o grafo possui loop e múltiplas linhas conectando dois vértices então 
ele é chamado pseudografo. 
 Em multigrafos/pseudografos, convém rotular as arestas para distingui-
las entre si, devido a multiplicidade de conexões entre os vértices. 
Introdução
Teoria dos Grafos
 Dizemos que uma aresta é incidente aos nós aos quais está associada. 
 Arestas incidentes em um mesmo nó são chamadas arestas adjacentes.
 Nós incidentes em uma mesma aresta são chamados nós adjacentes.
 Um nó pode estar isolado dos demais, caso ele não esteja ligado através 
de uma aresta aos restantes.
Introdução
Teoria dos Grafos
Introdução
G1 G2
Dados os grafos abaixo
 O grafo G1 é descrito por V(G1)={1,2,3,4,5} e A(G1)={(1,2),(1,3),
(1,4), (2,3),(2,4)}.
O grafo G2 é descrito por V(G2)={1,2,3,4} e A(G1)={a,b,c,d,e,f}. 
Teoria dos Grafos
 Um grafo dirigido, ou dígrafo, é um grafo cujas arestas são pares 
ordenados, comumente chamados de arcos ou arestas 
direcionadas. 
 Os dígrafos diferem dos grafos orientados por possuírem pares 
simétricos de arestas direcionadas. 
Introdução
 Dígrafo Grafo Orientado
Teoria dos Grafos
 O grau de um nó corresponde ao número de arestas incidentes a ele.
 Cada laço conta como duas arestas.
 O menor grau presente em um grafo G é denotado por 
 O maior grau presente em um grafo G é denotado por 
Introdução
Teoria dos Grafos
A soma total dos graus de todos os vértices de um grafo é sempre par
Prova por indução no número de arestas
Introdução
B.I. : Suponha um grafo sem arcos. Todos os seus vértices têm grau zero e 
portanto a soma geral dos graus dos vértices é zero (par)
H.I. : Suponha que para todo grafo de n arestas a soma dos graus de todos os 
vértices é par.
P.I. : Suponha um grafo G de n+1 arestas. Seja G' um grafo igual a G exceto 
com menos uma aresta. Portanto G' tem n arestas e pela H.I. tem como soma 
total dos graus de seus vértices um número par.
A inclusão da aresta removida faz com a soma dos graus seja incrementada de 
2 (é incrementado de 1 o grau dos vértices constituintes da aresta), portanto a 
soma dos graus dos vértices de G é um número par.
Teoria dos Grafos
Em um grafo qualquer, o número de vértices com grau ímpar tem que ser 
par
Prova por indução no número de arestas
Introdução
B. I. Suponha um grafo sem arestas, neste caso temos a soma dos graus de 
todos os vértices sendo par. 
Como a quantidade de vértices com grau impar é igual a zero. Então temos 
uma quantidade par de vértices de grau ímpar.
H. I. Suponha um grafo com n arestas e um número par de vértices com grau 
impar
Teoria dos Grafos
Introdução
P. I. Seja G um grafo com n+1 arestas. Seja G', o grafo resultante da retirada de 
uma aresta (v,w). Pela H.I. G’ tem um número par de vértices com grau impar
Vamos analisar o grafo G, baseado nas seguintes situações dos vértices v e w em 
G’:
 v tem grau impar e w tem grau impar
 v tem grau impar e w tem grau par
 v tem grau par e w tem grau par
A adição da aresta (v,w) em G' pode resultar nas seguintes situações:
• v tem grau impar e w tem grau impar em G’. 
A adição da aresta (v,w) faz com que v passe a ter grau par assim como w. Como a 
quantidade de vértices de grau impar é par e como transformamos 2 vértices de 
grau impar em vértices de grau par, G tem uma quantidade par de vértices de 
grau impar.
Teoria dos Grafos
Introdução
• v tem grau impar e w tem grau par em G‘. 
A adição da aresta (v,w) faz com que v passe a ter grau par e w passe a ter grau 
impar. Logo, G tem uma quantidade par de vértices com grau ímpar.
• v tem grau par e w tem grau par em G‘. 
A adição da aresta (v,w) faz com que tanto v quanto w passem a ter grau 
impar. Como tínhamos em G' uma quantidade par de vértices de grau impar, e 
como aumentou em 2 esta quantidade, temos que a quantidade de vértices de 
grau ímpar em G é par.
Teoria dos Grafos
Um passeio entre os nós i e j é uma seqüência alternada de nós e arestas que começa 
no nó i e termina no nó j. 
Introdução
Um exemplo de passeio entre os nós 1 e 4 do grafo G1 é 
(1,(1,3),3,(2,3),2,(1,2),1,(1,4),4). 
Poderíamos pensar que apenas a ordem dos nós é importante. Entretanto, 
podemos ter passeios diferentes com a mesma seqüência de nós.
G1 G2
Por exemplo, no grafo G2 temos os seguintes passeios entre os nós 3 e 4:
(3,d,2,a,4) , (3,c,2,a,4)
Teoria dos Grafos
Um caminho é um passeio que não contém nós repetidos. Entre os nós 1 e 4 do grafo 
G1 temos os seguintes caminhos (1,4),(1,2,4),(1,3,2,4).
Introdução
G1
O comprimento de um caminho entre os vértices u e v é a quantidade de arestas 
presentes no caminho. 
Se existirem mais de um caminho de u a v, então o comprimento do caminho de u a 
v será igual ao menor comprimento dentre todos os caminhos de u a v.
Teoria dos Grafos
Um circuito é um passeio fechado, ou seja, o nó de partida é igual ao nó de chegada. 
Um ciclo é um caminho fechado, isto é , um passeio que contém exatamente dois nós 
iguais: o primeiro e o último. 
Ciclos de comprimento 1 são laços(loops). 
Uma característica interessante de um ciclo é que o número de arestas pertencentes a 
ele é igual a número de vértices. 
Introdução
Teoria dos Grafos
Introdução - Subgrafo
O grafo H é um subgrafo de G, denotado por 
se e
Se
temos , ou seja, H é um subgrafo próprio de G. 
Um subgrafo gerador de G é um subgrafo H, com V(H)=V(G).
Teoria dos Grafos/GrafosA10.pdf
Teoria dos Grafos
Edson Prestes
Teoria dos Grafos
Árvores – Algoritmo de Kruskal
O algoritmo de Kruskal permite determinar a spanning tree de custo mínimo. 
Este custo corresponde à soma dos pesos (distância, tempo, qualidade, ...) 
associados a cada aresta do grafo. 
O algoritmo recebe como entrada um grafo G conexo com pesos e monta um 
grafo desconexo G’, o qual corresponde a uma floresta de árvores composta 
unicamente pelos vértices de G. 
Em seguida, ele ordena as arestas de G em ordem crescente e seleciona a cada 
instante a de menor peso. A aresta selecionada é marcada, para não ser 
analisada mais tarde, e verificada se pode ser adicionada ao grafo G' de forma a 
não gerar ciclos. 
O processo termina quando G' estiver conexo. 
Teoria dos Grafos
Árvores – Algoritmo de Kruskal
Determine a spanning tree de custo mínimo no grafo abaixo usando o 
algoritmo de Kruskal
Teoria dos Grafos
Árvores – Algoritmo de Kruskal
Teoria dos Grafos
Árvores – Algoritmo de Kruskal
Teoria dos Grafos
Árvores – Algoritmo de Dijkstra
O algoritmo de Dijkstra é usado para determinar a menor rota entre duas 
posições em um grafo. Ele assume que o caminho entre dois vértices, u e v, é 
composto sempre dos menores caminhos entre dois vértices quaisquer 
componentes do caminho.
O algoritmo considera um grafo G (ou dígrafo) com arestas de pesos positivos 
e um vértice inicial u. O peso da aresta formada pelos vértices u e v é w(u,v). 
Se u e v não são adjacentes então w(u,v)= 
Ele considera que existe um conjunto S de vértices tal que o menor caminho a 
partir de u até cada vértice de S é conhecido. 
Teoria dos Grafos
Árvores – Algoritmo de Dijkstra
Inicialmente, S={u}, t(u)=0, t(z)=w(u,z) para z u. 
A cada iteração seleciona-se um vértice e adiciona-o a S. 
Em seguida, as arestas a partir de v, (v,z), são exploradas e para cada z S, a nova 
distância aproximada t(z) é atualizada com 
min{t(z), t(v)+w(v,z)}. 
O processo continua até S=V(G) ou até t(z)= para todo z S.
Teoria dos Grafos
Planaridade
Existem três companhias que devem abastecer com gás, eletricidade e água três prédios 
diferentes através de tubulações subterrâneas. Estas tubulações podem estar à mesma 
profundidade ? 
Isto corresponde a perguntar: é possível desenhar um grafo bipartido com 2 conjuntos 
de três elementos cada, onde nenhuma aresta cruze outra.
 Podemos antecipar a resposta dizendo que é impossível !
Um grafo é planar se ele pode ser desenhado em um plano de tal forma que nenhuma 
aresta cruze as demais. 
O desenho deste grafo é chamado realização gráfica planar do grafo, ou simplesmente, 
realização planar. 
O estudo da planaridade é importante em diversas aplicações como, por exemplo, no 
desenvolvimento de circuitos impressos. 
Teoria dos Grafos
Planaridade
K5 e K3,3 não podem ser desenhados sem que algumas arestas se cruzem.
Prova : Considere o desenho de K5 e K3,3 no plano. Seja C um spanning circle do grafo em 
questão. Se o desenho não tiver arestas que se cruzem, então C é desenhado como uma 
curva fechada. 
As cordas de C devem ser desenhadas dentro ou fora da curva. Uma corda é uma aresta 
cujos vértices final e inicial situam-se em uma curva C, ou seja, se C é um spanning circle 
de G então as cordas são as arestas de G que não foram incluidas em C. 
Duas cordas são conflitantes se elas têm seus pontos finais em uma ordem alternante. 
Quando este conflito existe, então estas cordas devem ser desenhadas uma dentro de C e a 
outra fora de C. 
Quantas cordas conflitantes tem o spanning circle de K3,3 ? 
Ele tem três cordas conflitantes. Podemos colocar no máximo 1 corda dentro e outra fora 
de C, então é impossível desenhar K3,3 sem que as cordas se cruzem. 
Quantas cordas conflitantes tem o spanning circle de K5 ? 
Ele possui 5 cordas conflitantes. No máximo duas cordas podem ficar dentro ou fora de C. 
Novamente é impossível desenha-las sem que elas se cruzem. 
Teoria dos Grafos
Planaridade
As cordas conflitantes do grafo K3,3 são ilustradas pelas linhas tracejadas. As linhas 
sólidas indicam o spanning circle.
Teoria dos Grafos
Planaridade
Um grafo planar G divide o plano R2 em um conjunto regiões maximais, conhecidas 
como as faces de G. A região que engloba o grafo é chamada face ilimitada.
As fronteiras destas faces correspondem às arestas de G. 
d(F1)=4 
d(F2)=3
d(F3)=3
d(F1)=6
d(F2)=9
d(F3)=3
Cada aresta de G pertence à fronteira de uma ou duas faces de G. 
O grau (comprimento), de uma face f de G, representado por d(F) é igual ao número de 
arestas da fronteira de F. 
** Aquelas arestas que fazem fronteira com apenas uma face são contadas duas vezes **
Teoria dos Grafos
Planaridade
Se d(Fi) corresponde ao grau da face i em um grafo planar G então
Teoria dos Grafos
Planaridade
Um grafo dual G* é um grafo obtido a partir de um grafo G. 
As faces de G correspondem a vértices em G* e se e é uma aresta de G que 
situa-se entre as faces X e Y de G então a aresta dual e* será uma aresta que 
ligará os vértices x e y, correspondentes respectivamente às faces X e Y de G. 
O grau de uma face em G corresponde ao grau do vértice G*
Proposição: todas as faces de um grafo G têm grau par sse o grafo dual G* é 
euleriano.
Teoria dos Grafos
Planaridade
Um grafo é periplanar(outerplanar) se ele tem uma realização gráfica onde 
cada vértice do grafo faz fronteira com a face ilimitada.
Proposição: os grafos K4 e K2,3 não são periplanares.
Prova: Para mostrar que eles não são periplanares, um dos requisitos é mostrar 
que eles não possuem uma spanning circle. A existência de um spanning circle 
em um grafo G é condição necessária, mas não suficiente, para que G seja 
periplanar. 
Não ! Logo, K2,3 não é um grafo periplanar.
O grafo K2,3 possui um spanning circle ? 
Teoria dos Grafos
Planaridade
O K4 possui um spanning circle. Entretanto, ele possui duas cordas 
conflitantes. Isto faz com que ambas as cordas não possam ser desenhadas na 
parte interna do grafo. 
Como uma corda é desenhada na parte externa do grafo, um dos vértices de G 
fica na parte interna de G e por conseguinte não faz fronteira com a face 
ilimitada
O grafo K4 é periplanar ? 
Teoria dos Grafos
Planaridade
Teorema de Euler: seja G=(V,A) um grafo planar com |V(G)|=n e |A(G)|=m, 
p sendo o número de componentes conexos de G e f o número de faces de uma 
realização planar de G. Logo
n-m+f=p+1
Prova: Considere inicialmente p=1. A prova utiliza indução no número de arcos. 
Para m=0 e um único vértice, n=1, temos apenas 1 face. Portanto, n-m+f=p+1 é 
igual a 1-0+1=1+1.
Suponha que a equação seja verdadeira para um grafo com m-1 arcos, com m 1. 
Construa a realização planar de G acrescentando arcos incidentes ao subgrafo 
corrente. 
Antes da inserção do m-1-ésimo arco, 
nm-1-mm-1+fm-1=2
Teoria dos Grafos
Planaridade
Considere a inserção do m-ésimo arco. Este arco pode ser inserido de duas 
maneiras. 
1a) assuma que uma de suas extremidades corresponde a um nó pertencente ao 
subgrafo existente e a outra extremidade corresponde a um novo nó.
Observe que o número de faces não se altera, logo 
(nm-1+1)-(mm-1+1)+fm-1 =2
nm-mm+fm=2 
Novo vértice
Teoria dos Grafos
Planaridade
2a) considere que as extremidades
do m-ésimo arco correspondem aos nós já 
existentes no grafo em questão
Neste caso, as duas extremidades devem estar na fronteira de uma mesma face. 
Portanto, esta face é dividida em duas pelo m-ésimo arco. Como não criamos 
nenhum novo vértice, o número de vértices não se altera. Então temos,
nm-1-(mm-1+1)+(fm-1+1)=2
nm-mm+fm=2
Teoria dos Grafos
Planaridade
A prova para p>1 fica como exercício!
Teoria dos Grafos
Planaridade
Seja G=(V,A) um grafo conexo planar, com |V(G)|=n e |A(G)|=m, onde m 2. 
Então
 m 3n-6
Usando a fórmula de Euler, temos
Cada face de um grafo é delimitada por mínimo três arestas. Logo
pois cada aresta é compartilhada por duas faces
Teoria dos Grafos
Planaridade
Corolário k5 não é planar.
Para provar que k5 não é planar, basta usar a desigualdade
Sabemos que o número de arestas m de k5 é igual a 5.4/2=10 e que ele possui 
n=5 vértices. 
 m 3n-6
Usando a desigualdade temos 10 3.5-6, vemos que k5 não é planar.
Teoria dos Grafos
Planaridade
Corolário k3,3 não é planar.
De forma análoga ao demonstrado anteriormente, agora cada face é delimitada 
por no mínimo 4 arestas, . Usando o Teorema de Euler, temos 
Sabemos que k3,3 possui 9 arestas e 6 vértices. Usando a desigualdade acima, 
vemos que 9 2.6 -4 é falsa. Portanto, k3,3 não é planar.
 m 3n-6A desigualdade vale quando o grafo é planar e possui triangulos. 
Se ele não possuir triangulos então devemos usar a seguinte desigualdade para 
verificar se ele é planar 
Teoria dos Grafos
Planaridade
Teorema de Kuratowski: um grafo G é planar sse não contém um subgrafo que 
é um grafo generalizado de K5 ou K3,3. 
Um grafo é planar sse não contém um subgrafo o qual por contração chegaria a 
K5 ou K3,3. 
O grafo de Petersen é planar ? 
Não! Pois ele pode ser reduzido ao grafo K5 por arco-contração. 
Teoria dos Grafos
Planaridade
O grafo de abaixo é planar ? 
Não! Pois ele pode ser reduzido ao grafo K3,3 por arco-contração. 
Teoria dos Grafos
Planaridade
Dois grafos são homeomorfos se eles podem ser obtidos do mesmo grafo 
inserindo novos vértices de grau 2 nos arcos. Assim, 
Teorema: um grafo é planar sse não contém subgrafo homeomorfo a k5 ou k3,3. 
Considere que existem pessoas que 
participam dos Comitês:
1 e 2; 1 e 4; 2 e 3; e 3 e 4.
Teoria dos Grafos
Coloração de Grafos
Imagine que devamos reunir pessoas para participarem de um ou mais comitês 
de avaliação em uma determinada conferência. 
Qual deve ser o escalonamento de horários de atuações destes comitês para 
permitir que todos os membros inscritos participem de todas as atividades 
realizadas por seus respectivos comitês?
Este problema é comumente tratado na área de grafos através de técnicas de 
coloração de grafos. 
Um grafo é k-colorível se ele tem uma k-coloração própria. 
Em uma coloração própria, cada classe é um conjunto independente. Portanto, 
um grafo k-colorível é um grafo k-partido.
Teoria dos Grafos
Coloração de Grafos
Definição: Uma k-coloração de um grafo G é uma uma função de rotulamento 
f:V(G) S, onde S correspondem a um conjunto de cores e |S|=k. 
Os vértices associados a uma cor formam uma classe de cores. Uma k-coloração 
é própria se os vértices adjacentes do grafo têm rótulos (cores) diferentes. 
O número cromático é o menor k de forma que G seja k-colorível.
A coloração de um grafo deve seu nome à aplicação de coloração de mapas.
Grafos com loops não são coloríveis. 
Teoria dos Grafos
Coloração de Grafos
Um grafo é 2-colorível sse é ele um grafo bipartido. 
Qual é o número cromático do grafo de Petersen ? 
O grafo K2 é o único grafo 2-crítico, enquanto que os únicos grafos 3-críticos são 
os grafos que constituem ciclos ímpares. 
Teoria dos Grafos
Coloração de Grafos
Definição: Um grafo G é k-cromático se . Uma k-coloração de um 
grafo k-cromático é uma coloração ótima. 
Se para todo então G é k-crítico, ou seja, se 
G é crítico então 
Teorema: Para qualquer grafo G, o número cromático é no máximo 
uma unidade a mais que o maior grau de G, ou seja, 
Exemplo: Qualquer grafo completo garante e qualquer 
grafo estrela G com |V(G)|>2 garante
Proposição: Considere o tamanho do maior clique de G; e o 
tamanho do maior conjunto independente de G. 
Para qualquer grafo G, 
Teoria dos Grafos
Coloração de Grafos
Em relação à primeira desigualdade, note que em um clique todos os vértices tem 
que ter cores distintas. Portanto se o grafo G possui um clique de tamanho 
máximo então seu número cromático será no mínimo igual a , 
podendo ser maior. 
Teoria dos Grafos
Coloração de Grafos
Em relação à segunda desigualdade, considere um grafo C5. O maior conjunto 
independente tem tamanho 
Sabemos que são necessárias 3 cores para colorir C5, então a desigualdade 
é verdadeira.
Teoria dos Grafos
Coloração de Grafos
O problema das quatro cores.
A conjectura de colorir um mapa com no máximo quatro cores foi levantada em 
1852 por Francis Guthrie; e provada em 1976 por K. Appel e W. Haken. 
O teorema de quatro cores afirma que todo mapa desenhado no plano pode ser 
colorido com no máximo quatro cores, de maneira, que regiões adjacentes tenham 
cores diferentes. 
Este problema pode ser reescrito na forma de um grafo e verificada a adjacência 
de cada vértice. 
Teoria dos Grafos
Coloração de Grafos
Teorema : Se um grafo planar admite um circuito hamiltoniano, então suas faces 
podem ser coloridas com quatro cores. Extraido de “Quatro Cores e Matemática” 
João Carlos V. Sampaio.
Teoria dos Grafos
Coloração de Grafos – Polinômio Cromático
Dado k N e um grafo G, o valor é o número de maneiras que 
podemos colorir propriamente G com um conjunto [k]={1,2,…,k} de cores de 
forma que nem sempre todas as cores sejam usadas.
Determine 
Determine 
A função também é chamada função cromática ou polinômio 
cromático de G quando é dado em função de k. 
Note que então .
Se então
Teoria dos Grafos
Coloração de Grafos – Polinômio Cromático
Determine o polinômio cromático dos grafos abaixo
Teoria dos Grafos
Coloração de Grafos – Polinômio Cromático
Qual é o polinômio cromático de uma T com n vértices ?
Proposição: Se T é uma árvore com n vértices então 
Teoria dos Grafos
Coloração de Grafos – Polinômio Cromático
Teorema: Se G é um grafo simples e então
C4
Teoria dos Grafos
Coloração de Grafos – Polinômio Cromático
K3
Teoria dos Grafos
Coloração de Grafos – Polinômio Cromático
C4
Teoria dos Grafos/GrafosA11.pdf
Teoria dos Grafos
Edson Prestes
Teoria dos Grafos
Planaridade
Existem três companhias que devem abastecer com gás, eletricidade e água três prédios 
diferentes através de tubulações subterrâneas. Estas tubulações podem estar à mesma 
profundidade ? 
Isto corresponde a perguntar: é possível desenhar um grafo bipartido com 2 conjuntos 
de três elementos cada, onde nenhuma aresta cruze outra. 
 Podemos antecipar a resposta dizendo que é impossível !
Um grafo é planar se ele pode ser desenhado em um plano de tal
forma que nenhuma 
aresta cruze as demais. 
O desenho deste grafo é chamado realização gráfica planar do grafo, ou simplesmente, 
realização planar. 
O estudo da planaridade é importante em diversas aplicações como, por exemplo, no 
desenvolvimento de circuitos impressos. 
Teoria dos Grafos
Planaridade
K5 e K3,3 não podem ser desenhados sem que algumas arestas se cruzem.
Prova : Considere o desenho de K5 e K3,3 no plano. Seja C um spanning circle do grafo em 
questão. Se o desenho não tiver arestas que se cruzem, então C é desenhado como uma 
curva fechada. 
As cordas de C devem ser desenhadas dentro ou fora da curva. Uma corda é uma aresta 
cujos vértices final e inicial situam-se em uma curva C, ou seja, se C é um spanning circle 
de G então as cordas são as arestas de G que não foram incluidas em C. 
Duas cordas são conflitantes se elas têm seus pontos finais em uma ordem alternante. 
Quando este conflito existe, então estas cordas devem ser desenhadas uma dentro de C e a 
outra fora de C. 
Quantas cordas conflitantes tem o spanning circle de K3,3 ? 
Ele tem três cordas conflitantes. Podemos colocar no máximo 1 corda dentro e outra fora 
de C, então é impossível desenhar K3,3 sem que as cordas se cruzem. 
Quantas cordas conflitantes tem o spanning circle de K5 ? 
Ele possui 5 cordas conflitantes. No máximo duas cordas podem ficar dentro ou fora de C. 
Novamente é impossível desenha-las sem que elas se cruzem. 
Teoria dos Grafos
Planaridade
As cordas conflitantes do grafo K3,3 são ilustradas pelas linhas tracejadas. As linhas 
sólidas indicam o spanning circle.
Teoria dos Grafos
Planaridade
Um grafo planar G divide o plano R2 em um conjunto regiões maximais, conhecidas 
como as faces de G. A região que engloba o grafo é chamada face ilimitada. 
As fronteiras destas faces correspondem às arestas de G. 
d(F1)=4 
d(F2)=3 
d(F3)=3
d(F1)=6 
d(F2)=9 
d(F3)=3
Cada aresta de G pertence à fronteira de uma ou duas faces de G. 
O grau (comprimento), de uma face f de G, representado por d(F) é igual ao número de 
arestas da fronteira de F. 
** Aquelas arestas que fazem fronteira com apenas uma face são contadas duas vezes **
Teoria dos Grafos
Planaridade
Se d(Fi) corresponde ao grau da face i em um grafo planar G então
Teoria dos Grafos
Planaridade
Um grafo dual G* é um grafo obtido a partir de um grafo G. 
As faces de G correspondem a vértices em G* e se e é uma aresta de G que 
situa-se entre as faces X e Y de G então a aresta dual e* será uma aresta que 
ligará os vértices x e y, correspondentes respectivamente às faces X e Y de G. 
O grau de uma face em G corresponde ao grau do vértice G* 
Proposição: todas as faces de um grafo G têm grau par sse o grafo dual G* é 
euleriano.
Teoria dos Grafos
Planaridade
Um grafo é periplanar(outerplanar) se ele tem uma realização gráfica onde 
cada vértice do grafo faz fronteira com a face ilimitada. 
Proposição: os grafos K4 e K2,3 não são periplanares.
Prova: Para mostrar que eles não são periplanares, um dos requisitos é mostrar 
que eles não possuem uma spanning circle. A existência de um spanning circle 
em um grafo G é condição necessária, mas não suficiente, para que G seja 
periplanar. 
Não ! Logo, K2,3 não é um grafo periplanar.
O grafo K2,3 possui um spanning circle ? 
Teoria dos Grafos
Planaridade
O K4 possui um spanning circle. Entretanto, ele possui duas cordas 
conflitantes. Isto faz com que ambas as cordas não possam ser desenhadas na 
parte interna do grafo. 
Como uma corda é desenhada na parte externa do grafo, um dos vértices de G 
fica na parte interna de G e por conseguinte não faz fronteira com a face 
ilimitada
O grafo K4 é periplanar ? 
Teoria dos Grafos
Planaridade
Teorema de Euler: seja G=(V,A) um grafo planar com |V(G)|=n e |A(G)|=m, 
p sendo o número de componentes conexos de G e f o número de faces de uma 
realização planar de G. Logo 
n-m+f=p+1
Prova: Considere inicialmente p=1. A prova utiliza indução no número de arcos. 
Para m=0 e um único vértice, n=1, temos apenas 1 face. Portanto, n-m+f=p+1 é 
igual a 1-0+1=1+1.
Suponha que a equação seja verdadeira para um grafo com m-1 arcos, com m 1. 
Construa a realização planar de G acrescentando arcos incidentes ao subgrafo 
corrente. 
Antes da inserção do m-1-ésimo arco, 
nm-1-mm-1+fm-1=2
Teoria dos Grafos
Planaridade
Considere a inserção do m-ésimo arco. Este arco pode ser inserido de duas 
maneiras. 
1a) assuma que uma de suas extremidades corresponde a um nó pertencente ao 
subgrafo existente e a outra extremidade corresponde a um novo nó.
Observe que o número de faces não se altera, logo 
(nm-1+1)-(mm-1+1)+fm-1 =2 
nm-mm+fm=2 
Novo vértice
Teoria dos Grafos
Planaridade
2a) considere que as extremidades do m-ésimo arco correspondem aos nós já 
existentes no grafo em questão
Neste caso, as duas extremidades devem estar na fronteira de uma mesma face. 
Portanto, esta face é dividida em duas pelo m-ésimo arco. Como não criamos 
nenhum novo vértice, o número de vértices não se altera. Então temos, 
nm-1-(mm-1+1)+(fm-1+1)=2 
nm-mm+fm=2
Teoria dos Grafos
Planaridade
A prova para p>1 fica como exercício!
Teoria dos Grafos
Planaridade
Seja G=(V,A) um grafo conexo planar, com |V(G)|=n e |A(G)|=m, onde m 2. 
Então
 m 3n-6
Usando a fórmula de Euler, temos
Cada face de um grafo é delimitada por mínimo três arestas. Logo
pois cada aresta é compartilhada por duas faces
Teoria dos Grafos
Planaridade
Corolário k5 não é planar.
Para provar que k5 não é planar, basta usar a desigualdade 
Sabemos que o número de arestas m de k5 é igual a 5.4/2=10 e que ele possui 
n=5 vértices. 
 m 3n-6
Usando a desigualdade temos 10 3.5-6, vemos que k5 não é planar.
Teoria dos Grafos
Planaridade
Corolário k3,3 não é planar.
De forma análoga ao demonstrado anteriormente, agora cada face é delimitada 
por no mínimo 4 arestas, . Usando o Teorema de Euler, temos 
Sabemos que k3,3 possui 9 arestas e 6 vértices. Usando a desigualdade acima, 
vemos que 9 2.6 -4 é falsa. Portanto, k3,3 não é planar.
 m 3n-6A desigualdade vale quando o grafo é planar e possui triangulos. 
Se ele não possuir triangulos então devemos usar a seguinte desigualdade para 
verificar se ele é planar 
Teoria dos Grafos
Planaridade
Teorema de Kuratowski: um grafo G é planar sse não contém um subgrafo que 
é um grafo generalizado de K5 ou K3,3. 
Um grafo é planar sse não contém um subgrafo o qual por contração chegaria a 
K5 ou K3,3. 
O grafo de Petersen é planar ? 
Não! Pois ele pode ser reduzido ao grafo K5 por arco-contração. 
Teoria dos Grafos
Planaridade
O grafo de abaixo é planar ? 
Não! Pois ele pode ser reduzido ao grafo K3,3 por arco-contração. 
Teoria dos Grafos
Planaridade
Dois grafos são homeomorfos se eles podem ser obtidos do mesmo grafo 
inserindo novos vértices de grau 2 nos arcos. Assim, 
Teorema: um grafo é planar sse não contém subgrafo homeomorfo a k5 ou k3,3. 
Considere que existem pessoas que 
participam dos Comitês: 
1 e 2; 1 e 4; 2 e 3; e 3 e 4.
Teoria dos Grafos
Coloração de Grafos
Imagine que devamos reunir pessoas para participarem de um ou mais comitês 
de avaliação em uma determinada conferência. 
Qual deve ser o escalonamento de horários de atuações destes comitês para 
permitir que todos os membros inscritos
participem de todas as atividades 
realizadas por seus respectivos comitês? 
Este problema é comumente tratado na área de grafos através de técnicas de 
coloração de grafos. 
Um grafo é k-colorível se ele tem uma k-coloração própria. 
Em uma coloração própria, cada classe é um conjunto independente. Portanto, 
um grafo k-colorível é um grafo k-partido.
Teoria dos Grafos
Coloração de Grafos
Definição: Uma k-coloração de um grafo G é uma uma função de rotulamento 
f:V(G) S, onde S correspondem a um conjunto de cores e |S|=k. 
Os vértices associados a uma cor formam uma classe de cores. Uma k-coloração 
é própria se os vértices adjacentes do grafo têm rótulos (cores) diferentes. 
O número cromático é o menor k de forma que G seja k-colorível. 
A coloração de um grafo deve seu nome à aplicação de coloração de mapas. 
Grafos com loops não são coloríveis. 
Teoria dos Grafos
Coloração de Grafos
Um grafo é 2-colorível sse é ele um grafo bipartido. 
Qual é o número cromático do grafo de Petersen ? 
O grafo K2 é o único grafo 2-crítico, enquanto que os únicos grafos 3-críticos são 
os grafos que constituem ciclos ímpares. 
Teoria dos Grafos
Coloração de Grafos
Definição: Um grafo G é k-cromático se . Uma k-coloração de um 
grafo k-cromático é uma coloração ótima. 
Se para todo então G é k-crítico, ou seja, se 
G é crítico então 
Teorema: Para qualquer grafo G, o número cromático é no máximo 
uma unidade a mais que o maior grau de G, ou seja, 
Exemplo: Qualquer grafo completo garante e qualquer 
grafo estrela G com |V(G)|>2 garante
Proposição: Considere o tamanho do maior clique de G; e o 
tamanho do maior conjunto independente de G. 
Para qualquer grafo G, 
Teoria dos Grafos
Coloração de Grafos
Em relação à primeira desigualdade, note que em um clique todos os vértices tem 
que ter cores distintas. Portanto se o grafo G possui um clique de tamanho 
máximo então seu número cromático será no mínimo igual a , 
podendo ser maior. 
Teoria dos Grafos
Coloração de Grafos
Em relação à segunda desigualdade, considere um grafo C5. O maior conjunto 
independente tem tamanho 
Sabemos que são necessárias 3 cores para colorir C5, então a desigualdade 
é verdadeira.
Teoria dos Grafos
Coloração de Grafos
O problema das quatro cores. 
A conjectura de colorir um mapa com no máximo quatro cores foi levantada em 
1852 por Francis Guthrie; e provada em 1976 por K. Appel e W. Haken. 
O teorema de quatro cores afirma que todo mapa desenhado no plano pode ser 
colorido com no máximo quatro cores, de maneira, que regiões adjacentes tenham 
cores diferentes. 
Este problema pode ser reescrito na forma de um grafo e verificada a adjacência 
de cada vértice. 
Teoria dos Grafos
Coloração de Grafos
Teorema : Se um grafo planar admite um ciclo hamiltoniano, então suas faces 
podem ser coloridas com quatro cores. Extraido de “Quatro Cores e Matemática” 
João Carlos V. Sampaio.
Teoria dos Grafos
Coloração de Grafos – Polinômio Cromático
Dado k N e um grafo G, o valor é o número de maneiras que 
podemos colorir propriamente G com um conjunto [k]={1,2,…,k} de cores de 
forma que nem sempre todas as cores sejam usadas.
Determine 
Determine 
A função também é chamada função cromática ou polinômio 
cromático de G quando é dado em função de k. 
Note que então . 
Se então
Teoria dos Grafos
Coloração de Grafos – Polinômio Cromático
Determine o polinômio cromático dos grafos abaixo
Teoria dos Grafos
Coloração de Grafos – Polinômio Cromático
Qual é o polinômio cromático de uma T com n vértices ?
Proposição: Se T é uma árvore com n vértices então 
Teoria dos Grafos
Coloração de Grafos – Polinômio Cromático
Teorema: Se G é um grafo simples e então
C4
Teoria dos Grafos
Coloração de Grafos – Polinômio Cromático
K3
Teoria dos Grafos
Coloração de Grafos – Polinômio Cromático
C4
Teoria dos Grafos/GrafosA2.pdf
Teoria dos Grafos
Edson Prestes
Teoria dos Grafos
Um passeio entre os nós i e j é uma seqüência alternada de nós e arestas que começa 
no nó i e termina no nó j. 
Introdução
Um exemplo de passeio entre os nós 1 e 4 do grafo G1 é 
(1,(1,3),3,(2,3),2,(1,2),1,(1,4),4). 
Poderíamos pensar que apenas a ordem dos nós é importante. Entretanto, 
podemos ter passeios diferentes com a mesma seqüência de nós.
G1 G2
Por exemplo, no grafo G2 temos os seguintes passeios entre os nós 3 e 4:
(3,d,2,a,4) , (3,c,2,a,4)
Teoria dos Grafos
Um caminho é um passeio que não contém nós repetidos. Entre os nós 1 e 4 do grafo 
G1 temos os seguintes caminhos (1,4),(1,2,4),(1,3,2,4).
Introdução
G1
O comprimento de um caminho entre os vértices u e v é a quantidade de arestas 
presentes no caminho. 
Se existirem mais de um caminho de u a v, então o comprimento do caminho de u a 
v será igual ao menor comprimento dentre todos os caminhos de u a v.
Teoria dos Grafos
Um circuito é um passeio fechado, ou seja, o nó de partida é igual ao nó de chegada. 
Um ciclo é um caminho fechado, isto é , um passeio que contém exatamente dois nós 
iguais: o primeiro e o último. 
Ciclos de comprimento 1 são laços(loops). 
Uma característica interessante de um ciclo é que o número de arestas pertencentes a 
ele é igual a número de vértices. 
Introdução
Teoria dos Grafos
Introdução - Subgrafo
O grafo H é um subgrafo de G, denotado por 
se e
Se temos , ou seja, H é um subgrafo próprio de G. 
Um subgrafo gerador de G é um subgrafo H, com V(H)=V(G).
Teoria dos Grafos
Introdução – Grafo Conexo/Desconexo
Um grafo é conexo se existe um caminho entre qualquer par de nós, caso contrário 
ele é chamado desconexo. 
Por exemplo, se não existir um caminho entre um nó p e qualquer outro nó do grafo, 
então este grafo é chamado desconexo. 
Dois nós estão conectados se existe um caminho entre eles no grafo. 
p
Não, pois ele está contido no subgrafo formado pelos nós u,v,w,x,y e arestas (u,v),
(v,w),(w,x),(x,y),(y,u) e (u,x).
O grafo possui 2 componentes conexos. O primeiro é formado pelos nós u,v,w,x,y e 
arestas (u,v),(v,w),(w,x),(x,y),(y,u) e (u,x) e o segundo unicamente formado pelo nó p.
Teoria dos Grafos
Introdução – Componentes Conexos
Os componentes conexos de um grafo são os subgrafos conexos maximais deste 
grafo, ou seja, são os subgrafos conexos que não estão estritamente contidos em 
outros subgrafos conexos. 
p
O subgrafo formado pelos vértices u e v juntamente com a aresta (u,v) corresponde 
a componente conexo ?
Teoria dos Grafos
Introdução – Componentes Conexos
Quantos componentes conexos o grafo abaixo possui ?
Dois! 
Teoria dos Grafos
Introdução – Grafo totalmente conexo/desconexo
Grafo Totalmente desconexo
Um grafo totalmente desconexo tem todos os seus vértices com grau zero. 
Quantas arestas um grafo completo (Kn) com n vértices possui ? 
Grafo Completo ou Completamente Conexo 
Um grafo completo de n vértices, denotado por Kn, possui a característica de que todo 
vértice do grafo é adjacente aos demais. 
Ele possui exatamente n(n-1)/2
arestas. 
Teoria dos Grafos
Introdução – Conjunto Independente
Um conjunto independente (maximal) em um grafo é um conjunto de vértices não 
adjacentes entre si que não está estritamente contido em outros conjuntos 
independentes. 
O tamanho do maior conjunto independente é chamado número de independência, 
denotado por α(G)
O Grafo abaixo mostra um conjunto independente de tamanho 2 formado pelos 
vértices {u,w}
Existe mais algum ?
Teoria dos Grafos
Introdução – Conjunto Independente
número de independência α(G)=6
outros conjuntos {1,3,5,7}, {4,6}
Teoria dos Grafos
Introdução – Cliques
Um clique (clique maximal) de um grafo é um conjunto de vértices adjacentes entre 
si que não está estritamente contido em outros cliques (conceito similar para 
dígrafos). O tamanho do maior clique de (dí)grafo G é chamado número de clique, 
ω(G).
Um clique de G é um subgrafo completo de G. 
Quantos cliques os grafos abaixo possuem ?
2 cliques, ω(G) = 3 4 cliques, ω(G) = 3
Teoria dos Grafos
Introdução – Cliques
ω(G) = 4
ω(G) = 4
Teoria dos Grafos
Introdução – Grafo Regular
Um grafo G=(V,A) é regular se todos os vértices de G possuírem o mesmo grau, i.e., 
δ(G) =Δ(G)=d(v) ∀ v ∈ V
Quantas arestas são necessárias para desenhar um grafo regular de 9 vértices, 
onde o grau de cada vértice é igual a 3 ? 
Observe que todo grafo completo é regular de grau n-1, onde n corresponde ao 
número de vértices
Não é possível ! 
E um grafo com 10 vértices ? Desenhe!
Teoria dos Grafos
Introdução – Grafo Regular
Um grafo regular com 10 vértices, onde cada vértice tem grau 3, também é chamado 
de 3-regular.
Outro exemplo : grafo 2 - regular
Teoria dos Grafos
Introdução – Grafo Ciclo
Um grafo ciclo de n(>2) vértices, Cn, é um grafo simples 2-regular
Teoria dos Grafos
Introdução – Grafo Roda
Um grafo roda Wn, com n>2, e igual ao grafo Cn adicionado de mais um vertice, o 
qual é adjacente a todos os demais. 
Um grafo Wn possui n+1 vertices e 2n arestas, onde o vertice adicionado ao Cn 
possui grau igual a e os demais vertices grau igual a 3. 
Teoria dos Grafos
Introdução – Grafo Bipartido
Um grafo G é bipartido se seus vértices podem ser separados em dois conjuntos 
independentes de tal forma que toda a aresta do grafo liga sempre dois vértices, um 
de cada conjunto. 
Neste caso, o conjunto de vértices pode ser dividido em dois conjuntos 
V1={ y,u,v} e V2={x,z,w}. 
Teoria dos Grafos
Introdução – Grafo Bipartido
Considere um grafo bipartido constituído dos conjuntos Vj e Vk. 
Se todo vértice estiver ligado a todo vértice então temos um 
grafo bipartido completo G, chamado de biclique e denotado por Kr,s, onde r = |Vj| 
e s=|Vk|. 
Quantos vértices e quantas arestas possui um biclique ?
Ele possui r+s vértices e r.s arestas.
Teoria dos Grafos
Introdução – Grafo K-partido
Um grafo G é k-partido se ele possuir k conjuntos independentes. Logo, um grafo G 
bipartido é um grafo com 2 conjuntos independentes, portanto, ele é 2-partido. 
Um grafo G = (V,A) é chamado k-partido se os seguintes criterios forem obedecidos
• for possível particionar o conjunto de vertices em k conjuntos não vazios V1, V2, ... 
Vk, de forma que eles sejam disjuntos dois a dois e a união dos elementos destes 
conjuntos seja o conjunto de vertices original.
• cada aresta a∈A, tenha extremidades em conjuntos distintos.
• k é o menor inteiro que ainda garante os criterios anteriores, caso contrário 
qualquer grafo com n vertices seria um grafo n partido.
Teoria dos Grafos
Introdução – Grafo K-partido
Teoria dos Grafos/GrafosA3.pdf
Teoria dos Grafos
Edson Prestes
Teoria dos Grafos
Introdução – Grafo Estrela
Um grafo estrela é um grafo bipartido de n vértices que possui um conjunto 
independente com um único vértice e o outro com n-1 vértices
Quantos grafos estrelas podemos construir com um conjunto de n vértices. 
Assumindo que todos os vértices têm um rótulo diferente ?
n grafos
E se considerarmos que todos os vértices são iguais, ou seja, possuem um mesmo 
rótulo ?
1 grafo.
Teoria dos Grafos
Introdução – Grafo K-Cubo
Um k-cubo,Qk, são grafos bipartidos cujos vértices são k-tuplas de 0's e 1's, onde os 
vértices adjacentes diferem em exatamente uma coordenada. 
O grafo abaixo ilustra um 3-cubo. 
Quantos vértices e quantas arestas possui um k-cubo ? 
Ele possui 2k vértices e k 2k-1 arestas. 
Teoria dos Grafos
Introdução – Aplicações
Redes de Computadores
Qual é a melhor maneira de interligarmos um conjunto de computadores de forma 
a minimizar o tempo de transmissão de dados? 
Teoria dos Grafos
Introdução – Aplicações
Atribuição de Tarefas
Dado um conjunto de m tarefas e m operários, é possível atribuir exatamente uma 
tarefa para cada operário de modo que todas as tarefas sejam realizadas?
Cada operário tem um conjunto de habilidades {Oi} para realizar um sub conjunto 
de tarefas.
Teoria dos Grafos
Introdução – Aplicações
Reconhecimento de Gestos
Teoria dos Grafos
Introdução – Aplicações
Decomposição Aproximada
Teoria dos Grafos
Introdução – Aplicações
Decomposição Topológica
Teoria dos Grafos
Introdução – Aplicações
Banco de Dados
Teoria dos Grafos
Introdução – Aplicações
Traçado de um circuito impresso
Teoria dos Grafos
Introdução – Representação
Dado um grafo G=(V,A), a sua matriz de incidência B=[bi,j] é uma matriz |V| x |A| 
que associa os vértices às arestas de G. Cada entrada bi,j associa o vértice i à aresta j, 
assumindo os seguintes valores
O valor 0 indica que a aresta b não é incidente ao vértice a. 
O valor 1 informa que o vértice a é incidente à aresta b e que a aresta b
Matriz de Incidência
Teoria dos Grafos
Introdução – Representação
A matriz de adjacência M=[mi,j] simétrica n x n que armazena o relacionamento 
entre os vértices do grafo entre os nós de um grafo. 
Matriz de Adjacência
Teoria dos Grafos
Introdução – Representação
Uma lista de adjacência armazena o relacionamento entre os vértices de um grafo 
em uma estrutura de listas.
Note que para listar todos os nós adjacentes a um nó ni bastar percorrermos a sua 
lista encadeada. 
Se quisermos saber se um nó ni é adjacente ao nó nk, basta realizar uma busca 
linear na lista associada a ni. 
|*
Teoria dos Grafos
Introdução – Representação
Mostre que com que n vértices distintos podemos formar grafos 
simples (aquele que não possui laços ou mais de uma aresta ligando o 
mesmo par de vértices).
Em um grafo simples, cada par de vértices dá origem ou não a uma aresta. 
Sabemos que um grafo de n vértices possui no máximo arestas. 
Logo, temos grafos com nenhuma aresta, grafos com 1 aresta,..., 
 grafos com m arestas (grafo completo). 
Somando estes resultados,
Teoria dos Grafos
Introdução – Representação
Mostre que todo passeio de u até v contém um caminho de u até v.
Considere um passeio de comprimento l de u até v.
Se l = 0 então temos um passeio sem nenhuma aresta. Isto denota que o 
caminho entre u e v também tem comprimento igual a 0.
Se l > 0, temos que considerar o seguinte. Se o passeio de u a v não possuir 
nenhum vértice que tenha sido visitado duas vezes, então ele corresponde a 
um caminho entre u e v. 
Teoria dos Grafos
Introdução – Representação
Se existe um vértice w que tenha sido visitado mais que uma vez, podemos 
remover as arestas e vértices entre as duas aparições de w. 
Se existirem mais vértices que tenham sido visitados mais que uma vez o 
processo é repetido. Isto produz um passeio mais curto onde cada vértice é 
visitado uma única vez. Logo existe nesta situação um caminho entre u e v.
Teoria dos Grafos
Introdução – Representação
Mostre que todo grafo com n vértices e k arestas, onde n > k, tem no 
mínimo n-k componentes
Um grafo com n vértices com nenhuma aresta tem n componentes. Cada 
aresta reduz a quantidade de componentes em 1 unidade. Então, quando k 
arestas tiverem sido adicionadas ao grafo, o número de componentes será no 
mínimo n-k.
Teoria dos Grafos/GrafosA4.pdf
Teoria dos Grafos
Edson Prestes
Teoria dos Grafos
Introdução – Representação
Mostre que todo grafo com n vértices e k arestas, onde n > k, tem no 
mínimo n-k componentes
Um grafo com n vértices com nenhuma aresta tem n componentes. Cada 
aresta reduz a quantidade de componentes em 1 unidade. Então, quando k 
arestas tiverem sido adicionadas ao grafo, o número de componentes será no 
mínimo n-k.
Teoria dos Grafos
Introdução – Representação
Mostre que um grafo G com n vértices e c componentes, tem uma 
quantidade de arestas k que satisfaz a seguinte desigualdade
O limite inferior foi mostrado anteriormente. 
O limite superior é definido da seguinte maneira. Considere a situação extrema, 
onde temos (c-1) componentes correspondendo a (c-1) vértices de grau igual a 
0; e n-c+1 vértices constituindo um grafo completamente conexo. 
Este grafo irá possuir
Teoria dos Grafos
Introdução – Representação
Mostre que todo grafo simples com dois ou mais vértices tem pelo menos 
dois vértices de mesmo grau
Considere um grafo com n vértice. Se o grafo é simples então o grau de cada 
vértice deve variar de 0 a n-1. Se existir um vértice de grau 0 então não existe 
um vértice de grau n-1, e vice versa. 
Logo, teremos n-1 valores de graus a associar a n vértices. Usando o 
principio de Dirichlet, podemos considerar n caixas rotuladas com os valores 
de graus de 0 a n-1. Porém sabendo que apenas n-1 caixas serão 
preenchidas. 
Distribuindo n-1 vértices em cada uma das n-1 caixas de acordo com seu 
respectivo grau fará com que cada uma das caixas válidas seja preenchida. 
O n-ésimo vértice será associado a uma caixa que já possui um elemento. 
Logo, a caixa escolhida terá 2 vértices, indicando que existem dois vértices 
com mesmo grau.
Dois grafos G e G' são isomorfos, ou seja, se eles 
apresentam as mesmas propriedades estruturais.
Teoria dos Grafos
Definição: Dois grafos G e G' são isomorfos se existe uma função 
bijetora 
tal que
G G’
1 3 2
Introdução – Isomorfismo
Os grafos abaixo são isomorfos ?
Teoria dos Grafos
Sim!
Introdução – Isomorfismo
Os grafos abaixo são isomorfos ?
Teoria dos Grafos
Não! O grafo G é bipartido e o G’ não é .
G G’
Introdução – Isomorfismo
Os grafos abaixo são isomorfos ?
Teoria dos Grafos
Sim!
Introdução – Isomorfismo
Os grafos abaixo são isomorfos ?
Teoria dos Grafos
Não!
Introdução – Isomorfismo
A relação de isomorfismo é uma relação de equivalência sobre o 
conjunto de grafos simples. 
Propriedade reflexiva: uma permutação da identidade dos vértices de 
G é um isomorfismo de G para si próprio.
Teoria dos Grafos
Introdução – Isomorfismo
Propriedade simétrica: Se é uma função que 
define o isomorfismo entre G e G', então f -1 é a função que define o 
isomorfismo entre G' e G. 
Logo, 
temos que
Propriedade de Transitividade: Suponha que as funções 
 e definam a relação de 
isomorfismo entre os grafos G e H; e H e M, respectivamente. 
Teoria dos Grafos
Introdução – Isomorfismo
Sabemos que e que 
Como f define uma relação de isomorfismo, se , então 
existe uma aresta tal que f(u)=x e f(v)=y. 
Logo, .Portanto, a 
composicão lof define a relação de isomorfismo entre G e M, ou seja, 
Uma relação de equivalência divide um conjunto de grafos em classes de 
equivalência, onde dois grafos pertencem ao mesmo conjunto sse eles são 
isomorfos. 
Uma classe isomórfica de grafos é uma classe de equivalência de grafos 
regida por uma relação de isomorfismo. 
Um exemplo de classe isomórfica é a classe chamada grafo de petersen.
Teoria dos Grafos
Introdução – Isomorfismo
Um grafo de Petersen é um grafo simples não orientado gerado usando o 
seguinte conjunto S={1,2,3,4,5}. Seus vértices estão associados a 
subconjuntos de dois elementos de S. 
Os vértices formados a partir destes subconjuntos serão conectados por 
uma aresta se seus subconjuntos correspondentes forem disjuntos.
Teoria dos Grafos
Introdução – Grafo de Petersen
O grafo abaixo é isomórfico ao grafo de Petersen ?
Teoria dos Grafos
Introdução – Grafo de Petersen
Mostre que dois vértices não adjacentes em um grafo de Petersen têm 
exatamente 1 vizinho em comum.
Teoria dos Grafos
Introdução – Grafo de Petersen
Dois vértices A e B não adjacentes no grafo de Petersen são subconjuntos de 
2 elementos que compartilham um único elemento. 
Um vértice adjacente tanto à A quanto à B tem que ser um subconjunto 
disjunto dos dois subconjuntos associados à A e à B. 
Como estes dois vértices são escolhidos a partir do conjunto {1,2,3,4,5}, a 
quantidade de elementos resultante da união dos subconjuntos associados a 
eles é igual a 3. 
Então existe exatamente uma única combinação de 2 elementos para o 
terceiro vértice de forma que ele seja adjacente tanto ao vértice A quanto ao 
vértice B.
Teoria dos Grafos
Introdução – Automorfismo
Um automorfismo de um grafo G é um isomorfismo de G para si próprio. 
Os automorfismos de G são as permutações de V(G) que podem ser 
aplicadas a ambas as linhas e colunas da matriz de adjacência sem mudar a 
adjacência entre os vértices de G. 
Considere um grafo G representado pela matriz de adjacência abaixo
Teoria dos Grafos
Introdução – Automorfismo
G possui 2 automorfismos: ele próprio e a permutação que mapeia o 
vértice 1 para o vértice 4 e o vértice 2 para o vértice 3. 
Realizando o mapeamento
Re-arranjando linhas e colunas
Teoria dos Grafos
Introdução – Automorfismo
Realizando o mapeamento
Re-arranjando linhas e colunas
Apenas trocar a identidade do vértice 1 pela identidade do 4 não é um 
automorfismo de G. 
Embora este grafo seja isomórfico ao grafo G, ele não é um automorfismo 
de G.
Problema 1 
Desenvolver um algoritmo que receba como entrada um grafo G e produza 
como saída α(G) e ω(G), assim como os conjuntos de vértices que deram 
origem a estas medidas. 
A descrição do grafo deve ser feita através de arquivo texto. 
Entrega 08/06
Teoria dos Grafos
Trabalho - Definição
Problema 2 
Dado um mapa composto por obstáculos, uma posição inicial e uma posição 
final, construa uma RRT que encontre um caminho livre de obstáculos entre a 
posição final e a posição inicial. 1 ponto extra se a implementação funcionar no 
simulador
do robô. 
Links uteis 
http://msl.cs.uiuc.edu/rrt/about.html 
http://msl.cs.uiuc.edu/~lavalle/papers/Lav98c.pdf 
http://www.golems.org/papers/AkgunIROS11-sampling.pdf 
http://planning.cs.uiuc.edu (temos o livro na biblioteca :) 
Informações úteis sobre o simulador 
http://www.inf.ufrgs.br/~prestes/Courses/Robotics/instrucoes.rtf 
Falar com o Edson ou com membros do grupo de Edson. 
Entrega 08/06
Teoria dos Grafos
Trabalho - Definição
Teoria dos Grafos/GrafosA5.pdf
Teoria dos Grafos
Edson Prestes
Teoria dos Grafos
Introdução – Automorfismo
Um automorfismo de um grafo G é um isomorfismo de G para si próprio. 
Os automorfismos de G são as permutações de V(G) que podem ser 
aplicadas a ambas as linhas e colunas da matriz de adjacência sem mudar a 
adjacência entre os vértices de G. 
Considere um grafo G representado pela matriz de adjacência abaixo
Teoria dos Grafos
Introdução – Automorfismo
G possui 2 automorfismos: ele próprio e a permutação que mapeia o 
vértice 1 para o vértice 4 e o vértice 2 para o vértice 3. 
Realizando o mapeamento
Re-arranjando linhas e colunas
Teoria dos Grafos
Introdução – Automorfismo
Realizando o mapeamento
Re-arranjando linhas e colunas
Apenas trocar a identidade do vértice 1 pela identidade do 4 não é um 
automorfismo de G. 
!
Embora este grafo seja isomórfico ao grafo G, ele não é um automorfismo 
de G.
Teoria dos Grafos
Introdução – Mais sobre grafos..
Cintura 
A cintura de um grafo é o comprimento do menor ciclo do grafo. 
Um grafo sem ciclos tem uma cintura de comprimento infinito. 
!
Diâmetro de um grafo 
O diâmetro de um grafo consiste na maior distância entre dois vértices em um 
grafo.
Teoria dos Grafos
Introdução – Mais sobre grafos..
Deleções 
A operação de deleção consiste na retirada de vértices ou de arestas de um grafo. 
!
Considere um grafo G =(V,A). A retirada de um vértice v, representada por G-v, 
causa a retirada de todas as arestas incidentes a v. 
!
Enquanto que a retirada de uma aresta w=(u,v), representada por G-w, leva a 
quebra da adjacência dos nós u e v, se o grafo for simples.
Teoria dos Grafos
Introdução – Mais sobre grafos..
Se V1 é um subconjunto de V(G), então G-V1 é o grafo resultante da retirada 
de todos os vértices e de suas arestas incidentes. 
!
Esta operação leva ao grafo G', onde 
Se A1 é um subconjunto de A(G), então G-A1 é o grafo resultante da 
retirada das arestas . Esta operação leva ao grafo G'', 
onde 
V(G'')=V(G) e 
!
A(G'')=A(G)-A1
{(u,v) 2 A(G) | u, v 2 V(G’)}
A operação de arco-contração, denotada por G/a, consiste na retirada da aresta 
a=(u,v) juntamente com seus vértices u e v, seguida da inserção de um novo 
vértice w e a re-ligação das arestas incidentes tanto a u quanto a v a este novo 
vértice.
Teoria dos Grafos
Introdução – Mais sobre grafos..
Qual é o resultado da execução da seqüência (((((G/a)/b)/c)/d)/e) no grafo G de 
Petersen ?
Teoria dos Grafos
Introdução – Mais sobre grafos..
Teoria dos Grafos
Introdução – Mais sobre grafos..
Um vértice de corte é um vértice cuja remoção aumenta a quantidade de 
componentes do grafo. 
!
Uma aresta de corte, também chamada de ponte, quando removida aumenta a 
quantidade de componentes conexos do grafo. 
Um grafo induzido é um grafo obtido através da remoção de um conjunto de 
vértices.
Teoria dos Grafos
Introdução – Mais sobre grafos..
Conjunto desconector é o subconjunto de arestas de G cuja retirada torna G 
desconexo. 
Conjunto de corte de arestas é qualquer conjunto desconector minimal de G. 
A conectividade de arco λ(G) é o tamanho do menor conjunto de corte de 
arestas de G. Um grafo G é k-arco-conexo se λ(G)=k. Por definição λ(G)=0, se 
o grafo é trivial ou desconexo
Conjunto separador é um subconjunto de vértices de G cuja retirada torna G 
desconexo. 
!
Conjunto de corte de vértices é qualquer conjunto separador minimal de G. 
!
A conectividade de vértice κ(G) é o tamanho do menor conjunto corte de vértices 
de G. Um grafo G é um grafo k-vértice-conexo se κ(G)=k. Por definição κ(G)=0, 
se G for desconexo ou trivial, e κ(Kn)=n-1.
O grafo G1 é 2-arco-conexo(λ(G1)=2) e 1-vértice-conexo (κ(G1)=1). !
O grafo G2 é 1-arco-conexo(λ(G2)=1) e 1-vértice-conexo(κ(G2)=1). 
Teoria dos Grafos
Introdução – Mais sobre grafos..
G1 G2
Determine a conectividade de arestas e vértices dos grafos abaixo
Teoria dos Grafos
Introdução – Mais sobre grafos..
Mostre que para qualquer G
Teoria dos Grafos
Mais sobre grafos..
Mostre que um grafo é bipartido sse ele não possuir ciclos de tamanho impar
è Seja G um grafo bipartido e V(G) o conjunto de vértices de G 
correspondente à união de dois subconjuntos disjuntos V1 e V2 de modo que as 
arestas de G unem apenas vértices de diferentes subconjuntos. 
Considere um ciclo C em G, onde C é denotado pela seguinte seqüência de 
vértices v1,v2, v3, ..., vn, v1. Suponha que ,então , , 
seja uma seqüência alternada entre os dois subconjuntos. 
Como o ultimo vértice é v1, e a seqüência é alternada entre os subconjuntos V1 
e V2. Podemos constatar que o penúltimo vértice vn possui índice n par. 
Como um caminho com um número par de vértices possui exatamente um 
número ímpar de arestas. Logo, a adição da aresta de retorno (vn,v1) faz com 
que este caminho possua um comprimento par, dado pelo número par de 
arestas.
Teoria dos Grafos
Mais sobre grafos..
Este ciclo pode ser decomposto em dois subcaminhos, um entre v e u, e outro 
entre u e v', juntamente com a aresta que liga os vértices v e v'. Como v e v' estão 
no mesmo conjunto, os caminhos entre v e u e entre v' e u serão ou pares ou 
impares. 
ç A prova de que G é bipartido é como segue. Considere um vértice u, e uma 
função f(v) que retorna o comprimento do menor caminho de u até v. Faça 
 e . 
Considere uma aresta (v,v'), onde ou , ou seja, uma aresta 
que liga vértices de um mesmo conjunto. Considere também um ciclo que passa 
pelo vértice u. 
Teoria dos Grafos
Mais sobre grafos..
Portanto, a soma dos comprimentos destes caminhos resultará em um número 
par que adicionado de 1, correspondente a aresta (v,v'), leva a um caminho de 
comprimento impar. Como estamos afirmando que nenhum ciclo de tamanho 
impar existe, logo a aresta (v,v') não existe. Por conseguinte, tanto X quanto Y 
são conjuntos independentes, logo o Grafo G é bipartido. 
!
Obs: para sabermos se um grafo não é bipartido, basta verificarmos se 
existe algum ciclo de comprimento impar. 
Teoria dos Grafos
União de Grafos
A união de dois grafos G1 e G2 é definida como 
Teoria dos Grafos
Complemento de Grafos
O complemento de um grafo G, denotado por , é um grafo com 
 e 
 
G
O complemento de um grafo completo é um grafo nulo. Enquanto que o 
complemento de um grafo bipartido é a união de dois grafos completos. 
Teoria dos Grafos
Complemento de Grafos
Um grafo é autocomplementar se ele for isomorfico ao seu complemento. 
O grafo abaixo é autocomplementar ?
G
Sim!
Teoria dos Grafos
Complemento de Grafos
Mostre que para qualquer Grafo G com 6 pontos, G ou possui um triângulo
Considere um vértice v de V(G). Sem perda
de generalidade, podemos assumir v 
é adjacente a outros três vértices u1, u2 e u3 em G. 
Se dois destes vértices forem adjacentes, então existirá um triangulo formado 
por estes dois e por v. 
Caso contrário, estes três vértices não serão adjacentes entre si em G, mas serão 
em
Teoria dos Grafos/GrafosA6.pdf
Teoria dos Grafos
Edson Prestes
Teoria dos Grafos
Complemento de Grafos
Mostre que para qualquer Grafo G com 6 pontos, G ou possui um triângulo
Considere um vértice v de V(G). Sem perda de generalidade, podemos assumir 
v é adjacente a outros três vértices u1, u2 e u3 em G. !
Se dois destes vértices forem adjacentes, então existirá um triangulo formado 
por estes dois e por v. !
Caso contrário, estes três vértices não serão adjacentes entre si em G, mas 
serão em
Teoria dos Grafos
Decomposição
Uma decomposição de um grafo é uma lista de subgrafos tal que cada aresta 
aparece exatamente uma única vez em um único subgrafo. 
Teoria dos Grafos
Matching
Um matching em um grafo G é um conjunto de arestas que não formam loops e 
que não compartilham vértices entre si. !
Um vértice incidente às arestas de um matching M é dito saturado por M. !
Um matching perfeito de G satura todos os vértices de G.
Determine um matching para o grafo abaixo
É um matching perfeito ? Sim!
Teoria dos Grafos
Matching
O tamanho de um matching M é igual a quantidade de arestas de M. !
Um matching M de um grafo G é maximal se toda aresta que não participa de M 
é incidente a alguma aresta em M. !
Se M for o matching de maior cardinalidade de G então ele é chamado matching 
máximo. 
Teoria dos Grafos
Matching
Um caminho de alternante em um matching M é um caminho cujas arestas 
alternam entre aquelas que estão em M e aquelas que não estão em M. !
!
Um caminho alternante, cujos vértices extremos não são saturados por M, é um 
caminho de aumento de M. !
!
Quando M possuir um caminho de aumento P podemos trocar as arestas deste 
caminho, substituindo aquelas que não estão M pelas que estão. Isto irá 
aumentar em uma (1) unidade o tamanho do matching. !
!
Uma observação importante é que o matching máximo é caracterizado pela 
ausência de caminhos de aumento. 
Teoria dos Grafos
Matching
O matching do grafo abaixo, representado pelas arestas sólidas, é um matching 
maximal ou máximo ?
Maximal!
Caminho de aumento
Teoria dos Grafos
Cobertura de Vértices
Uma cobertura de vértices de um grafo G é um subconjunto, Q, de vértices de 
G que contém no mínimo um vértice de cada aresta de G. !
Logo, podemos dizer que os vértices em Q cobrem A(G). 
Teoria dos Grafos
Cobertura de Vértices
A relação entre os problemas de matching e da cobertura de vértices 
corresponde a uma relação min-max, quando tomados sob a mesma instância 
de um problema. !
!
Quando a resposta para a maximização de um problema é igual a resposta para 
a minimização do outro sobre a mesma instância do problema então sabemos 
que o valor encontrado é ótimo. Ou seja, obtendo um matching máximo e uma 
cobertura mínima de vértices de mesmo tamanho provamos que cada um deles 
é ótimo. !
!
O teorema que rege esta relação para os problemas de matching e de cobertura 
é o teorema de König-Egervary. Este teorema afirma que para grafos bipartidos 
o tamanho do matching máximo é igual ao tamanho da menor cobertura de 
vértices.
Teoria dos Grafos
Cobertura de Vértices
Na figura abaixo, tanto a cardinalidade do matching (denotado pelas arestas 
mais escuras) quanto a da cobertura de vértices (ilustrado pelos vértices cinzas) 
é a mesma e igual a 2. 
Note que a cardinalidade da cobertura proíbe matching com mais de 2 
arestas; e o tamanho do matching proibe coberturas com menos que 2 
vértices. 
Teoria dos Grafos
Cobertura de Vértices
Encontre a menor cobertura e o maior matching do grafo abaixo ? 
A cardinalidade da cobertura é igual a 5 enquanto que a cardinalidade do 
matching igual a 5 vértices. 
Teoria dos Grafos
Grafos Eulerianos
O problema das pontes de Königsberg é o primeiro e mais famoso problema em 
teoria dos grafos resolvido por Euler em 1736. Na cidade de Königsberg 
existiam sete pontes que cruzavam o rio Pregel estabelecendo ligações entre 
duas ilhas e entre as ilhas e as margens opostas do rio.!
!
!
!
!
!
O problema consiste em determinar se é possível ou não fazer um passeio pela 
cidade começando e terminando no mesmo lugar, cruzando cada ponte 
exatamente uma única vez. Se isto for possível o grafo é chamado grafo 
Euleriano. 
Teoria dos Grafos
Grafos Eulerianos
Este problema é similar ao problema do carteiro chinês. Neste último, as 
arestas correspondem a trechos de ruas que o carteiro deve percorrer para 
entregar as cartas. !
!
O carteiro deve realizar a entrega das cartas de forma mais eficiente possível, 
ou seja, percorrendo o menor caminho. 
Teoria dos Grafos
Grafos Eulerianos
Se o grafo G é euleriano então qualquer circuito euleriano é ótimo, caso 
contrário algumas arestas serão percorridas mais de uma vez. !
!
Baseado na segunda situação, busca-se encontrar um percurso de peso mínimo 
no grafo que modela o problema.!
!
Logo o nosso problema consiste em um problema de otimização onde devemos 
encontrar um circuito que contenha todas as arestas do grafo e cuja distância 
total seja mínima.
Teoria dos Grafos
Grafos Eulerianos
O teorema de Euler caracteriza uma classe de grafos e ao mesmo tempo mostra 
como construir um circuito Euleriano.!
Teorema: Um grafo conexo G=(V,A) é euleriano, sse, os graus de todos os nós 
de G são pares.
Demonstração: Suponha que o grafo seja euleriano. Então G possui um 
circuito (passeio fechado) euleriano. Se contarmos para cada nó, a entrada e 
saída dele, ao final de todo percurso teremos um conjunto de números pares.!
Suponha agora que temos um grafo G onde todos os seus nós têm grau par. 
Escolha um nó i qualquer e comece a percorre-lo sem repetir arestas, até não 
existirem arestas a serem percorridas, a partir do vértice corrente. !
Como todos os nós têm grau par então o último nó alcançado é o nó i. Se o 
circuito C contiver todos as arestas de G então a demonstração está concluída. 
Caso contrário, existirão arestas não percorridas.
Teoria dos Grafos
Grafos Eulerianos
Como o grafo é conexo então existe um caminho entre qualquer par de 
vértices. Logo, existe algum caminho entre algum vértice do circuito até uma 
aresta q não incluída em C. !
Imagine que este caminho seja formado pela aresta (j,k), onde j pertence ao 
circuito C e k pertence a aresta q. !
Se isto ocorrer devemos percorrer o grafo a partir de j visitando todas as novas 
arestas sem acessar nenhuma aresta em C. Este novo circuito C' pode ser unido 
ao circuito C formando um único circuito. Agora basta percorrer C a partir de 
j e quando retornar a j começar a percorrer C‘.!
Repetimos este processo até que todas as arestas tenham sido visitadas. No 
final teremos um único circuito formado pela união de vários circuitos. O 
circuito resultante é chamado euleriano, assim como o grafo.
Teoria dos Grafos
Grafos Eulerianos
O grafo abaixo é euleriano? Se sim decomponha em ciclos. 
Teoria dos Grafos
Grafos Eulerianos
Baseado nesta idéia podemos afirmar que todo grafo par (cujos vértices possui 
grau par) pode ser decomposto em circuitos. !
Se removermos a condição de que o circuito tem que ser fechado então temos 
um grafo semi-euleriano. 
O grafo abaixo é euleriano ? Se sim determine um circuito euleriano.
Euleriano
Teoria dos Grafos
Grafos Eulerianos
O grafo abaixo é euleriano ? Se sim determine um
circuito euleriano. !
Caso contrário se o grafo for semi-euleriano, determine um passeio que visite !
todos as arestas do grafo
Um grafo semi-euleriano possui 2 vértices com grau impar. Um deles é o 
ponto de partida e o outro é o ponto de chegada. 
semi-euleriano
Teoria dos Grafos
Grafos Hamiltonianos
Um grafo G é chamado Hamiltoniano quando possui um ciclo que inclui todos !
os vértices de G, ou seja, neste ciclo cada vértice aparece uma única vez, com !
exceção do vértice de partida. 
O grafo abaixo é hamiltoniano? Se sim, encontre o ciclo hamiltoniano.
Teoria dos Grafos
Grafos Hamiltonianos
O problema do cálculo do ciclo hamiltoniano, embora semelhante ao problema 
do cálculo do circuito euleriano, é muito mais complexo pois não são 
conhecidas todas as condições necessárias e suficientes para que um grafo 
genérico contenha um ciclo hamiltoniano nem tampouco métodos eficientes 
para construir tal ciclo. !
!
Este problema está intimamente relacionado ao problema do caixeiro viajante, 
o qual consiste em encontrar um caminho que passe por todas as cidades uma 
única vez e retorne ao ponto de partida escolhendo para isso um caminho de 
custo mínimo. !
!
Este caminho consiste em um ciclo hamiltoniano de custo mínimo, onde a 
soma dos custos das arestas pertencentes ao ciclo é mínima. 
Teoria dos Grafos
Grafos Hamiltonianos
Verifique se o grafo abaixo é Hamiltoniano. Se for, mostre um ciclo 
hamiltoniano.
Não é 
Teoria dos Grafos
Grafos Hamiltonianos
Verifique se o grafo abaixo é Hamiltoniano. Se for, mostre um ciclo 
hamiltoniano.
Hamiltoniano
Teoria dos Grafos
Grafos Hamiltonianos
Se o grafo não contiver um ciclo hamiltoniano, mas contiver um caminho entre 
dois vértices de forma que cada vértice do grafo seja visitado uma única vez, 
então este grafo é chamado semi-hamiltoniano. 
O grafo abaixo é hamiltoniano ? semi-hamiltoniano, euleriano, semi-euleriano?
Hamiltoniano e semi-euleriano semi-hamiltoniano e semi-euleriano
Teoria dos Grafos
Traga na próxima aula as condições necessárias e suficientes para que 
um grafo seja hamiltoniano (Olhar livro do Harary ou West).!
Grafos Hamiltonianos
Teoria dos Grafos/GrafosA7.pdf
Teoria dos Grafos
Edson Prestes
Teoria dos Grafos
Dígrafos
As arestas possuem a função de indicar o relacionamento(espacial, 
comportamental, temporal) entre os elementos de um grafo. 
Em diversas situações esta relação não é simétrica, ou seja, par (a,b) não 
implica (b,a). Ex: fluxo de carros em uma rodovia de mão única.
Esta restrição é indicada no grafo determinando uma direção para cada 
aresta, a qual agora é chamada de arco. 
Um dígrafo D=(V,A) é constituído de um conjunto finito de vértices V e 
um conjunto A de arcos, onde cada arco corresponde a um par ordenado de 
vértices.
Teoria dos Grafos
Dígrafos
dígrafo
Podemos dizer que um arco é incidente do nó i para o nó j, ou divergente do 
nó i e convergente ao nó j. 
Um grafo orientado difere de um dígrafo por não possuir pares simétricos de 
arestas direcionadas. 
Grafo orientado
A Figura abaixo ilustra um dígrafo de 6 vértices. 
Teoria dos Grafos
Dígrafos
O grau de entrada de um vértice v, d-(v), é o número de arcos que são 
convergentes a v. 
O grau de saída de um vértice v, d+(v) , é o número de arcos que são 
divergentes de v.
Vértice Sumidouro
d+(v6)=0
Vértice Fonte
d-(v2)=0
Teoria dos Grafos
Dígrafos – Matrizes de Adjacência e Incidência
Matriz de adjacência Matriz de incidência
Quantidade de arcos de w para y
Quantidade de 
arcos de y para w
O arco a está convergindo para w
O arco e está 
divergindo de y
Teoria dos Grafos
Dígrafos - Fluxogramas
Teoria dos Grafos
Dígrafos - Autômatos
Teoria dos Grafos
Dígrafos – Redes Neurais
O caminho para um dígrafo é constituído de uma seqüência de nós e arcos, 
sem se importar com a orientação de cada arco. 
Existem o passeio orientado e o caminho orientado em dígrafos. São 
similares aos usados em grafos com a diferença de que a orientação dos arcos 
é levada em consideração . 
Tanto para o caminho quanto para o passeio orientado, os arcos devem se 
conectar entre si, ou seja, para cada par de arcos que atuam sobre um vértice, 
um diverge e o outro obrigatoriamente converge para o vértice, ou vice versa. 
 
Teoria dos Grafos
Dígrafos
Um caminho orientado de 4 a 6 pode ser {4,(4,5),5,(5,3),3,(3,6),6} 
Um caminho (não orientado) de 6 a 1 pode ser {6,(6,5),5,(5,4),4,(4,1),1}. 
Teoria dos Grafos
Dígrafos
A noção de isomorfismo é estendida aos grafos direcionados considerando a 
orientação dos arcos. 
O dígrafo A é isomórfico ao dígrafo B?
Teoria dos Grafos
Dígrafos
A B C
e ao dígrafo C?
Sim! Não!
A partir de um dígrafo G podemos encontrar um grafo subjacente G’ 
substituindo cada arco de G por uma aresta.
Teoria dos Grafos
Dígrafos
Um dígrafo é fracamente conexo se seu grafo subjacente é conexo. 
Um dígrafo é fortemente conexo ou forte se para cada par de vértices u, v 
existe um caminho orientado de u para v. 
Os componentes fortes de um dígrafo são seus subgrafos maximais fortes. 
Teoria dos Grafos
Dígrafos
Encontre os componentes fortes do dígrafo abaixo. 
Teorema: Um grafo G conexo não direcionado pode ser transformado em um 
dígrafo D fortemente conexo sse G não contém nenhuma ponte.
Teoria dos Grafos
Dígrafos
Prova
Ida: Suponha um dígrafo D fortemente conexo cujo grafo G subjacente 
contém no mínimo uma ponte. Logo, G deve possui no mínimo dois vértices 
cuja ligação exige passar por essa ponte. 
Necessariamente essa ponte permite caminhar em uma única direção, por 
exemplo de um vértice vi para outro vértice vk , mas não permite o retorno de 
vk para vi. Portanto, D não pode ser fortemente conexo se G possuir uma 
ponte.
Teoria dos Grafos
Dígrafos
Volta: Como o grafo subjacente G não contém nenhuma ponte, toda aresta 
faz parte de um ciclo. 
Suponha um ciclo C1 cujas as arestas são orientadas de tal maneira que seja 
possível percorrer o ciclo e voltar à origem. 
Observe que todo vértice em C1 é acessível a partir de qualquer outro. 
Considere outro ciclo C2 que tem no mínimo um vértice em comum com C1. 
Se orientarmos os arcos de C2 sem mudarmos a orientação dos arcos em C1, 
faremos com que qualquer vértice pertencente a união de C1 com C2 possa 
ser alcançado a partir de qualquer outro desta união, pois teremos um 
caminho fechado que passa por todos os vértices. 
Se isso for possível o dígrafo D é fortemente conexo.
Teoria dos Grafos
Dígrafos
Teoria dos Grafos
Dígrafos
Verifique se o grafo abaixo pode ser transformado em um dígrafo fortemente 
conexo. Se puder então determine este dígrafo! 
Teoria dos Grafos
Dígrafos
Um passeio euleriano em um dígrafo é um passeio contendo todas os arcos 
do dígrafo. Um circuito euleriano é um passeio fechado. Um dígrafo é 
euleriano se ele tem um circuito euleriano. 
Os ciclos Bruijn são dígrafos eulerianos e hamiltonianos.
Os vértices são strings de comprimento n formadas a partir de um alfabeto com 
m simbolos. O exemplo mostra o grafo construido usando um alfabeto binário.
Dois vértices a e b estão ligados se os n-1 últimos elementos de a forem iguais 
aos n-1 primeiros elementos de b. Se isto for verdade então o arco que os conecta 
terá como rótulo o último elemento de b. 
111
Teoria dos Grafos
Dígrafos
Os grafos de Bruijn podem ser usados para montar

Teste o Premium para desbloquear

Aproveite todos os benefícios por 3 dias sem pagar! 😉
Já tem cadastro?

Outros materiais