Slides 20

Prévia do material em texto

1
Matemática Discreta
Aula nº 20
Francisco Restivo
2006-05-19
2
Grafos ligados:
Um grafo diz-se ligado se dado qualquer par de vértices distintos 
houver um caminho ligando-os.
Dois grafos não ligados
Um grafo subdivide-se sempre num conjunto de sub-grafos 
ligados, os seus componentes.
Se definirmos a relação R no conjunto de vértices VG como vRw
se e só se v e w estiverem ligados por um caminho em G, os 
componentes de G são as classes de equivalência de R.
2
3
As pontes de Königsberg: problema tratado por Euler em 1736
4
Um caminho Euleriano num gráfico G é um caminho fechado que 
inclui todos os lados do grafo.
Um grafo Euleriano é um grafo que admite pelo menos um 
caminho Euleriano.
Se o caminho que inclui todos os lados não é fechado, o grafo diz-
se semi-Euleriano.
Teorema (Euler):
Um grafo ligado G é Euleriano se e só se todos os seus vértices 
têm um grau par.
http://mathforum.org/isaac/problems/bridges1.html
3
5
Exemplos:
O grafo completo Kn é (n – 1)-regular, isto é, cada vértice tem grau 
n – 1. Como é um grafo ligado, só é Euleriano se n for par.
não Euleriano
O grafo completo bipartido K4,4 é Euleriano.
solução em Garnier & Taylor
6
Um circuito Hamiltoniano num gráfico G é um circuito que passa 
uma vez em todos os vértices do grafo.
Um grafo Hamiltoniano é um grafo que admite pelo menos um 
circuito Hamiltoniano.
Se o caminho que passa por todos os vértices do grafo não é
fechado, o grafo diz-se semi-Hamiltoniano.
Teorema:
Se G é um grafo ligado simples com n (³3) vértices e o grau de 
cada vértice é deg(v) ³ n/2 então o grafo é Hamiltoniano.
Esta condição é suficiente, mas não necessária!
http://mathworld.wolfram.com/HamiltonianCircuit.html
4
7
Problema:
Quantas pontes seria necessário construir em Königsberg para o 
grafo ser Euleriano? E semi-Euleriano? E Hamiltoniano?
Respostas: duas, uma, nenhuma.
Outro problema:
Pode um cavalo de xadrês percorrer todas as casas do tabuleiro 
uma única vez e voltar à casa inicial?
O problema não tem solução (porquê?) para n = 3. E para outros 
valores de n?
8
tem solução para n = 8!
Isomorfismos de grafos:
Os dois grafos de 4 vértices seguintes são isomorfos!
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ë
é
=
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ë
é
=
1211
2010
1103
1030
B
0311
3001
1002
1121
A
Porquê?
5
9
1 2
4 3
a | 3 b | 4
d | 1 c | 2
O isomorfismo é uma bijecção entre os conjuntos de vértices e de 
lados dos dois grafos.
Que grupos de grafos são isomorfos? Só os três primeiros.
10
Sejam G e S dois grafos. Um isomorfismo de G para S consiste de 
um par de bijecções q e f
q: VG ® VS e f:EG ® ES
tais que para qualquer lado e de G, se dG(e) = {v, w} então 
dS(f(e))={q(v),f(w)}. Os gráficos G e S dizem-se então isomorfos.
As matrizes de adjacência de dois grafos isomorfos podem ser 
convertidas uma na outra trocando a ordem das suas linhas e 
colunas (segundo a mesma regra).
Definições:
Uma árvore é um grafo ligado que não contem ciclos.
Num grafo ligado G com um conjunto de vértices V, uma árvore 
expandida é um subgrafo que é uma árvore e com o conjunto de 
vértices V.