21 _22 _23_e_24_-_Teoria_dos_Grafos

Prévia do material em texto

INTRODUÇÃO À TEORIA DOS GRAFOS 
Matemática Discreta Vitor Almeida dos Santos 1 
OS GRAFOS E A RESOLUÇÃO DE 
PROBLEMAS 
M
atem
ática C
o
m
p
u
tacio
n
al 
2 
V
ito
r A
leid
a d
o
s S
an
to
s 
• Muitos problemas reais podem ser 
resolvidos sem uma modelagem prévia. 
– Exemplo: o problema do lobo da ovelha e 
do repolho 
 
 
 
– www.plastelina.net/games/game1.html 
OS GRAFOS E A RESOLUÇÃO DE 
PROBLEMAS 
3 
• Há problemas, entretanto, que são mais 
facilmente resolvidos através de modelos 
matemáticos. 
– O problema dos missionários 
 
 
 
 
– www.plastelina.net/games/game2.html 
OS GRAFOS E A RESOLUÇÃO DE 
PROBLEMAS 
M
atem
ática D
iscreta 
4 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
• Como seria um modelo para representar 
este problema? Um sugestão: 
• Considere as possíveis quantidades de 
canibais e missionários na margem direita do 
rio como sendo o par (c,m); 
• Ligaremos por setas os pares de números 
que configuram uma possibilidade de 
travessia e não representam perigo para os 
missionários. 
OS GRAFOS E A RESOLUÇÃO DE 
PROBLEMAS 
M
atem
ática D
iscreta 
5 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
OS GRAFOS E A RESOLUÇÃO DE 
PROBLEMAS 
M
atem
ática D
iscreta 
6 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
OS GRAFOS E A RESOLUÇÃO DE 
PROBLEMAS 
M
atem
ática D
iscreta 
7 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
• “Uma pessoa pode planejar uma caminhada 
de modo que ela cruze cada uma destas 
pontes uma única vez, e não mais que isso?” 
OS GRAFOS E A RESOLUÇÃO DE 
PROBLEMAS 
M
atem
ática D
iscreta 
8 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
OS GRAFOS E A RESOLUÇÃO DE 
PROBLEMAS 
M
atem
ática D
iscreta 
9 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
Este é o problema do 
Circuito de Euler 
OS GRAFOS E A RESOLUÇÃO DE 
PROBLEMAS 
M
atem
ática D
iscreta 
10 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
Estrela de cincos pontas 
Podemos desenhar uma estrela de cinco pontas sem tirar o lápis do papel.
Podemos desenhar uma estrela de cinco pontas sem tirar o 
lápis do papel. 
Envelope 
Podemos desenhar um envelope sem tirar o lápis do papel mas 
não terminamos no mesmo ponto que começamos. 
Problema da Casinha 
Uma criança diz ter posto a ponta do lápis numa das bolinhas e 
com movimentos contínuos (sem levantar e sem retroceder o 
lápis) traçou as linhas que formam o desenho da casa, traçando 
cada linha uma única vez. A mãe da criança, professora de 
Matemática Discreta, acha que ela trapaceou pois não foi capaz 
de achar nenhuma seqüência que pudesse produzir tal resultado. 
Você concorda com esta mãe? 
 
Problema da Casinha 
Observação 
 Um circuito que percorre cada arco de um grafo 
exatamente uma vez é chamado de circuito 
euleriano 
 
 Um circuito qualquer deve chegar à ilha e sair dela o 
mesmo número de vezes. Logo, para que exista um 
circuito euleriano, deve haver um número par de 
pontes com extremidade nesta ilha. Como existem três 
pontes nessas condições, concluímos que não é 
possível encontrar um circuito euleriano. 
Revisitando o Problema da Pontes de 
Könisberg 
OS GRAFOS E A RESOLUÇÃO DE 
PROBLEMAS 
M
atem
ática D
iscreta 
17 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
• Os pontos verdes da 
figura representam 
cidades e os valores são 
as distâncias entre elas. 
Qual a melhor maneira de 
construir estradas entre 
elas de forma que seja 
possível ir de uma cidade 
a qualquer outra? 
Problema das Três Casas 
Três casas e têm de ser ligadas ao gás, à água e à 
electricidade. Será possível encontrar um grafo tal que 
as (linhas que representam as) arestas não se cruzam? 
 
 
 
IMPORTÂNCIA DOS GRAFOS 
Através de grafos são modeladas situações 
de bastante relevância no mundo moderno. 
 Redes de energia, água e esgoto 
 Redes de computadores (com e sem fio) 
 Redes de relacionamentos 
 Diagramas 
