Algoritmos em Grafos
Celso C. Ribeiro
Caroline T. Rocha
PARTE 1: CONCEITOS BÁSICOS
Algoritmos em Grafos
2
Conceitos Básicos
Grafo: Geometricamente, um grafo é um conjunto de
pontos (vértices ou nós) conectados por linhas (arestas).
v1
v5
G = (V,
e E)
e2
e3
v2
v3
v4
vérticese6
e10
e8
5
e4
e1
v8
e7
e12
v7
e9
arestas
v6
e11
v9
V = {v1, v2, ..., vn}
|V | = n
V = {v1, vE2,=v3{e
, v1,4,ev2,5,...,
v6,evm7}, v8, v|9E}| = mn = 9
E = {e1, e2, e3, e4,..., e9, e10, e11, e12} m = 12
Algoritmos em Grafos
3
Conceitos Básicos
Cada aresta é definida por um par não-ordenado de
nós, que são suas extremidades:
e = (vi , vj)
u e v são adjacentes
e é incidente a v
e é incidente a u
e = (u, v)
d(v) : grau do nó v = número de arestas incidentes a v
e5, e7 , e8(nós
incidentes
a v5
adjacentes)
a v4), v=
v7
6, 2
d(v ) = d(v v) 5 =adjacente
d(v ) = d(v
1
2
8
9
d(v3) = d(v4) = d(v5) = d(v6) = 3
d(v7) = 4
d(v) = 0
vértice isolado
Algoritmos em Grafos
4
Conceitos Básicos
Teorema: o número de nós de grau ímpar em um grafo finito é
par.
Demonstração:
d (v i )  2. | E |

i V

e1
e = (u, v) é um laço se u = v
arestas paralelas possuem as
mesmas extremidades
e4
e2
e3
e5
Multi-grafo: sem laços, mas eventualmente com arestas paralelas
Grafo simples (grafo) : sem laços nem arestas paralelos
Algoritmos em Grafos
5
Conceitos Básicos
Kn: grafo completo com n nós
número de arestas: n(n-1)/2
K3
K4
K5
Grafo k-regular: todos os nós têm grau k.
Kn é (n-1)-regular
Algoritmos em Grafos
6
Conceitos Básicos
Grafo bipartido: o conjunto de nós pode ser particionado
em dois subconjuntos V1 e V2 tais que qualquer aresta
possui uma extremidade em V1 e a outra em V2.
V1
É bipartido?
SIM
V2
Km,n: grafo bipartido completo
onde |V1| = m e |V2| = n
É bipartido?
NÃO
Algoritmos em Grafos
7
Conceitos Básicos
G '  (V ' , E ' ) é um subgrafo de G  (V , E ) :
V ' V , E '  E
Grafo induzido em G  (V , E ) por X V :
G (X )  (X , E (X ))
onde E(X) é o subconjunto de E formado por todas as
arestas com as duas extremidades em X.
2
1
G
6
X = {2, 3, 4, 5}
4
3
G(X)
5
Algoritmos em Grafos
8
Conceitos Básicos
Clique: subconjunto de nós que induz um subgrafo completo.
5
C1 = {1, 2, 3}
C2 = {2, 4, 5}
2
1
6
3
C3 = {4, 6}
C4 = {3}
4
G  (V , E ) e G  (V , E ) são complementares:
(i , j )  E  (i , j )  E
1
2
(i , j )  E  (i , j )  E
3
G
4
1
2
3
4
G
Algoritmos em Grafos
9
Conceitos Básicos
Caminho de v i a v j :
Seqüência P de vértices e arestas alternados, tais que cada
aresta é incidente ao nó anterior e ao nó posterior.
v i  v j  P é um ciclo ou circuito.
Caminho simples: cada vértice aparece exatamente uma vez
Comprimento de um caminho: número de arestas
Caminhos disjuntos em vértices/arestas: não têm
vértices/arestas em comum
Algoritmos em Grafos
10
Conceitos Básicos
Vértices vi e vj são conectados se existe um caminho de vi a vj.
Dois vértices vi e vj estão na mesma componente conexa se
existe um caminho entre eles.
Um grafo é conexo se possui uma única componente conexa,
ou seja, se existe um caminho entre qualquer par de nós
Problema importante: determinar se um grafo é conexo ou não.
É conexo?
Algoritmos em Grafos
11
Conceitos Básicos
Um grafo gerador de um grafo conexo G=(V,E) é um subgrafo
conexo G’ com o mesmo conjunto de nós V.
Grafo G
Grafo gerador de G
v é um ponto de articulação do grafo conexo
G se sua remoção desconecta G.
v
Se uma componente conexa de um grafo não contem ponto de
articulação, então ela é uma componente 2-conexa.
Uma aresta e cuja remoção desconecta um
grafo conexo é chamada de ponte.
e
Algoritmos em Grafos
12
Conceitos Básicos
Digrafo ou grafo orientado: grafo no qual são associadas
direções aos seus arcos.
G  (V , A)
V  {v 1 ,...,v n }
A  {a1 ,...,am }
a  (i , j ) V V
Início ou origem
j é sucessor de i
i
par ordenado
Fim ou destino
2
j
i é predecessor de j
d  (i )
= grau de entrada de i
= número de predecessores de i
d  (i )
= grau de saída de i
= número de sucessores de i
4
1
3
5
d  (1)  1
d  (4)  0
d  (4)  3
d  (6)  1
6
Algoritmos em Grafos
13
Conceitos Básicos
Uma cadeia a1, a2, ..., aq de arcos é uma seqüência tal que
cada arco ai tem uma extremidade comum com o arco ai-1 e
outra com o arco ai+1, 2 ≤ i ≤ q-1.
2
a1
a3
5
a2
1
a4
a6
a5
3
a7
a2, a5, a6, a4  cadeia entre os nós 2 e 3
4
Ciclo: cadeia cujas extremidades coincidem.
Caminho a1, a2,..., aq: extremidade final do arco ai coincide
com a extremidade inicial do arco ai+1.
Circuito: caminho cujas extremidades coincidem.
Algoritmos em Grafos
14
Conceitos Básicos
Dois vértices vi e vj estão na mesma componente fortemente
conexa de um grafo orientado se existe um caminho de vi a
vj e um caminho de vj a vi.
7
6
2
8
1
{1, 2, 3, 4, 5, 6, 8, 9, 10}
{7}
5
3
10
9
4
1
4
7
{1, 2, 3, 4}
{5, 6, 7}
2
3
6
5
Algoritmos em Grafos
15
Conceitos Básicos
Grafos planares:
Um grafo é planar se ele pode ser representado no plano de
modo tal que não haja interseção entre suas arestas.
K3 ?
PLANAR
K4 ?
PLANAR
K5 ?
NÃO
K3,3 ?
NÃO
Algoritmos em Grafos
16
Conceitos Básicos
Árvore: grafo conexo sem circuitos
Floresta: grafo cujas componentes conexas são árvores
Um caminho é uma árvore?
Sim!
Algoritmos em Grafos
17
Conceitos Básicos
Teorema: Se T é uma árvore com n vértices, então:
1. Existe um único caminho entre dois nós quaisquer de T.
2. Sejam i, j dois nós de T tais que a aresta (i, j) não existe.
Então, a inserção da aresta (i, j) em T provoca a formação
de exatamente um ciclo.
3.
T possui n-1 arestas.
Algoritmos em Grafos
18
Conceitos Básicos
Formas de representação e matrizes associadas a um grafo
Matriz de incidência nó-arco:
Uma linha para cada nó
Uma coluna para cada aresta
G  (V , A)
|V | n
| A | m
1
a1
a2
4
a5
a  (i , j )  A
2
a4
a
a3
3
Am n
 0
i   1
 0
 
j   1
 0 
0
0
0
 1  1



1
0

1

1
0


 0 1 1
0  1


0
0  1  1
 0
Algoritmos em Grafos
19
Conceitos Básicos
Formas de representação e matrizes associadas a um grafo
Uma matriz quadrada é unimodular se seu determinante é 1.
Uma matriz retangular A é totalmente unimodular se e
somente qualquer matriz quadrada regular extraída de A é
unimodular.
Algoritmos em Grafos
20
Conceitos Básicos
Formas de representação e matrizes associadas a um grafo
Teorema: A matriz de incidência de um grafo é totalmente
unimodular.
Uma matriz de incidência contém exatamente dois elementos nãonulos por coluna (+1, -1).
Demonstração por indução:
1. Todas as matrizes quadradas regulares de dimensão 1 são
unimodulares (det = 1).
2. Suponha a hipótese verdadeira até matrizes de ordem n-1 e
considere uma matriz quadrada A’ de ordem n extraída de A.
Se toda coluna de A’ tem dois elementos não-nulos, então
det(A’) = 0 (soma das linhas nulas).
Se uma coluna de A’ não tem elementos não-nulos, então
det(A’) = 0.
Algoritmos em Grafos
21
Conceitos Básicos
Formas de representação e matrizes associadas a um grafo
Se existe uma coluna com um único coeficiente não-nulo, então
det(A’) =  det(A’’), onde A’’ é a matriz quadrada de ordem n-1
extraída de A’ pela eliminação da linha i e da coluna j. Como a
hipótese é verdadeira para n-1, det(A’’) = 1 ou 0. Logo,
det(A’) = 1 ou 0.
j
A' 


i



1







Algoritmos em Grafos
22
Conceitos Básicos
Formas de representação e matrizes associadas a um grafo
Matriz de adjacência:
Uma linha para cada nó
Uma coluna para cada nó
a12
1
2
a24
a13
a34
4
aij = 1  (i , j )  A
aij = 0  (i , j )  A
a23
An n
3
0

0


0

0
1
0
0
0
1
1
0
0
0

1
1

0
Grafos sem arcos paralelos:
1
2
1
2
4
3
n2 posições
4
3
Algoritmos em Grafos
23
Conceitos Básicos
Formas de representação por listas de adjacências
Lista de nós:
Cada nó aponta para a lista de seus sucessores (ou nós
adjacentes)
2
1
n nós  n +m posições
m arestas
4
nós
3
sucessores
nós
predecessores
1
2
3
1
2
3
4
2
1
3
4
3
1
2
4
2
3
4
Algoritmos em Grafos
24
Conceitos Básicos
Formas de representação por listas de adjacências
1
3
Lista de arcos
2
1
4
1
2
3
4
n
1
3
5
7
m
1
3
1
3
2
1
1
2
3
4
5
6
7
2
S(.)
1
1
1
2
4
4
T(.)
2
3
4
3
2
3
3
É simples passar de uma forma de representação para outra.
Algoritmos em Grafos
25
Conceitos Básicos
Desenhar o grafo representado pela matriz de adjacência
abaixo:
0
0

0
A
0
0

 1
1
2
1
1 0 0 0 1
0 1 0 0 1
0 0 1 0 0

0 1 0 0 0
1 0 1 0 0

0 1 0 1 0 
3
4
5
6
7
8
1
2
5
3
6
5
2
8
7
4
6
3
11
9
4
10
9 10 11
Quais1 são
conexas deste grafo?
1  1componentes
0 0 0 0 0 fortemente
0 0 0
 1  as


2  1 {3,4}
0
0
0

1
0

1

1
0
0
0
{1,2,5,6},


3  0

0
0 1
0
0 0 matriz
0 0
4  0 0 sua
Representar
5  0
0  1  1

0de 0incidência.
 1  1  1
0  1  1 0 0

0 0 0 0 0
0 1
0 0 0 0 1

6  0  1  1  1  1  1
0
Algoritmos em Grafos
26
Conceitos Básicos
Representar o mesmo grafo por sua lista de adjacências.
1
2
6
2
3
6
3
4
4
1
1
2
5
3
6
3
5
5
2
4
6
1
3
2
8
7
4
6
3
11
9
4
5
10
Representar o grafo por sua lista de arcos.
1
2
3
4
5
6
7
8
9
10
11
1
1
6
6
2
6
2
5
5
3
4
2
6
1
3
6
5
3
2
4
4
3
Algoritmos em Grafos
27
Conceitos Básicos
Algoritmo para converter uma representação de um grafo orientado
sob forma de matriz de adjacência em matriz de incidência.
Ler número de nós n, matriz A
linha  1, coluna  1, arco  0
Enquanto linha ≤ n faça
Enquanto coluna ≤ n faça
Se A(linha,coluna)=1 então
arco  arco+1, k  1
Enquanto k ≤ n faça
B(k,arco)  0
k  k+1
fim_enquanto
B(linha,arco)  +1
B(coluna,arco)  -1
fim_se
coluna  coluna +1
fim_enquanto
coluna  1
linha  linha +1
fim_enquanto
Algoritmos em Grafos
28
Conceitos Básicos
Exercício: Escrever um algoritmo para converter a representação
de um grafo orientado sob forma de matriz de incidência
em uma representação por listas de adjacência.
Algoritmos em Grafos
29