Teoria dos Grafos
e
Otimização com Grafos
POP2 – UDESC
Prof. Adelmo A. Martins
Aspectos históricos
Euler resolveu o problema das pontes de Königsberg do rio
Pregel, em 1736, utilizando um modelo de grafos: partir de uma
das 4 regiões, atravessar cada ponte uma única vez e retornar à
região de partida.
Figura 1. Rio Pregel e suas sete pontes.
Figura 2. Leonhard Euler.
Definições
• Dado um conjunto V, denotaremos V(2) o conjunto de
todos pares não ordenados de elementos de V. Se V tem
n elementos então V(2) tem n(n-1)/2 elementos.
• Os elementos de V(2) serão identificados com os
subconjuntos de V que têm cardinalidade 2. Assim, cada
elemento de V(2) terá a forma {v, w}, sendo v e w dois
elementos distintos de V.
• Um grafo é um par (V, A) em que V é um conjunto
arbitrário e A é um subconjunto de V(2). Os elementos de
V são chamados vértices e os de A são chamados arestas.
Definições
• Uma aresta como {v, w} será denotada simplesmente por
vw ou por wv. Diremos que a aresta vw incide em v e em
w e que v e w são as pontas da aresta. Se vw é uma
aresta, diremos que os vértices v e w são vizinhos ou
adjacentes.
• De acordo com a definição, um grafo não pode ter duas
arestas diferentes com o mesmo par de pontas (ou seja,
não pode ter arestas “paralelas”). Também não pode ter
uma aresta com pontas coincidentes (ou seja, não pode
ter “laços”). Há quem goste de enfatizar esse aspecto da
definição dizendo que o grafo é “simples” ou
simplesmente conectado.
Teoria dos Grafos
• A teoria dos Grafos fornece uma linguagem para
tratarmos com as propriedades dos grafos.
• São uma maneira de modelar problemas.
• Muitos problemas algorítmicos são simplificados ao
pensar neles em termos de grafos.
Aplicações
1. Grafos planares: problemas de linhas montagens/trevos
A
D1
A, B, C : linhas de montagens/rodovias
principais
B
D2
D1, D2, D3: departamentos/rodovias
secundárias
C
D3
Ligações: esteiras/viadutos ou túneis
Aplicações
2. Problemas de Localização
Existindo n cidades consumidoras de um produto fabricado por
uma determinada empresa, deseja-se saber onde seria o melhor
local para a instalação de uma filial que atendesse as n cidades
com menor custos de distribuição deste produto.
Sendo este um problema específico, existem algoritmos próprios
para sua solução, além de várias heurísticas que possuem bom
desempenho.
Mais Definições
• Diz-se que um grafo é fracamente conectado (ou
simplesmente conectado) se existe pelo menos uma
cadeia entre quaisquer dois de seus nós, e é fortemente
conectado se existe pelo menos um caminho de cada nó
a todos os demais nós do grafo. Para efeitos da disciplina
trataremos de grafos fortemente conectados.
• Uma árvore é um grafo conectado sem ciclos.
• Um Grafo G’ = (N’, E’) é um subgrafo de G = (N,E) se N’
está contido (ou seja igual) em N e E’ está contido (ou
seja igual) em E, com a condição de que se (i,j) pertence a
E’ e i e j também pertencem a N’.
Mais Definições
• Diz-se que um grafo é fracamente conectado (ou
simplesmente conectado ou simples) se existe pelo menos
uma cadeia entre quaisquer dois de seus nós, e é
fortemente conectado se existe pelo menos um caminho de
cada nó a todos os demais nós do grafo. Neste caso, poderá
existir laços e arestas paralelas.
S1
3
1
S2
4
2
6
5
7
8
O grafo acima não é fortemente conectado mas os subgrafos
S1 e S2 são.
Mais Definições
• Relembrando, uma árvore é um grafo conectado sem
ciclos.
Ex.
5
3
4
1
2
Um Grafo G’ = (N’, E’) é um subgrafo de G = (N,E) se N’ está
contido (ou seja igual) em N e E’ está contido (ou seja igual)
em E, com a condição de que se (i,j) pertence a E’ e i e j
também pertencem a N’.
Mais Definições
• Uma árvore geradora de um grafo G é um subgrafo de G
que é uma árvore e inclui TODOS os nós do grafo G.
Exemplo. Indique possíveis árvores geradoras para o
seguinte grafo.
3
1
4
2
Mais Definições
São possíveis árvores geradoras as seguintes:
3
1
4
3
2
1
4
2
3
1
4
2
Mais Definições
Considerações sobre árvores geradoras:
• Seja um grafo G = (N,E) com |N| = n, isto é, G tem n
nós, e um subgrafo G’ = (N,E’) de G. O subgrafo G’ =
(N, E’) é uma árvore geradora de G se:
• 1. |E’| = n - 1 (n - 1 arcos) e G’ é conectado
ou
• 2. |E’| = n - 1 e G’ não tem ciclos
• Em outras palavras, toda árvore geradora de um grafo
com n nós tem n – 1 arcos, e basta que seja um
subgrafo conectado ou sem ciclos.
Mais Definições
Utilizando a definição detalhada anteriormente, NÃO SÃO
árvores geradoras do exemplo anterior, os seguintes
subgrafos:
3
1
4
2
3
1
4
2
Mais Definições
• Uma árvore geradora de um grafo G é um subgrafo de G
que é uma árvore e inclui TODOS os nós do grafo G.
Exemplo. Indique as possíveis árvores geradoras para o
seguinte grafo.
3
1
4
2
Mais Definições
São as seguintes:
3
1
4
3
2
1
4
2
3
1
4
2
Mais Definições
Considerações sobre árvores geradoras:
• Seja um grafo G = (N,E) com |N| = n, isto é, G tem n nós,
e um subgrafo G’ = (N,E’) de G. O subgrafo G’ = (N, E’) é
uma árvore geradora de G se:
• 1. |E’| = n - 1 (n - 1 arcos) e G’ é conectado
ou
• 2. |E’| = n - 1 e G’ não tem ciclos
• Em outras palavras, toda árvore geradora de um grafo
com n nós tem n – 1 arcos, e basta que seja um subgrafo
conectado ou sem ciclos.
Representação dos Grafos
1. Matemática G(V, A) onde:
V = Conjunto de vértices ou nós do grafo
A = Conjunto de arcos ou arestas do grafo
2. Diagramas
2
a
2
c
a
3
1
b
Grafo não Orientado
c
3
1
b
Grafo Orientado
Representação dos Grafos
3. Matriz de adjacência (grafo não-orientado)
1, se  aresta do nó i ao nó j
A = (aij) = 
0, se  aresta do nó i ao nó j
2
c
a
Onde A =
3
1
b
10

