Algoritmos em Grafos

Algoritmos em GrafosAlgoritmos em Grafos

Celso C. RibeiroCaroline T. Rocha

22Algoritmos em Algoritmos em GrafosGrafos

PARTE 1: CONCEITOS BÁSICOS


e3

e2

e4

e5

e9e6

e8

e10

e11

e1 e12e7

v1

v2

v3 v4

v5

v6

v7

v8

v9

V = {v1, v2, v3, v4, v5, v6, v7, v8, v9} n = 9E = {e1, e2, e3, e4,..., e9, e10, e11, e12} m = 12

V = {v1, v2, ..., vn} |V| = n E = {e1, e2, ..., em} |E| = m

G = (V, E)

vértices arestas

Conceitos BásicosConceitos BásicosGrafo: Geometricamente, um grafo é um conjunto de pontos (vértices ou nós) conectados por linhas (arestas).


Conceitos BásicosConceitos BásicosCada aresta é definida por um par não-ordenado de nós, que são suas extremidades:

e = (vi , vj)

e = (u, v) u e v são adjacentese é incidente a ve é incidente a u

e5, e7 , e8 incidentes a v5

v5 adjacente a v4, v6, v7

d(v) : grau do nó v = número de arestas incidentes a v (nós adjacentes)

d(v1) = d(v2) = d(v8) = d(v9) = 2d(v3) = d(v4) = d(v5) = d(v6) = 3d(v7) = 4

d(v) = 0 vértice isolado


Conceitos BásicosConceitos Básicos

Teorema: o número de nós de grau ímpar em um grafo finito é par.

Demonstração: ||.2)( EvdVi

i

e5

e4

e2 e3

e1

e = (u, v) é um laço se u = varestas paralelas possuem as mesmas extremidades

Multi-grafo: sem laços, mas eventualmente com arestas paralelasGrafo simples (grafo) : sem laços nem arestas paralelos



Kn: grafo completo com n nósnúmero de arestas: n(n-1)/2

Grafo k-regular: todos os nós têm grau k.

K3 K4 K5

Kn é (n-1)-regular



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.

Km,n: grafo bipartido completo onde |V1| = m e |V2| = n

É bipartido?

É bipartido?

SIM

NÃO

V1 V2



é um subgrafo de :

Grafo induzido em por :

onde E(X) é o subconjunto de E formado por todas as arestas com as duas extremidades em X.

G(X)

G X = {2, 3, 4, 5}

1 2

34

5

6

),( EVG

),( EVG EEVV ','

VX

)','(' EVG

))(,()( XEXXG



Clique: subconjunto de nós que induz um subgrafo completo.

),( EVG

C1 = {1, 2, 3}1

3

2

4

5

6 C2 = {2, 4, 5}C3 = {4, 6}C4 = {3}

e são complementares:),( EVG EjiEji ),(),(EjiEji ),(),(

G

1

3

2

4

1

3

2

4G



Caminho de a :Seqüência P de vértices e arestas alternados, tais que cada aresta é incidente ao nó anterior e ao nó posterior. P é um ciclo ou circuito.

iv jv

ji vv

Caminho simples: cada vértice aparece exatamente uma vez

Comprimento de um caminho: número de arestasCaminhos disjuntos em vértices/arestas: não têm vértices/arestas em comum



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

É conexo?

Problema importante: determinar se um grafo é conexo ou não.


Um grafo gerador de um grafo conexo G=(V,E) é um subgrafo conexo G’ com o mesmo conjunto de nós V.


v

e

Grafo G

Grafo gerador de G

v é um ponto de articulação do grafo conexo G se sua remoção desconecta G.

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.



Digrafo ou grafo orientado: grafo no qual são associadas direções aos seus arcos.

),( AVG },...,{ 1 nvvV },...,{ 1 maaA VVjia ),( par

ordenadoInício ou origem Fim ou destino

1

2

3

4

56

)(id

)(id

= grau de entrada de i = número de predecessores de i= grau de saída de i = número de sucessores de i

i j

j é sucessor de ii é predecessor de j

)1(d

)4(d

)4(d

)6(d

1

3

0

1



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.

32

41

5

a1 a2

a3

a5

a6

a4

a7

a2, a5, a6, a4 cadeia entre os nós 2 e 3

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.



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.

{1, 2, 3, 4, 5, 6, 8, 9, 10}{7}

{1, 2, 3, 4}{5, 6, 7}

3

2

4

15

6 7

910

8

32

41

56

7



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 ?

K5 ?

K4 ?

K3,3 ?

PLANAR

NÃO

PLANAR

NÃO



Árvore: grafo conexo sem circuitos

Floresta: grafo cujas componentes conexas são árvores

Um caminho é uma árvore? Sim!



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.



Matriz de incidência nó-arco:Uma linha para cada nóUma coluna para cada aresta

Formas de representação e matrizes associadas a um grafo

),( AVG nV ||mA ||

Ajia ),(

01010

j

i

a

1 2

34

a1

a2

a3

a4

a5

11000101100110100011

nmA



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.




Teorema: A matriz de incidência de um grafo é totalmente unimodular.Uma matriz de incidência contém exatamente dois elementos não-nulos 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.




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.

1

'

i

Aj




Matriz de adjacência:Uma linha para cada nóUma coluna para cada nó

a23

1 2

34

a12

a13

a24

a34

0000100011000110

nnA

Grafos sem arcos paralelos:1 2

34

1 2

34

n2 posições


aij = 1 (i , j ) Aaij = 0 (i , j ) A



Lista de nós:Cada nó aponta para a lista de seus sucessores (ou nós adjacentes)

Formas de representação por listas de adjacências

1 2

34

n nós m arestas n +m posições

1

2

3

4

2 3

3 4

4

nós sucessores nós predecessores1

2

3

4

1

1 2

2 3


Conceitos BásicosConceitos BásicosFormas de representação por listas de adjacências

1 3 5 71

23 m

n1 2 3 4

1 3 1 3 2 11 2 3 4 5 6 7

Lista de arcos 1 2

34

S(.)

2 3 4 3 2 3

1 1 1 2 4 4

T(.)

É simples passar de uma forma de representação para outra.



Desenhar o grafo representado pela matriz de adjacência abaixo:

010101001010000100001000100100100010

A

Quais são as componentes fortemente conexas deste grafo?

Representar sua matriz de incidência.

{1,2,5,6}, {3,4}

1 2

3

4

56

1

2

3

4

5

6

7

8

910

11

0000011111000110100000111000000001100100100000011010001000000001111

2

3

4

5

6

1 2 3 4 5 6 7 8 9 10 11



Representar o mesmo grafo por sua lista de adjacências.

Representar o grafo por sua lista de arcos.

1

2

3

4

5

6

2 6

3 6

4

2 4

1 3

3

5

1 1 6 6 2 6 2 5 5 3 4

2 6 1 3 6 5 3 2 4 4 3

1 2 3 4 5 6 7 8 9 10 11

1 2

3

4

56

1

2

3

4

5

6

7

8

910

11


Conceitos BásicosConceitos BásicosAlgoritmo 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 Alinha 1, coluna 1, arco 0Enquanto 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 +1fim_enquanto



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.

Documents

Algoritmos em Grafos