PAA-12-conectividadeGrafosDigrafos

Prévia do material em texto

Profa. Thaís Alves Burity Rocha 
GRAFOS 
Agenda 
 Introdução 
 Conectividade 
 Passeio 
 Caminho 
 Trilha 
 Circuito 
 Ciclo 
 Dígrafos 
 
 
 
Conectividade: Introdução 
 Exemplos de problemas que podem ser modelados com 
grafos 
 Planejamento eficiente de roteamento de pacotes de dados 
na internet 
 
 Definir melhor a rota de distribuição de correspondência 
nos postos de distribuição da ECT (Empresa de Correios e 
Telégrafos) 
 
 A aplicação prática de grafos está relacionada com a 
possibilidade de caminhar, visitar e/ou definir 
conectividade entre vértices e arestas 
 
Grafos: Caminho mínimo 
Problema das 4 cores 
 Trata da determinação do número mínimo de cores 
necessárias para colorir um mapa de forma que 
países/estados vizinhos tenham cores diferentes 
 
 Em 1852, Francis Guthrie conjecturou que 4 era esse 
número mínimo 
 
 Somente em 1976 se conseguiu provar que a 
conjectura estava realmente correta, obtendo-se o 
teorema 
Teorema das 4 cores 
 Dado um mapa 
plano, quatro 
cores são 
suficientes para 
colori-lo de forma 
que estados 
vizinhos não 
partilhem a mesma 
cor 
Teorema das 5 cores 
 Teorema de Heawood: Cinco cores são suficientes 
para colorir qualquer mapa no plano 
 
 Coloração e Número cromático 
 Uma coloração (de vértices) de um grafo é a 
atribuição de uma cor a cada vértice de tal forma que 
dois vértices adjacentes não tenham a mesma cor 
O número cromático do grafo é o menor número de 
cores necessárias para se obter uma coloração 
 Não existe um algoritmo eficiente para esse problema 
Coloração e Número cromático 
 Exemplo 
 
 
 
 
 Número cromático: 2 
 Conjuntos de vértices independentes: {A, D} e {B, C} 
 
 Existem vários problemas práticos cuja solução consiste 
em dividir os vértices de um grafo na menor 
quantidade de conjuntos de vértices independentes 
A B 
C D 
Passeio (walk) 
 Um passeio em um grafo G = (V, E) é uma sequência 
alternada de vértices e arestas que começa e termina 
com vértices 
 A sequência v1, …, vk , ∀ v1, …, vk ∈ V, é um passeio de v1 
a vk , se (vj, vj+1) ∈ E, 1 ≤ j ≤ |k – 1| 
 Um passeio com k vértices possui k – 1 arestas, no mínimo 
 Neste caso teríamos as seguintes arestas: (v1, v2) , (v2, v3), …, (vk-
1, vk) 
 O comprimento de um passeio é o número de arestas 
do passeio 
 No caso de grafos ponderados, a definição de comprimento leva 
em consideração o peso das arestas 
Passeio (walk): Exemplo 
 
 
 
 
 
 
 
 Passeio: A sequência {u, 1, 4, 3, 5, 4, 3, 5, v} 
 Comprimento: 8 
 u1, 14, 43, 35, 54, 43, 35, 5v 
1 
5 4 
2 
3 
v 
u 
Caminho (path) 
 Um caminho ou caminho simples em um grafo é 
um passeio em que todos os seus vértices são 
distintos 
 
 O comprimento de um caminho é o número de 
arestas do caminho 
 
 
 
 
 
Caminho (path): Exemplo 
 
 
 
 
 
 
 
 Caminho: Sequência {u, 1, 4, 5, v} 
 Comprimento: 4 
 
 Observe que a sequência {u, 1, 4, 3, 5, 4, 3, 5, v} do 
exemplo anterior é um passeio, mas não constitui um 
caminho 
1 
5 4 
2 
3 
v 
u 
Trilha (trail), circuito e ciclo 
 Uma trilha (ou trajeto) em um grafo é um passeio em 
que todas as arestas são distintas 
 
 Um circuito (ou trajeto fechado) em um grafo é um 
trajeto em que o vértice inicial e o vértice final são 
iguais 
 
 Um ciclo é um circuito em que todos os vértices são 
distintos, com exceção do primeiro e do último 
 Um triângulo é um ciclo de tamanho 3 
 Possui 3 vértices e 3 arestas 
 Um grafo acíclico é aquele que não possui ciclos 