2 1
3 1
1
1
0
1
2
1

1
0
3
Representação dos Grafos
3. Matriz de incidência (grafo orientado)
A = (aij) é a matriz (não necessariamente quadrada) de incidência
de G na qual
 1, se o arco j sai do nó i

aij  -1, se o arco j chega no nó i
 0, se o arco j não é incidenteao nó i

Representação dos Grafos
3. Matriz de incidência (grafo orientado)
A = (aij) é a matriz (não necessariamente quadrada) de incidência
de G na qual
 1, se o arco j sai do nó i

aij  -1, se o arco j chega no nó i
 0, se o arco j não é incidenteao nó i

Tipos de Grafos
Valorado
RJ
400
SP
MG
700
1500
RS
d
a
e
h
c
f
i
b
Especial
d
g
Tipos de Grafos
Árvore – Grafo conexo sem ciclos
e
a
f
d
b
c
e
Cadeia – sequência de arcos com extremidade em comum
a
b
d
c
Tipos de Grafos
Caminho – sequência de arcos com mesma orientação
f
e
a
b
d
c
Tipos de Grafos
d
Ciclo – Cadeia fechada
l
a
i
b
g
a
c
Circuito – Caminho Fechado
b
Problema da Árvore Mínima
Também chamado de árvore geradora mínima, ou custo
mínimo, este problema também está relacionado à menor
distância. Tem várias aplicações práticas diretas ou apresentase como um subproblema de outros problemas mais
complexos.
Exemplo de Problema.
•
Como ligar a fibra ótica a todos departamentos da empresa
a um custo mínimo?
Algoritmo de Kruskal
Determinação de uma árvore mínima num grafo G (V, A)
Para cada aresta (i, j) existe um custo associado Cij.
|V| = cardinalidade do conjunto de nós V = número de nós.
1. Considerar o grafo trivial formado apenas pelos nós de G
2. Para construção da árvore acrescentar ao grafo trivial a
aresta (i,j) associada ao menor valor de custo Cij. Repetir
o procedimento respeitando a ordem crescente de
valores de Cij, desde que a aresta analisada não forme
ciclo com as arestas já incorporadas à árvore.
Após incorporar |V| - 1 arestas parar! A árvore mínima foi
obtida.
Algoritmo de Kruskal - Exercício
Determinar a Árvore Mínima para o grafo abaixo
A
8
2
7
2
1
E
3
S
C
4
2
1
1
7
2
B
T
D
Algoritmo de Kruskal - Exercício
Solução:
Custo Mínimo = 1 + 1 + 1 + 2 + 2 + 2 = 9
A
8
2
7
2
1
E
3
S
C
4
2
1
1
7
2
B
T
D