M
atem
ática D
iscreta 
19 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
GRAFOS – DEFINIÇÃO 
 Def.: Um grafo G é definido por dois conjuntos V(G) 
e E(G), onde V(G) é um conjunto não-vazio de 
vértices, E(G), um conjunto de arestas. 
 Existe uma função G que associa cada aresta de 
E(G) a um par de elementos de V. 
M
atem
ática D
iscreta 
20 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
GRAFOS – DEFINIÇÃO 
M
atem
ática D
iscreta 
21 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
u r 
s 
t 
a 
b 
c 
d 
V={u,r,s,t} 
E={a,b,c,d} 
G(a) =(u,r)=(r,u) 
G(b) =(u,s)=(s,u) 
G(c) =(s,r)=(r,s) 
G(d) =(r,t)=(t,r) 
GRAFOS DIRECIONADOS – 
DEFINIÇÃO 
 Def.: Um grafo G é direcionado se a sua função G 
associa cada aresta de E(G) a um par ordenado 
(v,w) de V(G). 
M
atem
ática D
iscreta 
22 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
GRAFOS DIRECIONADOS – 
DEFINIÇÃO 
M
atem
ática D
iscreta 
23 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
V={u,p,q,r,s,t} 
U={a,b,c,d,e} 
G(a) = (r,p) 
G(b) = (s,p) 
G(c) = (s,q) 
G(d) = (t,q) 
G(e) = (q,u) 
a b c d 
e 
u 
p 
q 
r s t 
GRAFOS 
 Se e=(u,v) é uma aresta de G, dizemos que u e v são 
vértices adjacentes ou vizinhos. 
 Denotaremos |V(G)| = n e |E(G)| = m. 
M
atem
ática D
iscreta 
24 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
CLASSES ESPECIAIS DE 
GRAFOS 
 Simples: não possui um par de vértices ligados por 
mais de uma aresta (arestas múltiplas) ou arestas 
que liguem o mesmo vértice (loops). 
 Completo: grafo simples em que cada par de 
vértices está ligado por uma aresta. Um grafo 
completo com n vértices é denotado por Kn. 
 Vazio: grafo sem arestas. 
M
atem
ática D
iscreta 
25 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
SLIDE VERMELHO: GRAFOS E A 
RESOLUÇÃO DE PROBLEMAS 
1. Desenhe o seguinte grafo direcionado G: 
V={u,p,q,r} U={a,b,c,d,e} 
G(a) = (r,p) G(b) = (u,p) G(c) = (q,p) 
G(d) = (r,u) G(e) = (q,u) 
2. Desenhe um grafo G simples direcionado com 
n=5 e m=8. Defina V, E e . 
M
atem
ática D
iscreta 
26 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
SLIDE VERMELHO: GRAFOS E A 
RESOLUÇÃO DE PROBLEMAS 
3. Descreva uma situação do mundo real que pode 
ser convenientemente representada por grafos 
direcionados e outra que pode ser representada 
por grafos não direcionados. 
4. Qual o número máximo de arestas que pode ter 
um grafo simples não direcionado com n vértices? 
M
atem
ática D
iscreta 
27 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
Novas Propriedade 
 Sejam U e W dois conjuntos mutuamente disjuntos e seja 
A o conjunto dos pares não-ordenados da forma (uw) 
com u ∈ U e w ∈ W. Dizemos que (U ∪W,A) é um 
grafo bipartido. 
 
 Sejam U e W dois conjuntos mutuamente disjuntos e seja 
A o conjunto de todos os pares não-ordenados da forma 
uw com u ∈ U e w ∈ W. Dizemos que (U ∪W,A) é um 
grafo bipartido completo. 
 Dizemos que esse grafo é um Kp,q , Kp,q sendo 
 p := |U| e q := |W|. 
 
Teorema 
 Se grafo é bipartido se e somente se o grafo não 
possui um ciclo de tamanho ímpar. 
 Se grafo é bipartido se e somente se o grafo pode ser 
colorido por duas cores de tal forma que dois vértices 
vizinhos não recebam a mesma cor. 
 
 
Grafo Bipartido 
Algoritmo 
GRAUS DE VÉRTICES 
 O grau dG(u) de um vértice u em G é o número de 
arestas incidentes em u. 
 Denotamos por (G) e (G) o grau mínimo e o grau 
máximo de vértices em G. 
M
atem
ática D
iscreta 
33 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
Terminologia 
 
.O grau máximo do grafo, Δ(G) = 3 e o grau mínimo ,δ(G) = 1 
Grau máximo 
Grau mínimo 
Teorema 
Em todo grafo G=(V,E), a soma dos graus dos vértices é igual ao 
dobro do número de arestas, ou seja, 
Σv ∈ V d(v) =2*|E| 
 