Exercício 1 
 Forneça exemplos de: 
 Passeio que não é nem trilha nem caminho 
 Passeio que é trilha e não é caminho 
 Circuito que não é ciclo 
 Triângulo 
a 
e 
d 
c 
f 
b 
Exercício 1: Solução 
 Passeio que não é nem trilha nem caminho 
 Trilha: arestas distintas 
 Caminho: vértices distintos 
 {a, b, d, c, b, d} 
a 
e 
d 
c 
f 
b 
Exercício 1: Solução 
 Passeio que é trilha e não é caminho 
 Trilha: arestas distintas 
 Caminho: vértices distintos 
 {a, b, c, e, f, c} 
a 
e 
d 
c 
f 
b 
Exercício 1: Solução 
 Circuito que não é ciclo 
 Trilha: arestas distintas 
 Circuito: trilha com mesmo vértice de início e fim 
 Ciclo: vértices distintos 
 {a, b, c, e, f, c, d, a} 
a 
e 
d 
c 
f 
b 
Exercício 1: Solução 
 Triângulo 
 Ciclo de tamanho 3 
 Ciclo: arestas e vértices distintos 
 {a, b, d, a} 
a 
e 
d 
c 
f 
b 
Grafos conectados (conexos) 
 Um grafo é conectado se e somente se existe um 
caminho entre qualquer par de vértices do grafo 
 Caso contrário, o grafo é dito desconexo ou 
desconectado 
 Exemplo de grafo conectado: 
6 
2 
3 
5 
4 
1 
Exercício 2 
 É verdade que todo grafo conexo com n vértices 
tem pelo menos n-1 arestas? 
 
Exercício 2: Solução 
 Um grafo conexo é aquele em que é possível 
determinar um caminho entre qualquer par de 
vértices 
 
 Um caminho é um passeio cujos vértices são distintos 
 
 O comprimento de um passeio com k vértices é k-1, 
no mínimo 
 Esse mesmo conceito se aplica para caminho 
 
Exercício 3 
 É possível que um grafo e o seu complemento sejam 
ambos desconectados? 
 
Exercício 3: Solução 
 O complemento de um grafo G é um grafo G nos mesmos 
vértices tais que dois vértices de G são adjacentes se e 
somente se eles não são adjacentes em G 
 
 Já um grafo desconexo é aquele em que não existe um 
caminho entre qualquer par de vértices 
 
 Com base nessas definições, é possível concluir que um 
grafo e seu complemento não podem ser ambos 
desconexos! 
 Ora, se o grafo é desconexo, o seu complemento vai ser um 
grafo completo! 
_ 
_ 
Grafo Euleriano 
 Um grafo conectado G é dito euleriano se existe uma trilha 
fechada (circuito) contendo cada uma das arestas de G 
 O problema das pontes (lembram da primeira aula?) é 
equivalente a identificar se o grafo correspondente é euleriano 
 Um caminho euleriano em um grafo G é um caminho que usa 
cada aresta de G exatamente uma vez 
 
 Teorema: Um grafo conectado G é euleriano se e somente 
se o grau de cada vértice é par 
 
 Todo grafo eureliano é conexo 
Grafo Euleriano: Exemplo 
 
 
 
 
 
 
 
 É possível identificar um circuito envolvendo todas as arestas do 
grafo 
 Todas as arestas são distintas 
 O vértice inicial e o vértice final são iguais 
 { a, b, c, d, b, e, d, a, e, f, g, h, f, a} 
 Todos os vértices tem grau par! 
 
a 
e d 
c 
b h 
g 
f 
1 
2 
3 
4 
5 
6 
7 
8 
9 10 
11 
12 13 
Exercício 4 
 K5 é euleriano? 
a 
e 
d 
c 
b 
K5 
Exercício 4: Solução 
 Sim 
 Todos os vértices tem grau par! 
 a 
e 
d 
c 
b 
1 
2 
3 
4 
5 9 
6 
7 
10 
8 
Grafo Hamiltoniano 
 Um grafo hamiltoniano é um grafo que contém ciclo 
envolvendo todos os seus vértices 
 Exemplo: 
 Ciclo: {a, c, d, e, b, a} 
 
 
 
 
 Podemos determinar precisamente se um grafo é Eureliano 
ou não, mas o mesmo não pode ser dito sobre grafo 
Hamiltoniano 
 Problema NP-Completo! 
