Algoritmos em Grafos
Conceitos principais
Prof. André Renato
1º Semestre / 2012
O que é um grafo?
Um grafo G(V,E) é um conjunto finito
não-vazio de V e um conjunto E de pares
não ordenados de elementos distintos de
V.
 Os elementos de V são denominados
vértices e os elementos de E são
denominados arestas.
 A ordem de um grafo é a cardinalidade
do conjunto de vértices V.

Conceitos
Cada aresta e  E pode ser representada
pelos vértices (v1,v2) que a formam.
 Os vértices v1 e v2 são chamados de
extremos da aresta e. Também são
classificados como adjacentes.
 A aresta e é dita incidente a v1 e v2.
 Duas arestas que possuam um extremo
em comum são ditas adjacentes.

Conceitos
Um subgrafo G2(V2,E2) de um grafo
G1(V1,E1) é um grafo tal que V2  V1 e
E2  E1.
 Se além disso, G2 possuir toda aresta
(v,w) de G1 de forma que ambos v e w
estejam em G2, este é considerado
induzido pelo conjunto de vértices V2.

Conceitos
1
2
1
3
4
2
3
5
4
1
2
3
4
Conceitos

Normalmente um grafo pode ser
visualizado através da sua representação
geométrica, na qual os vértices são
representados por pontos (ou pequenos
círculos) e as arestas por linhas que
conectam estes pontos.
Conceitos

Como desenhar um grafo?
◦ O único cuidado que devemos ter para
representar corretamente um grafo é
preservar a correta relação de arestas com os
seus respectivos vértices incidentes.
Conceitos

Isomorfismo:
◦ Dadas duas representações geométricas
distintas, correspondem elas ao mesmo grafo?
◦ É possível fazer coincidir os vértices de duas
representações de modo a preservar as
relações de adjacência?
◦ Em caso afirmativo, os grafos são chamados
de isomorfos entre si.
Conceitos

1
Isomorfismo:
2
8
b
a
4
3
7
6
f
c
d
5
e
h
j
p
i
k
l
m
n
o
g
Conceitos

Existem arestas cujos extremos sejam o
mesmo vértice?
...
...
Sim; estas arestas são chamadas de laços
(loopback).
 Aplicações????

Conceitos

Pode existir grafos com mais de uma
aresta incidente aos mesmos vértices?
Sim; neste caso, o grafo é chamado de
multigrafo. As arestas são chamadas de
paralelas.
 Aplicações???

Conceitos
Uma aresta e, incidente a v1 e v2, provê
uma relação reflexiva entre estas vértices.
Ou seja, v1 está conectado a v2 da mesma
forma que v2 está conectado a v1.
 Uma aresta onde esta propriedade
reflexiva não esteja preservada é pode ser
chamada de arco e normalmente é
representada por uma seta.

v1
v2
Conceitos
Neste caso a relação de v1 para v2 é
distinta da relação de v2 para v1.
 Grafos que possuam arcos são chamados
de grafos direcionados (digrafos); os
demais, de grafos não-direcioanados.
 Uma aresta e = (v1,v2) pode ser
entendida como um par de arcos (v1,v2)
e (v2,v1).

v1
v2
v1
v2
Conceitos

Grau de um vértice v:
◦ é a quantidade total de arestas incidentes a v;
◦ Em grafos direcionados, existem o grau de
entrada e o grau de saída;
◦ Grau de entrada: é a quantidade de arcos que
chegam a v;
◦ Grau de saída: é a quantidade de arcos que
partem de v;
Conceitos

Grau de um vértice v:
◦ um vértice com grau de entrada zero é
chamado de fonte;
◦ um vértice com grau de saída zero é chamado
de sumidouro;
Conceitos
Vértices que possuam grau igual a zero, são
chamados de desconexos.
 G será totalmente desconexo se não possuir
arestas.
 Um grafo será considerado conexo se e somente
se for possível sair de v e chegar a w, para todo par
de vértices (v,w) do grafo. Será desconexo, caso
contrário.
 O grafo será fortemente conexo, se for possível
sair de v, chegar a w e voltar a v, para todo par de
vértices (v,w) do grafo.

Conceitos
 grau(v)  2 | E |
vV

Verificar!!!!
Conceitos
Qual a quantidade mínima de arestas um
grafo deve ter para não ser desconexo?
 Qual a quantidade máxima de arestas um
grafo pode ter?


Considerar |V| = n e |E| = m.
Conceitos

Grafos regulares são aqueles em que
todos os vértices possuem o mesmo
grau.
Conceitos
Seja G(V,E) um grafo conexo. Um corte
de vértices de G é um subconjunto de
vértices de G que, se forem removidos,
tornam G desconexo.
 É possível fazer uma analogia para um
corte de arestas.
 Conectividade de vértices e
conectividade de arestas é a
cardinalidade dos respectivos menores
subconjuntos.