Teorema 
Em todo grafo G=(V,E), a soma dos graus dos vértices é igual ao 
dobro do número de arestas, ou seja, 
Σv ∈ V d(v) =2*|E| 
 
Demonstração: cada aresta (x,y) contribui com +1 para 
o grau de x e +1 para o grau de y. Portanto, cada aresta 
contribui com duas unidadespara a soma Σv ∈ V d(v). 
 
Teorema 
Em todo grafo G=(V,E), a soma dos graus dos vértices é igual ao 
dobro do número de arestas, ou seja, 
Σv ∈ V d(v) =2*|E| 
 
Demonstração: cada aresta (x,y) contribui com +1 para 
o grau de x e +1 para o grau de y. Portanto, cada aresta 
contribui com duas unidades para a soma Σv ∈ V d(v). 
 
Corolário: O número de vértices com grau ímpar é par. 
 
Aplicação 
Em um certo reino, existem 100 cidades, e quatro estradas 
partem de cada cidade. Quantas estradas existem no reino? 
 
 
Problemas 
Em um certo reino, existem 100 cidades, e quatro estradas 
partem de cada cidade. Quantas estradas existem no reino? 
 
Σv ∈ V d(v) = 400 = 2|E| 
 
|E| = 200 
 
 
 
 
Problema 
 Mostre que em toda festa, existem pelo menos duas que 
possuem o mesmo número de conhecidos no grupo. 
 Seja n o número de pessoa em uma festa. 
 Caso 1: Suponha que exista uma pessoa que não conhece 
ninguém. Cada pessoa pode conhecer 0,..,n-2 pessoa. 
Como temos n pessoas então temos duas pessoas que 
conhecem o mesmo número de pessoas. 
 
 
Problema 
 Mostre que em toda festa, existem pelo menos duas que 
possuem o mesmo número de conhecidos no grupo. 
 Seja n o número de pessoa em uma festa. 
 
 
 
 Caso II: Não existe ninguém que não conhece ninguém. 
Cada pessoa pode conhecer 1,..,n-1. Como temos n 
pessoas então temos duas pessoas que o mesmo número 
de pessoas. 
 
 
Teorema 
 Demonstre que todo grafo completo é conexo. 
 
 Usaremos uma demonstração por contraposição. Se 
Um grafo não é conexo então não existe um caminho 
entre um par de vértice. Em particular, não existe uma 
aresta entre este par de vértice. Logo, temos dois 
vértices que não são adjacentes. 
Isomorfismo entre grafos 
Dois grafos G1(V1,E1) e G2(V2,E2) são ditos isomorfos 
entre si se existe uma correspondência entre os seus 
vértices e arestas de tal maneira que a relação de 
incidência seja preservada. Em outros termos, temos 
|V1|= |V2| e existe uma função unívoca f: V1 →V2, tal 
que (i,j) é uma aresta de G1 se e somente se (ƒ(i),f(j)) é 
uma aresta de G2 
Isomorfismo 
Para mostrar que dois grafos são isomorfos basta mostrar que existe um 
função de isomorfismo entre eles que preserva a incidência entre os 
vértices. Por exemplo, o seguinte função f mostra que os dois grafos são 
isomorfos: 
f(a) = 1, f(b) = 2, f(c) = 3, f(d) = 8, f(e) = 5, f(f) = 6, f(g) = 7, f(h) = 4. 
 
Isomorfismo 
Motivos para não ser isomorfos 
1. Um grafo tem mais vértices que o outro. 
2. Um grafo tem mais arestas que o outro. 
3. Um grafo tem arestas paralelas e o outro não. 
4. Um grafo tem um laço e o outro não. 
5. Um grafo tem um vértice de grau k o outro não. 
6. Um grafo é conexo e o outro não. 
7. Um grafo tem um ciclo e o outro não. 
Exercício 
Demonstre que não existe um isomorfismo 
Slide Vermelho: Graus de vértices 
1. Modele os seguintes problemas através de grafos. 
 a) “Em um país existem diversos aeroportos de 
onde vôos partem de uns para outros. 
 i) Deseja-se saber quantos aeroportos e 
quantos vôos existem. 
 ii) Deseja-se determinar o aeroporto 
relacionado com o maior número de vôos.” 
 b) “O orkut é uma rede de relacionamentos. 
 i) Sempre haverá duas ou mais pessoas com o 
