Slides 22

Prévia do material em texto

1
Matemática Discreta
Aula nº 22
Francisco Restivo
2006-05-26
2
Definição:
Um grafo cujos vértices são pontos no plano e cujos lados são 
linhas no plano que só se encontram nos vértices do grafo são 
grafos planos.
Um grafo isomorfo de um grafo plano diz-se um grafo planar.
Problema dos três fornecedores (utilities):
Três fornecedores e três consumidores. Será possível ligá-los 
todos sem se cruzarem as ligações? K3,3 não é planar
http://mathworld.wolfram.com/UtilityGraph.html
2
3
Fórmula de Euler:
Um grafo planar conexo G divide o plano em regiões (faces).
K3 divide o plano em duas regiões, uma limitada e outra ilimitada.
K4 divide o plano em quatro regiões, três limitadas e uma ilimitada.
K5 não é um grafo planar (como se provará?)
464K4
233K3
FLV
Uma conjectura: |F| = |L| - |V| + 2
4
Teorema (fórmula de Euler):
Se G é um grafo planar conexo com |V| vértices, |E| lados e 
dividindo o plano em |F| faces ou regiões, então 
|F| = |E| - |V| + 2.
Este teorema prova-se por indução.
Se |E| = 0, então |V| = 1 e há uma única região (|F| = 1), pelo que 
se verifica o teorema.
Se o teorema for verdadeiro para todos os grafos com menos de n 
lados, então pode dizer-se o seguinte:
- Se o grafo com n lados for uma árvore, então |V| = n+1 e |F| = 1, 
pelo que o teorema se verifica (1 = n – (n+1) + 2)
- Se o grafo com n lados não for uma árvore, tem pelo menos um 
ciclo, e se removermos um dos lados do ciclo ficamos com um 
grafo com n-1 lados, e necessariamente
|F| - 1 = (|E| -1) - |V| + 2 ® |F| = |E| - |V| + 2
3
5
Exemplo:
K3,3 não é planar.
Se fosse planar, pela fórmula de Euler dividiria o plano em 
|F| = |E| - |V| + 2 = 9 – 6 + 2 = 5 faces.
A fronteira de cada face seria um ciclo, e cada lado de um ciclo
faria parte da fronteira entre duas faces. Haveria assim 2|E| lados 
pertencendo a fronteiras. Como em K3,3 cada ciclo terá de ter pelo 
menos quatro lados,
2|E| ³ 4|F|
o que contradiz o resultado obtido pela fórmula de Euler. Logo a 
hipótese não é verdadeira.
Outro exemplo:
K5 também não é planar.
Pode usar-se um argumento similar ao anterior para o provar.
6
Teorema de Kuratowski:
Um grafo é planar se e só se não contem nenhum subgrafo
homomorfo de K5 ou K3,3.
A prova deste teorema é longa e complicada...
Definição:
Dois grafos são homomorfos se um grafo se pode obter do outro 
adicionando aos ou retirando dos seus lados vértices de grau 2.
4
7
Qual deles é planar?
Grafo Dual:
O grafo dual G* de um grafo G obtem-se colocando um vértice de 
G* no interior de cada face de G e ligando dois vértices de G* se e 
só se as faces correspondentes de G tiverem um lado comum.
v* = f; e* = e; f* = v
8
Qual deles é planar?
Grafo Dual:
O grafo dual G* de um grafo G obtem-se colocando um vértice de 
G* no interior de cada face de G e ligando dois vértices de G* se e 
só se as faces correspondentes de G tiverem um lado comum.
v* = f; e* = e; f* = v
5
9
Grafo dirigido:
Um grafo dirigido ou digrafo D é constituído por
- Um conjunto não vazio de vértices VD,
- Um conjunto finito de lados ED,
- Uma função d : E ® VD×VD tal que para cada lado e, d(e) é o par 
ordenado (v, w). O lado e dirige-se de w para w. O vértice v é o 
vértice inicial e o vértice w é o vértice final.
Se ignorarmos a direcção dos lados de um digrafo, obtemos o 
grafo não dirigido subjacente.
O vértice v está adjacente ao vértice w, e o lado e emerge de v e 
incide em w. 
Matriz de adjacências:
A matriz de adjacências de um digrafo não é necessariamente 
simétrica, nem são necessariamente iguais os semi-graus
incidente e emergente de um vértice.
10
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ë
é
=
0000
0001
0100
0110
A
2
1
1
0
1 2
4 3
1 1 2 0
Um digrafo é fracamente conexo se o grafo subjacente for conexo.
Um digrafo é fortemente conexo se para cada par ordenado de 
vértices (v, w) existir um caminho dirigido de v para w.
Um digrafo cujo grafo subjacente seja completo diz-se um torneio: 
‘jogam todos contra todos e cada jogo tem um vencedor’.
P – B 2 – 0 
S – A 1 – 0 
P – A 3 – 1 
S – B 1 – 0
P – S 3 – 1 
B – A 1 – 0
6
11
Um digrafo é Euleriano se existir um caminho dirigido fechado 
contendo todos os lados. Um digrafo é Hamiltoniano se um 
caminho dirigido fechado passando por todos os vértices.
Terorema:
Um digrafo conexo é Euleriano se e só se o semi-grau incidente e 
o semi-grau emergente de cada vértice são iguais.
Terorema:
Um torneio tem um caminho directo passando por todos os 
vértices, isto é, é semi-Hamiltoniano.
Um torneio fortemente conexo é Hamiltoniano.