Conceitos
1
1
3
3
4
2
5
5
7
4
2
2
6
1
8
7
6
5
8
7
6
8
•Seja um inteiro k positivo, diz-se que G é k-conexo em vértices
(arestas) quando sua conectividade de vértices (arestas) é ≥ k.
•O primeiro grafo é 1-conexo em vértices, 1- e 2-conexo em arestas.
•2-conexo -> biconexo
Conceitos
Uma articulação é um vértice v que, se
removido, torna o grafo desconexo.
 Uma ponte é uma aresta que causa o
mesmo efeito.

Componentes biconexos
(blocos)
Conceitos
Grafos que possuam arestas entre todos
os pares de vértices de V são chamados
de grafos completos.
 Um grafo completo pode ser
representado pela notação Kn, onde n é a
ordem do grafo.

K5
Conceitos

O complemento de um grafo G(V,E) é
em grafo G que possuam todos os
vértices de V e todas as arestas que faltam
a E para que G seja completo.
Conceitos
Clique é um subgrafo G2 de G1, tal que
G2 seja completo.
 Clique maximal é o subgrafo G2 de maior
ordem possível. Ou seja, é o maior
subgrafo completo de G1.

Conceitos
Em um grafo G(V,E), uma partição é a
divisão do conjunto V em dois ou mais
subconjuntos com interseção vazia. A
união desses subcojuntos deve resultar
em V.
 Além disso, as arestas de E só podem
conectar vértices de subcojuntos
distintos.
 O caso mais usual é de grafos bi-partidos
(bipartite).

Conceitos
Conceitos

Seja um grafo G(V,E) e um conjunto de
cores C={ci}, uma coloração de G é uma
atribuição de cores aos vértices de V, sem
que vértices adjacentes tenham a mesma
cor.
Conceitos
Uma k-coloração de G é uma coloração
que utiliza k cores. Diz-se que G é
k-colorível.
 O número cromático X(G) de um grafo
G é o menor número de cores k, para o
qual existe uma k-coloração.

Conceitos
Seja G um grafo e R sua representação
geométrica. R é dita plana quando não
houver cruzamento de linhas.
 Um grafo que possuir pelo menos uma
representação plana é chamado de
planar.

Conceitos
G é imersível em uma superfície S se
possuir uma representação R desenhada
em S, tal que duas linhas não se cruzem.
 Neste caso, as linhas dividem a superfície
em faces. Existem sempre uma face não
limitada chamada de externa.

f3
f2
f4
f1
Conceitos
Fórmula de Euler para poliedros:
n + f = m +2
 Cada face é limitada por, no mínimo 3
arestas. Cada aresta pertence a
exatamente duas faces. Logo, 2m ≥ 3f.
 Aplicando,
m ≤ 3n -6, para que um grafo seja planar.

Conceitos
Se a um grafo G(V,E) for associada uma
função f:E=>R, diz-se que o grafo é
ponderado em arestas.
 Em outras palavras, cada aresta do grafo
deve estar associada a um número real.

2
-0.5
3
-1
Conceitos
O valor associado a cada aresta é
chamado de peso da aresta.
 Uma aresta pode ter peso zero,
dependendo do problema relacionado.
 Um grafo também pode ter pesos
associados aos vértices. Neste caso, é
denominado ponderado em vértices.

Conceitos
Grafos que não possuam pesos, são
chamado de não-ponderados.
 Dependendo do problema a ser estudado,
valores específicos (pesos) podem ser
dados a vértices e arestas.
 Outro atributos também podem ser
associados a estes elementos.

Conceitos
Sejam G1(V,E1) e G2(V,E2) dois grafos
que compartilham o mesmo conjunto de
vértices, tal que E1 E2.
 Um grafo G(V,E) é considerado grafosanduíche de (G1,G2) se E contiver E1 e
estiver contido em E2.

Conceitos
G1
G2
G
G
G
G
G
G
G
Aplicações

Roteamento
2
1
3
3
2
2
3
4
1
Aplicações

Escalonamento
Aplicações

Redes
10
2
3
2
2
4
3
2
1
5
3
2
1
3
Exercícios

a)
b)
c)
d)
e)
f)
Identificar:
Ordem do grafo
Graus dos vértices
Dois isomorfos
Subgrafo induzido por {1,3,4,5,8}
Dois subgrafos não-induzidos por {2,4,6,7,8}
O grafo é conexo, fortemente conexo ou desconexo?
3
2
4
8
1
9
5
6
7
Exercícios

a)
b)
c)
d)
e)
f)
g)
Identificar:
Conectividade de vértices e arestas
Pontes e articulações
Dois blocos
Cliques de tamanho 3 ou maior
K-coloração (a menor possível)
Um subgrafo planar de ordem 5 ou maior
Complemento do grafo
3
2
4
8
1
9
5
6
7
Exercícios

Desenhar todos os grafos sanduíche:
3
3
2
5
1
8
2
4
5
1
6
7
4
8
6
7