mesmo número de amigos.” 
M
atem
ática D
iscreta 
49 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
Problema da Existência 
1. É possível que a seguintes listas de números sejam os 
graus de todos os vértices de um grafo simples? 
i) 2,2,2,3 
ii) 1,2,2,3,4 
iii) 3,4,3,3,2 
iv) 4,4,4,4,2 
Nos casos em que a resposta é afirmativa, represente um 
grafo nessas condições. 
 
Problema 
 É possível que a seguintes listas de números sejam os 
graus de todos os vértices de um grafo? 
i) 2,2,2,3 
Não. O número de vértices com ímpar não é par. 
ii) 1,2,2,3,4 
É possível 
 
 
iii) 3,4,3,3,2 
Não. O número de vértices com ímpar não é par. 
iv) 4,4,4,4,2 
 δ(G) = 4 
Nos casos em que a resposta é afirmativa, represente um 
grafo nessas condições. 
v) 4,4,?,?,? 
δ(G) >= 2 
vi) 0,0,?,?,? 
Δ(G) <= 3 
 
 
 
REPRESENTAÇÃO DE GRAFOS 
 Matriz de adjacências 
A matriz A de adjacências de G é uma matriz nxn em 
que Aij é o número de arestas que ligam os vértices vi 
e vj. 
M
atem
ática D
iscreta 
53 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
1 2 
3 
4 
5 
1 2 3 4 5
1 0 0 0 0 1
2 1 0 0 0 1
3 0 1 0 1 0
4 1 1 0 0 0
5 0 1 0 0 0
REPRESENTAÇÃO DE GRAFOS 
 Lista de adjacências. 
Um vetor em que cada elemento i possui uma 
lista encadeada com a vizinhança de i. 
 
 
 
 
 
 
Possibilita uma grande economia de espaço em 
relação a matriz de adjacências 
Esforço para saber se dois vértices estão ligados. 
M
atem
ática D
iscreta 
54 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
5 1 
1 2 
2 4 3 
1 2 4 
1 2 
3 
4 
5 
2 5 
5 
Slide Vermelho: Representação de 
grafos 
1. Represente o grafo acima por uma matriz de 
adjacências e por uma lista de adjacências. 
2. Seja M matriz de adjacências de um grafo G. 
 No que resulta a soma dos valores de uma linha de M? 
 No que resulta a soma dos valores de uma coluna de M? 
M
atem
ática D
iscreta 
55 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
1 2 
3 
4 5 
6 
CAMINHOS 
 Em um grafo G, uma seqüência alternada de vértices 
e arestas W=v0e1v1e2v2...ekvk, onde, para 1  i  k, as 
extremidades de ei são vi-1 e vi é chamada de passeio. 
 Uma trilha é um passeio em que não há repetição de 
arestas. 
 Uma trilha que não possua repetição de vértices é 
chamada de caminho. 
M
atem
ática D
iscreta 
56 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
GRAFOS CONEXOS 
 Se existir um caminho em G com início em um vértice 
u e final em v, dizemos que u e v são conectados. 
 Se todos os pares de vértices de G forem conectados, 
dizemos que G é conexo. Do contrário, G é dito 
desconexo. 
M
atem
ática D
iscreta 
57 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
CICLOS 
 Um passeio é fechado se tem um mesmo vértice 
como início e fim. 
 Uma trilha fechada em que os vértices internos 
(vértices que não são origem nem fim) são todos 
distintos é chamada de ciclo. 
 Um grafo sem ciclos é chamado de acíclico. 
M
atem
ática D
iscreta 
58 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
Slide Vermelho: Caminhos e 
Grafos conexos 
1. Modele as seguintes situações utilizando grafos. 
 Em uma rede móvel ad hoc a comunicação entre os 
dispositivos ocorre através do roteamento de dados 
entre eles próprios. 
 i) Deseja-se que um pacote saia de um dispositivo A 
em direção a um dispositivo B passando pelo 
número mínimo de intermediários. 
 ii) Deseja-se que um pacote saia de um dispositivo A 
e volte para ele mesmo passando pelo maior número 
possível de dispositivos sem, no entanto, repeti-los. 
M
atem
ática D
iscreta 
59 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
Slide Vermelho: Caminhos e 
Grafos conexos 
2. Em relação ao grafo, responda. 
a) Qual caminho mais curto entre 4 e 2? 
b) Qual o passeio mais longo entre 5 e 2? E a 
trilha mais longa? E o caminho mais longo? 
c) Identifique os pares de vértices que não estão 
ligados por um passeio. 
d) Identifique três ciclos 
M
atem
ática D
iscreta 
60 
V
ito
r A
lm
eid
a d
o
s S
an
to
s 
1 2 
3 
4 5 
6 
Slide Vermelho: Caminhos e Grafos 
conexos 
 Um grafo não direcionado com 6 vértices e 10 
