677184_Unidade 1

Prévia do material em texto

1
Unidade I
Conceitos Básicos (1)
Prof. Pasteur Ottoni de Miranda Junior e 
Prof. Max do Val Machado
Pontifícia Universidade Católica de Minas Gerais
1 Conjunto de transparências baseado no material da Profa. Raquel Mini
2
• Grafo é uma coleção de vértices e arestas
• Vértice é um objeto simples que pode ter 
nomes e outros atributos
• Aresta é uma conexão entre dois vértices
Definições
Por definição um grafo deve
ter pelo menos 1 vértice
e1
V1
V3
e2
V4
e4
e3
e5
V2
3
Exemplo:
Dados os conjuntos: A={1,2,3,4} 
B={2,3,6} C={7,10} D={7,8,9} 
E={1,3} F={}
Modelagem:
– Vértices = conjuntos
– Arestas = conjuntos com interseção 
não vazia
Definições
4
Aplicações: Problema das 
Pontes de Königsberg
No século XVIII havia na cidade de 
Königsberg um conjunto de sete pontes que 
cruzavam o rio Pregel . Elas conectavam duas 
ilhas entre si e as ilhas com as margens. 
Por muito tempo os habitantes daquela cidade 
perguntavam-se se era possível cruzar as 
sete pontes em uma caminhada contínua sem 
passar duas vezes por qualquer uma delas. 
5
Aplicações: Problema do 
desenho da casa
No desenho abaixo, uma criança diz ter 
posto a ponta do lápis em uma das 
bolinhas e com movimentos contínuos 
(sem levantar e sem retroceder o lápis) 
traçou as linhas que formam o desenho da 
casa, traçando cada linha uma única vez. 
A mãe da criança acha que ela trapaceou, 
pois a mãe não foi capaz de achar uma 
seqüência que pudesse produzir tal 
resultado. Você concorda com a mãe? 
6
Aplicações: O Problema das 
três casas e três serviços
Suponha três casas e três serviços, a 
exemplo de:
É possível conectar cada serviço a cada 
uma das três casas sem que haja 
cruzamento de tubulações?
GÁS LUZ ÁGUA
7
Aplicações: Problema do 
caminho de custo mínimo
De forma a reduzir seus custos operacionais, 
uma empresa de transporte de cargas deseja 
oferecer aos motoristas de sua frota um 
mecanismo que os auxilie a selecionar o 
caminho de menor custo entre quaisquer 
duas cidades por ela servidas. Como realizar 
esta tarefa? 
8
Aplicações: 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 estabelecer uma 
viagem circular (que o leve ao ponto de 
partida) de forma a que ele visite cada cidade 
exatamente uma vez? 
9
• Grafo Direcionado G é um par (V,E), 
onde V é um conjunto finito e E é uma 
relação binária em V.
• Grafo não Direcionado G = (V,E) é um 
par onde o conjunto de arestas E consiste 
em pares de vértices não orientados. A 
aresta (vi,vj) e (vj,vi) são 
consideradas a mesma aresta.
Mais Definições
10
Mais Definições
• Loop: uma aresta associada ao par de 
vértices (vi,vi)
• Arestas paralelas: quando mais de uma 
aresta está associada ao mesmo par de 
vértices
• Grafo simples: um grafo que não possui 
loops e nem arestas paralelas
• Dois vértices são ditos adjacentes se eles 
são pontos finais de uma mesma aresta
• Duas arestas não paralelas são 
adjacentes se elas são incidentes a um 
vértice comum
• Quando um vértice vi é o vértice final de 
alguma aresta ej, vi e ej são incidentes
11
Mais Definições
• O número de arestas incidentes a um 
vértice vi é chamado de grau, d(vi), do 
vértice i
A soma dos graus de todos os vértices de 
um grafo G é duas vezes o número de 
arestas de G.
• TEOREMA: O número de vértices de 
grau ímpar em um grafo é par
∑
i= 1
n
dvi= 2 e
∑ ∑∑
n
=i
kd(v
k
jd(v
ji
ímpar)
)d(v
par)
+)d(v=)d(v
1
12
Mais Definições
• Um grafo no qual todos os vértices 
possuem o mesmo grau é chamado de 
grafo regular
• Um vértice com nenhuma aresta incidente 
é chamado de vértice isolado
• Um vértice com grau 1 é chamado de 
vértice pendente
• Um grafo sem arestas é chamado de grafo 
nulo. Todos os vértices em um grafo nulo 
são vértices isolados
• Um grafo G=(V,E) é completo se para 
cada par de vértices vi e vj existe uma 
aresta entre vi e vj. Em um grafo completo 
quaisquer dois vértices distintos são 
adjacentes (Kn)
13
Mais Definições
• Grafo conexo: existe pelo menos um 
caminho entre todos os pares de vértices 
de G
• Um grafo desconexo consiste de 2 ou mais 
grafos conexos. Cada um dos subgrafos 
conexos é chamado de componente
grafo desconexo com 5 componentes
14
Mais Definições
√ Loop
√ Arestas paralelas
√ Grafo simples
√ Adjacência
√ Incidência
√ Grau de um vértice
√ Grafo regular
√ Vértice isolado
√ Vértice pendente
√ Grafo nulo
√ Grafo completo
√ Grafo conexo
√ Componente
15
Estrutura de Dados:
Matriz de Incidências
• A matriz de incidências de um grafo G
sem loops com N vértices e E arestas é
uma matriz N x E, definida como:
– Mij = 1; se a j-ésima aresta é incidente 
ao i-ésimo vértice, e
– Mij = 0; caso contrário.
16
A B C D E F G H
v1 0 0 0 1 0 1 0 0
v2 0 0 0 0 1 1 1 1
v3 0 0 0 0 0 0 0 1
v4 1 1 1 0 1 0 0 0
v5 0 0 1 1 0 0 1 0
v6 1 1 0 0 0 0 0 0
Estrutura de Dados:
Matriz de Incidências
17
• A matriz de adjacências de um grafo 
simples G com N vértices é uma matriz 
N x N, definida como:
– Mij = 1; se existe uma aresta entre 
os vértices i e j, e
– Mij = 0; caso contrário.
Estrutura de Dados:
Matriz de Adjacências
18
v1 v2 v3 v4 v5 v6
v1 0 1 0 0 1 1
v2 1 0 0 1 1 0
v3 0 0 0 1 0 0
v4 0 1 1 0 1 1
v5 1 1 0 1 0 0
v6 1 0 0 1 0 0
Estrutura de Dados:
Matriz de Adjacências
19
• Armazena apenas os elementos diferentes 
de zero da matriz de adjacências. 
Consiste de uma lista para cada vértice do 
grafo contendo todos os vértices 
adjacentes a ele.
Estrutura de Dados:
Lista de Adjacências
20
2 4
1 3
2 4 4
1 3 3
11
2
3
4
Estrutura de Dados:
Lista de Adjacências
21
• As matrizes de adjacências são 
apropriadas para:
– Grafos densos (E é próximo a N*N).
– Quando precisa-se saber de forma 
rápida se existe uma aresta 
conectando dois vértices quaisquer.
• As listas de adjacências são apropriadas 
para grafos esparsos.
• O custo para determinar se dois vértices 
são adjacêntes em uma lista de 
adjacências é elevado.
Estrutura de Dados:
Considerações
22
Isomorfismo
• Dois grafos G e H são ditos isomorfos se 
existir uma correspondência um-para-um 
entre seus vértices e entre suas arestas, 
de maneira que as relações de incidência 
são preservadas
a
b
c
d
e
1 2
34
5
a b c
d e f
1 2
3
45
6
23
• Condições necessárias mas não 
suficientes para que G e H sejam 
isomorfos:
– mesmo número de vértices
– mesmo número de arestas
– mesmo número de componentes
– mesmo número de vértices com o mesmo 
grau 
• Exemplo:
a b c
d
e f
5
6
1 2 3 4
Obs. Não existe um algoritmo eficiente para 
determinar se dois grafos são isomorfos
Isomorfismo
24
Grafo Complementar
• Seja G = (V,E) um grafo simples dirigido 
ou não-dirigido
• O complemento de G, C(G), é um grafo 
formado da seguinte maneira:
– Os vértices de C(G) são todos os vértices 
de G
– As arestas de C(G) são exatamente as 
arestas que faltam em G para formarmos 
um grafo completo
• Encontre um grafo com 5 vértices que 
seja isomorfo a seu complemento.
• Qual o número de arestas de um grafo 
que é isomorfo a seu complemento?
25
Grafo Bipartite
• Um grafo é bipartite se o conjunto de 
vértices V pode ser particionado em 2 
subconjuntos V1 e V2 tal que não existem arestas 
entre dois vértices de um mesmo subconjunto.
a
b
c
1
2
a b
c d
26
Subgrafos
• Um grafo g é dito ser um subgrafo de um 
grafo G se todos os vértices e todas as 
arestas de g estão em G
• Observações:
–todo grafo é subgrafo de si próprio
–o subgrafo de um subgrafo de G é subgrafo de 
G
–um vértice simples de G é um subgrafo de G
–uma aresta simples de G (juntamente com 
suas extremidades) é subgrafo de G
• Encontre todos os subgrafos de G
v1
v2
e1
G
27
Subgrafos
• Subgrafos disjuntos de arestas: dois (ou 
mais) subgrafos g1 e g2 de um grafo G são 
disjuntos de arestas se g1 e g2 nãotiverem 
nenhuma aresta em comum.
⇒ g1 e g2 podem ter vértices em comum?
• Subgrafos disjuntos de vértices: dois (ou 
mais) subgrafos g1 e g2 de um grafo G são 
disjuntos de vértices se g1 e g2 não tiverem 
nenhum vértice em comum.
⇒ g1 e g2 podem ter arestas em comum?