a 
e 
d 
c 
b 
Exercício 5 
 Esse grafo é hamiltoniano? 
a 
d c 
b 
f 
e 
Exercício 5: Solução 
 Sim 
 Ciclo: {a, b, c, d, e, f, a} 
a 
d c 
b 
f 
eExercício 6 
 Esse grafo é hamiltoniano? 
a 
e d 
c 
b 
Exercício 6: Solução 
 Sim 
 Ciclo: {a, b, e, d, c, a} 
a 
e d 
c 
b 
Exercício 7 
 Esse grafo é hamiltoniano? 
 
a 
e d 
c 
b 
Exercício 7: Solução 
 Não! 
 Qualquer tentativa de conectar todos os vértices 
implicará na passagem pelo vértice c mais de uma 
vez! 
a 
e d 
c 
b 
Grafos Hamiltoniano: Aplicação 
 Problema do caixeiro viajante 
 Suponha que a área de venda de um caixeiro viajante 
inclua várias cidades, muitas das quais, aos pares, 
estão conectadas por rodovias 
O trabalho do caixeiro requer que ele visite cada 
cidade pessoalmente 
 Sob que condições seria possível ele estabelecer uma 
viagem circular (que o leve de volta ao ponto de 
partida), de forma que ele visite cada cidade 
exatamente uma vez? 
Dígrafos 
 Também chamados de grafos dirigidos ou 
orientados 
 Conjunto finito V não-vazio de vértices 
 Conjunto finito A de pares ordenados de vértices 
 Pares ordenados de vértices são chamadas de arcos 
em vez de arestas 
 Um arco (v, w) pode ser referenciado como vw 
simplesmente 
 D = (V, A) 
Dígrafos: Exemplo 
 
 
 
 
 
 
 V = {a, b, c, d} 
 A = {ab, bb, bc, cb, cb, ca, dc} 
a 
b c 
d 
Dígrafos 
 Dígrafo simples: 
 Todos os arcos são distintos 
 Não existem laços 
 
 Para obter o grafo correspondente de um dígrafo: 
 Eliminar as direções dos arcos 
 Não necessariamente o grafo correspondente a um 
dígrafo simples é simples 
Dígrafos: Exemplo 
a 
b c 
d 
Dígrafo simples 
a 
b c 
d 
Grafo correspondente 
não é simples 
Versão direcionada de um grafo 
 Cada aresta não direcionada (u,v) em G é 
substituída por duas arestas direcionadas (u,v) e 
(v,u) 
0 
1 2 
0 
1 2 
Dígrafos: Representação por matriz de 
adjacências 
1 2 3 4 
1 0 1 1 0 
2 0 0 1 1 
3 0 0 0 1 
4 0 0 0 0 
1 
4 3 
2 
a12 
a23 
a24 
a13 
a34 
Dígrafos: Representação por matriz de 
adjacências 
1 
4 5 
2 3 
6 
1 2 3 4 5 6 
1 0 1 0 1 0 0 
2 0 0 0 0 1 0 
3 0 0 0 0 1 1 
4 0 1 0 0 0 0 
5 0 0 0 1 0 0 
6 0 0 0 0 0 1 
Dígrafos: Representação por lista de 
adjacências 
1 2 3 
2 4 3 
3 4 
4 
1 
4 3 
2 
a12 
a23 
a24 
a13 
a34 
Dígrafos: Representação por lista de 
adjacências 
1 
4 5 
2 3 
6 
1 2 4 
2 5 
3 6 
4 
5 
6 
5 
2 
4 
6 
Dígrafos: Representação por lista de 
incidências 
1 
4 3 
2 
a1 
a3 
a4 
a2 
a5 
1 2 3 4 5 
1 +1 +1 0 0 0 
2 -1 0 +1 +1 0 
3 0 -1 -1 0 +1 
4 0 0 0 -1 -1 
Dígrafos: Grau de vértices 
 Os vértices de um dígrafo possuem: 
 Grau de entrada (indeg(v)) : número de arcos que chegam 
no vértice 
 Grau de saída (outdeg(v)) : número de arcos que partem 
do vértice 
 Da mesma forma: 
 Sequência de graus de entrada 
 Sequência de graus de saída 
 Proposição: 
 ∑ indeg(vi) = ∑ outdeg(vi) = |A| 
 A é o conjunto de arcos 