arestas é sempre conexo? 
 Um grafo não direcionado com n vértices precisa ter 
, no mínimo, quantas arestas para que alguém possa 
afirmar que ele é sempre conexo? 
 Qual o número mínimo de arestas que deve ter um 
grafo não direcionado e conexo? E direcionado? 
Árvores 
62 
 Uma árvore é um grafo conexo e acíclico. 
 
 
 
 
 
 Árvores modelam diversas situações reais: 
 Sistemas de arquivos 
 Redes e suas subredes 
 Hierarquias em geral 
1 2 
3 
4 
5 
Árvores 
63 
 Uma árvore é um grafoconexo e acíclico. 
 Teorema 2.1 
Se G é uma árvore, todo par de vértices está conectado por 
um único caminho. 
 Teorema 2.2 
Se G é uma árvore, m=n-1. 
 
 
 Uma folha é um vértice em uma árvore com grau 1. 
Teorema 
Se um grafo é uma árvore, então só existe um caminho 
ligando quaisquer dois vértices dados. 
Teorema 
Se um grafo é uma árvore, então só existe um caminho 
ligando quaisquer dois vértices dados. 
 
Prova por contrapositiva, se existe mais de um 
caminho ligando quaisquer dois vértices dados. Logo, 
existe um ciclo entre os dois vértices dados. Assim, o 
grafo é cíclico e não é uma árvore. 
 
Existem 101 cidades em Arbórea. Algumas delas são 
conectadas por estradas, e cada par de cidades é 
conectado por um e somente um caminho simples. 
Quantas estradas existem? 
Exercício 
Existem 101 cidades em Arbórea. Algumas delas são 
conectadas por estradas, e cada par de cidades é 
conectado por um e somente um caminho simples. 
Quantas estradas existem? 100 cidades 
Árvore 
Uma árvore pode ser construída recursivamente. 
 Um único vértice é uma árvore (este vértice é a raiz). 
 SeT1, T2, ..., Tt são árvores disjuntas com raízes r1, r2,..., 
rt, o grafo formado pela ligação de um novo vértice r, 
por uma única aresta a cada uma dos vértices r1, r2,..., rt 
constitui uma árvore de raiz r. 
 Os vértices r1, r2, ...,rt são filhos de r, e r é pai de r1, r2, ..., 
rt. 
Definição Recursiva 
Terminologia 
 A profundidade de um vértice em uma árvore é o 
comprimento do caminho da raiz até o vértice; em particular, 
a raiz tem profundidade 0. 
 A altura (profundidade) da árvore é a maior profundidade 
de todos seus vértices; em outras palavras, é o comprimento do 
maior caminho entre a raiz e um vértice. 
 Um vértice sem filhos é chamado de folha; 
 os vértices que não são folhas são chamados de vértices 
internos ou nós internos. 
 Uma floresta é qualquer grafo acíclico (não 
necessariamente conexo); portanto, uma floresta é uma 
coleção de árvores disjuntas. 
Terminologia 
 Arvores binárias, onde cada nó tem no máximo dois 
filhos, constituem um caso de particular interesse. 
 Em uma árvore binária, cada filho é designado como o filho 
à esquerda ou o filho à direita deste nó. 
 Uma árvore binária completa é aquela em que 
todos os nós internos têm dois filhos e todas as 
folhas têm a mesma profundidade. 
Árvore Binária de Altura 4 
Árvore Binária Completa de altura 3 
Slide Vermelho: Árvores 
 Modele a seguinte situação utilizando árvores. 
 Em uma empresa cada funcionário está subordinado a um 
único chefe, com excecão do Diretor, que não está 
subordinado a ninguém. 
 Deseja-se saber quantos funcionários não possuem 
subordinados. 
 Baseado no modelo da questão anterior, responda e 
justifique. 
 Se cada chefe realiza uma reunião semanal com seus 
subordinados, um funcionário participa de quantas 
reuniões semanais? 
 Uma informação importante que o Diretor deseja que 
todos os funcionário conheçam deve ser repassada de 
cada chefe para os seus subordinados, individalmente. 
Quantas conversas deverão ocorrer? 
Slide Vermelho: Árvores 
 Árvores binárias são aquelas cujos vértices possuem 
0, 1 ou 2 “filhos”. Uma árvore binária completa é 
aquela em que todos os vértices (com excecão das 
folhas) possuem exatamente 2 filhos. 
 Existe uma árvore binária completa com 10 vértices? 
 Existe uma árvore binária completa com 1000 vértices?