Grafos

Prévia do material em texto

Grafos
Evando Carlos Pessini
UTFPR – Campus Medianeira
1
Indice
1. Histórico
2. Tipos de grafos
3. Conceitos Básicos
4. Representação de grafos
5. Subgrafos
6. Prática!
2
 Tudo começou no século XVIII, na
cidade medieval de Königsberg,
situada no leste europeu.
 Königsberg é banhada pelo rio
Pregel, que a divide em quatro áreas
de terra ligadas umas às outras por
sete pontes, as famosas “sete pontes
de Königsberg”.
Um pouco da história de Teoria de 
Grafos
Durante muito tempo, os habitantes daquela cidade
perguntavam-se se era possível cruzar as sete pontes
numa caminhada contínua, sem que se passasse duas
vezes por qualquer uma delas.
Leonhard Euler estudou este problema em 1736 e a
partir daí, desenvolveu toda a teoria que é hoje
utilizada nas mais diversas áreas que envolvem tarefas:
a Teoria de Grafos.
Definição de Grafo
 Um grafo G é um par (V,E) onde:
V ={v1,…,vn} é um conjunto de vértices
E = {e1,…,em} é um conjunto de arestas,
com cada ek  {vi, vj}, com vi, vj V, vi ≠ vj
Os vértices são representados como pontos e as 
arestas como linhas entre vértices
 Exemplo:
G = (V,E)
 V = {a,b,c,d }
 E = {{a,b}, {b,c}, {a,c}, {a,d}, {d,b} }
5
Tipos de grafos
 É importante lembrar que um mesmo grafo pode ter 
diferentes representações gráficas
 Exemplo:
Duas representações do mesmo grafo
G = ({a,b,c,d,e,f},
{{a,b},{a,e},{a,f}{e,f},{b,c},{c,d},{e,d},{d,f}})
6
Tipos de Grafos
 Se a ordem das arestas é importante, trata-se 
então de grafos dirigidos:
 Neste caso as arestas são chamadas de arcos
e são representadas como pares para indicar 
a ordem:
 V = { a,b,c,d,e}
 A ={(e,a), (a,b), (b,a), (d,a), (c,d), (d,c),(b,c),(c,b) }
7
Tipos de Grafos
 Se é permitida a existência de diversas arestas entre dois 
vértices, trata-se de multigrafos:
8
Tipos de Grafos
 Quando as arestas tiverem um valor numérico
associado, trata-se de grafos valorados:
 O valor numérico associado a cada aresta é
denominado custo.
9
Tipos de Grafos
 Os tipos de grafos mencionados anteriormente
podem ser combinados, originando por exemplo
multigrafos valorados, ou grafos dirigidos valorados,
etc.
 Em geral, tratamos com grafos ou multigrafos não
dirigidos, exceto quando explicitamente dito.
10
Conceitos Básicos
 Dois vértices são adjacentes se existir uma aresta que os
une.
 Os vértices que formam uma aresta são os extremos da
aresta.
 Se o vértice v é um extremo de uma aresta a, diz-se que a
é incidente em v.
 O grau de um vértice v, denotado por gr (v), é dado pelo 
número de aresta incidentes em v.
 Exemplo:
 gr(6)= _______ gr(1) = ________
11
Conceitos Básicos
 Teorema
Seja G=(V,A) um grafo. Então, ∑ gr(v) = 2|A|
v V
 Significado: a soma dos graus de todos os vértices é igual a 
duas vezes o número de arestas.
 Exemplo:
 gr(a)+gr(b)+gr(c)+gr(d)+gr(e)+gr(f) = 3+4+5+2+4+4 = 22
 2|A| = 2 ____ = _____
12
Conceitos Básicos
 Grafo completo é aquele em que todos os vértices são adjacentes.
 Para cada n ≥ 1, denomina-se grafo completo de ordem n e
representa-se por Kn, um grafo de n vértices conectados de todas
as formas possíveis:
13
Conceitos Básicos
 Denomina-se ciclo de grau n (denotado por Cn)
G=({v1,…,vn}, 
{{v1, v2}, {v2, v3},…, {vn-1, vn}, {vn, v1}} )
 Nota: A princípio, considera-se ciclos para n ≥ 3.
14
Representação de Grafos
 Para representar os grafos utiliza-se a chamada
matriz de adjacência.
 É construída imaginando-se que as linhas e colunas
correspondem aos vértices. Coloca-se o valor 0 para
indicar que dois vértices não são adjacentes e o
valor 1 para indicar que são adjacentes.
15
1
2
3
4
5
6
1 2 3 4 5 6
G
Matriz de Adjacência de G
Representação de Grafos
 No caso de grafo não dirigido, a matriz será simétrica. Isto não 
é igualmente verdadeiro para grafos dirigidos.
 No caso de grafos dirigidos, asume-se que a linha representa
o vértice de origem, e a coluna representa o vértice de
destino do arco.
16
Representação de Grafos
 A matriz de adjacência também permite
representar grafos valorados.
 O valor armazenado é o custo atribuído ao arco 
(aresta).
 Ao invés do valor 0, emprega-se um valor
especial  para indicar que dois vértices não
estão conectados.
17
Subgrafos
 Seja G=(V,A). G’=(V’,A’) é dito ser um subgrafo de G
se: 
1. V’  V
2. A’  A
3. (V’,A’) é um grafo.
 G1 e G2 são subgrafos de G.
18
Subgrafos
 Um grafo é dito cíclico quando contêm algum ciclo
como subgrafo
 Exemplo:
 Contêm 2 ciclos de longitude 3: 
 {a,e,f,a} e {_, _, _, _}
 Contêm 1 ciclo de longitude 6: {_,_,_,_,_,_,_}
 Mais algum ciclo?
19
Prática!
20