Slides 19

Prévia do material em texto

1
Matemática Discreta
Aula nº 19
Francisco Restivo
2006-05-18
2
As pontes de Königsberg: problema tratado por Euler em 1736
2
3
Teoria dos grafos:
Grafos são constituídos por pontos (vértices) e linhas que ligam 
esses pontos (lados, ou arestas).
Definição:
Um grafo (não orientado) G é constituído por
- Um conjunto não vazio de vértices V,
- Um conjunto finito de lados E,
- Uma função d : E ® P(V) tal que para cada lado e, d(e) é um 
sub-conjunto de V com um ou dois elementos. O lado e liga os 
elementos de d(e).
Definição:
Grafo simples é um grafo sem lados múltiplos a ligar os mesmos 
dois vértices e sem lados ligando um único vértice (anéis). 
Duas figuras diferentes podem representar exactamente o mesmo 
grafo.
4
grafo grafo simples o mesmo grafo simples
Um grafo e o diagrama que o representa não são o mesmo.
Definições:
- Um par de vértices v e w são adjacentes se existir um lado e que 
os ligue. O lado e incide em v e w.
- Os lados e1, e2, ..., en são adjacentes se tiverem um vértice 
comum.
- O grau ou valência de um vértice v é o número de lados que 
incide em v. Um grafo em que todos os vértices têm o mesmo grau
r diz-se um gráfico r-regular.
3
5
Dois diagramas do mesmo grafo simples de Peterson (3-regular)
Mais definições:
- Um grafo nulo é um grafo em que o conjunto de lados é vazio.
- Um grafo completo é um grafo simples em que cada par de 
vértices distintos está ligado por um lado.
- Um grafo bipartido é um grafo em que o conjunto dos vértices V 
tem uma partição [V1, V2] tal que cada lado liga um vértice de V1 a 
um vértice de V2.
- Um grafo bipartido completo é um grafo bipartido em todos os 
vértices de V1 estão ligados a todos os vértices de V2 por um 
único lado.
6
grafo completo K4 outra vez grafo bipartido grafo bipartido completo K2,3
Matriz de adjacências:
Seja G um grafo com o conjunto de vértices {v1, v2, ..., vn}. A matriz 
de adjacências de G é uma matriz n×n A = A(G) tal que aij é o 
número de lados distintos que ligam vi a vj.
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ë
é
=
0000
0012
0101
0211
A
deg(v1) = 5
deg(v2) = 2
deg(v3) = 3
deg(v4) = 0
1 2
4 3
4
7
Matriz de adjacências de um digrafo:
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.
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ë
é
=
0000
0001
0100
0110
A
2
1
1
0
Definição:
Um grafo orientado ou digrafo G é constituído por
- Um conjunto não vazio de vértices V,
- Um conjunto finito de lados E,
- Uma função d : E ® P(V) tal que para cada lado e, d(e) é o sub-
conjunto de V {u, v}. O lado e dirige-se de u para v. O vértice u
está adjacente ao vértice v, e o lado e emerge de u e incide em v. 
1 2
4 3
1 1 2 0
8
Matriz de incidências:
Seja G um grafo com o conjunto de vértices {v1, v2, ..., vn} e um 
conjunto de lados {e1, e2, ..., em}. A matriz de incidência de G é uma 
matriz n×m I = I(G) tal que aij =1 significa que o lado j incide sobre o 
vértice vi.
Sub-grafo de um grafo:
Um grafo S é um sub-grafo do grafo G, dizendo-se que S£G, se 
VSÍVG, ESÍEG e dS(e)=dG(e) para cada lado e de S.
Intuitivamente, corresponde a apagar certos lados e vértices de G, 
com o cuidado de apagar todos os lados que incidem sobre um 
vértice apagado.
1 2
4 3
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ë
é
=
00000
11100
00101
11011
I
5
9
Exemplo:
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ë
é
=
ú
ú
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ê
ê
ë
é
=
0101
1000
0001
1011
M 
01101
10011
10020
01201
11011
M SG
S é um sub-grafo de G:
Num grafo, a soma dos graus dos vértices é duas vezes o número 
de lados (lema do cumprimento de mão)å
Î
´=
Vv
|E|2deg(v)
10
Caminhos, circuitos e ciclos:
Uma sequência de lados de comprimento n num grafo G é uma 
sequência de n lados e1, e2, ..., en em que ei e ei+1 são adjacentes 
para n = 1, 2, ..., n-1. (lados não necessariamente distintos)
A sequência de lados determina uma sequência de vértices v0, v1, 
v2, ..., vn em que d(ei) = {vi-1, vi}.
Um caminho é uma sequência de lados em que todos os lados são 
distintos.
Uma sequencia de lados é fechada se o vértice inicial coincide 
com o vértice final: v0 = vn. Um caminho fechado simples com pelo 
menos um lado diz-se um circuito (ou ciclo).
Que informação dará A2?
(multiplicação da matriz de adjacências por ela própria)
6
11
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ë
é
=
0000
0021
0201
0111
A
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ë
é
=
0000
0513
0153
0333
A2
5 é o número de sequências de lados de comprimento 2 que 
ligam o vértice 2 ao vértice 2. Quais são?
O termo de ordem r do somatório é o produto do número
de lados ligando vi a vr pelo número de lados ligando vr a vj, isto é, 
o número de sequências de lados de ordem 2 que ligam vi a vj
através de vr.
å
=
n
1k
kjikaa
1 2
4 3
12
Dado um grafo G com um conjunto de vértices V = {v1, v2, ..., vn} e 
matriz de adjacência A, o valor (i, j) da matriz An é número de 
sequências de lados de comprimento n que ligam vi a vj.
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.