Dígrafos: Exemplo de grau de vértices 
 indeg(a) = 1 
 outdeg(a) = 1 
 indeg(b) = 4 
 outdeg(b) = 2 
 
 Sequência indeg = 4, 2, 1, 0 
 Sequência outdeg = 3, 2, 1, 1 
 
 ∑indeg = 4 + 2 + 1 + 0 = 7 
 ∑outdeg = 3 + 2 + 1 + 1 = 7 
 |A| = 7 
a 
b c 
d 
Dígrafos: Isomorfismo 
 Dois dígrafos são isomórficos se: 
 Existe um isomorfismo entre os respectivos grafos 
correspondentes 
 A ordem dos vértices em cada arco é preservada 
 Exemplo: 
 Checar com base nos valores de indeg e outdeg 
D1 D2 
Exercício 8 
 
 
 
 
 
 
 D1 e D2 são isomórficos? 
a 
b c 
d 
D1 
a 
b c 
d 
D2 
Exercício 8: Solução 
 
 
 
 
 
 
 D1 e D2 são isomórficos? 
 Não, pois a direção do arco que conecta c e d não é 
preservada 
a 
b c 
d 
D1 
a 
b c 
d 
D2 
Dígrafos: Conectividade 
 Os conceitos de passeio, caminho, ciclos, etc. são 
semelhantes: 
 Deve respeitar a orientação dos arcos 
 
 Exemplo: 
 Trilha: {d, c, b, c, a} 
 Ciclo: {c, a, b, c} 
a 
b c 
d 
Dígrafos conectados 
 Um dígrafo D é conectado se o grafo correspondente é 
conectado 
 Um grafo é conectado se e somente se existe um caminho 
entre qualquer par de vértices do grafo 
 
 Um dígrafo D é fortemente conectado se para 
quaisquer dois vértices v e w, existe um caminho entre 
v e w 
 
 Um dígrafo D é Euleriano se e somente: 
 Fortemente conectado 
 indeg(vi) = outdeg(vi), para todo vértice i 
Dígrafos conectados: Exemplo 1 
 
 
 
 
 
 O dígrafo é conectado 
 O dígrafo não é fortemente conectado 
 O dígrafo não é Euleriano 
a 
b c 
d 
Dígrafos conectados: Exemplo 2 
 
 
 
 
 
 O dígrafo é conectado 
 O dígrafo é fortemente conectado 
 O dígrafo é Euleriano 
a 
b c 
Exercício 9 
 Trace um grafo que tenha: 
 Vértices: {1, 2, 3, 4, 5} 
 Arestas: {a1, a2, a3, a4, a5, a6} 
 Funções: 
 g(a1) = 1-2 
 g(a2) = 1-3 
 g(a3) = 3-4 
 g(a4) = 3-4 
 g(a5) = 4-5 
 g(a6) = 5-5 
Exercício 9: Solução 
 Trace um grafo que tenha: 
 Vértices: {1, 2, 3, 4, 5} 
 Arestas: {a1, a2, a3, a4, a5, a6} 
 Funções: 
 g(a1) = 1-2 
 g(a2) = 1-3 
 g(a3) = 3-4 
 g(a4) = 3-4 
 g(a5) = 4-5 
 g(a6) = 5-5 
1 
5 
2 a1 
a2 
a5 
4 
3 
a3 
a4 a6 
Exercício 10 
 Com relação ao grafo obtido: 
 Encontre dois vértices que não sejam adjacentes 
 Encontre um vértice que seja adjacente a ele mesmo 
 Encontre um laço 
 Encontre duas arestas paralelas 
 Encontre o grau do vértice 3 
 Encontre um caminho de comprimento 5 
 Encontre um ciclo 
 Este grafo é completo? 
 Este grafo é conexo? 
Exercício 10: Solução 
 Encontre dois vértices que não sejam adjacentes 
 2 e 3 
 Encontre um vértice que seja adjacente a ele 
mesmo 
 5 
 Encontre um laço 
 a6 
 Encontre duas arestas paralelas 
 a3 e a4 
1 
5 
2 a1 
a2 
a5 
4 
3 
a3 
a4 a6 
Exercício 10: Solução 
 Encontre o grau do vértice 3 
 3 
 Encontre um caminho de comprimento 5 
 Não é possível, dado que em um caminho todos os vértices 
devem ser distintos 
 Encontre um ciclo 
 a3, a4 
 Este grafo é completo? 
 Não 
 Este grafo é conexo? 
 Sim 
 
 
1 
5 
2 a1 
a2 
a5 
4 
3 
a3 
a4 a6