AlgoritmosGrafosParte1

Algoritmos em Grafos

Celso C. Ribeiro
Caroline T. Rocha

PARTE 1: CONCEITOS BÁSICOS

Algoritmos em

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, e5 E)

e2 e4 e1 e3 v2

v3

v4

vérticese6

v8 e10 e8 e7 e12 v7 e9 arestas e11

v6

V = {v1, v2, ..., vn}
|V| = n
{e1, e2, ..., em}
|E| = m
V = {v1,Ev=
2, v 3 , v 4 , v 5 , v 6 , v 7, v 8 , v 9 } n = 9

E = {e1, e2, e3, e4,..., e9, e10, e11, e12}

v9

m = 12

Algoritmos em

3

Conceitos Básicos
Cada 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 adjacentes e é incidente a v e é incidente a u

d(v) : grau do nó v = número de arestas incidentes a v e5, e7 , e8 incidentes a v5
(nós adjacentes) v49,)v6= , v27 d(v1) = d(vv25) adjacente
= d(v8) = ad(v d(v3) = d(v4) = d(v5) = d(v6) = 3 d(v7) = 4 d(v) = 0

vértice isolado

Algoritmos em

4

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

 d (v ) 2. | E |

Demonstração:

i

i V

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

e1 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

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

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.
É bipartido?
V1

SIM
V2

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

NÃO

Algoritmos em

7

Conceitos Básicos
G ' (V ' , E ' ) é um subgrafo de
G (V , E )

:

V ' V , E '  E

X V
G (V , E )
Grafo induzido em por G ( X ) ( X , E ( X ))

:

onde E(X) é o subconjunto de E formado por todas
as