<<seu nome aqui!>>

Universidade Federal de Ouro Preto

DECEA / João Monlevade

A03 Conceitos

Básicos em Grafos

Prof. Dr. George H. G. Fonseca

Universidade Federal de Ouro Preto

CSI466 – Teoria dos Grafos

1

Definições

Um grafo G = (V, E) é um par de conjuntos (V, E):

Conjunto de Vértices V (pontos)

Conjunto de Arestas E (ligações)

G = (V, E)

Ordem

O número de vértices de um grafo G é denotado por |V| e é

conhecido como Ordem de G

2

V = {v1, ..., vn} E = {e1, ..., en}

Definições

Cada aresta é um subconjunto de elementos de V de

tamanho 2 (E ⊇ V x V)

Incidência

Uma aresta e = (v1, v2) é dita incidente a v1 e a v2

Os vértices que a aresta conecta também são ditos incidentes à

aresta

v1 e v2 são incidentes a e

e é incidente a v1 e a v23

v1 v2e

Definições

Adjacência

Dois vértices que são incidentes a uma mesma aresta são ditos

adjacentes ou vizinhos

v1 e v2 são adjacentes

Duas arestas que são incidentes a um mesmo vértice são ditas

adjacentes

e1 e e2 são adjacentes 4

v1 v2e

v1

v2

e1

v2e2

Definições

Grau de um vértice

O grau de um vértice é o número de arestas que nele incidem

Representação: d(v)

Se d(v) = 0, v é um vértice isolado

d(v1) = 2

d(v2) = 4

d(v3) = 3

d(v4) = 2

d(v5) = 1

d(v6) = 0 (isolado)5

Definições

Exercício

1. Considerando o seguinte grafo:

G = (V, E)

V = {v1, v2, v3, v4, v5}

E = {(v1, v2), (v1, v3), (v1, v5), (v2, v3), (v2, v4), (v3, v4), (v3, v5)}

a) Apresente uma representação gráfica para G

b) Determine o grau de cada vértice

c) Apresente as arestas incidentes a v5

d) Apresente os vértices adjacentes a v5

e) Apresente os vértices incidentes a e5

f) Apresente as arestas adjacentes a e5

6

e1 e2 e3 e4 e5 e6 e7

Definições

Solução do exercício

G = (V, E)

V = {v1, v2, v3, v4, v5}

E = {(v1, v2), (v1, v3), (v1, v5), (v2, v3), (v2, v4), (v3, v4), (v3, v5)}

d(v1) = 3

d(v2) = 3

d(v3) = 4

d(v4) = 2

d(v5) = 2

Incidentes a v5 = {e3, e7}

Adjacentes a v5 = {v1, v3}

Incidentes a e5 = {v2, v4}

Adjacentes a e5 = {e1, e4, e6}7

v1

v2 v3

v5v4

e1 e2e3

e4

e5 e6 e7

e1 e2 e3 e4 e5 e6 e7

Terminologia

Vértice isolado

Vértice de grau 0

Vértice pendente

Vértice de grau 1

Grafo nulo

Grafo sem nenhuma aresta

Grafo trivial

Grafo de apenas 1 vértice e nenhuma aresta8

Terminologia

Grafo regular

Grafo em que todos os vértices possuem o mesmo grau

Um grafo regular com vértices de grau r é chamado

grafo r-regular

Exemplos

9

Terminologia

Laço

Aresta associada a um par do mesmo vértice

a’ é um laço

Aresta paralela

Quando mais de uma aresta está associada ao mesmo vértice

b’ e b’’ são arestas paralelas

Grafo simples

Grafo não contem laço nem aresta paralela10

Terminologia

Grafo Completo

Grafo simples em que todo o par de vértices é ligado por aresta

Todo vértice é adjacente a todos os outros vértices

Um grafo completo com n vértices é denotado Kn

Exemplos

11

Terminologia

Grafo Complementar

Seja G = (V, E) um grafo simples, o complemento de G, G é o

grafo formado da seguinte maneira:

Os vértices de G são os mesmos de G

As arestas de G são exatamente as arestas que faltam em G para

formarmos um grafo completo

Exemplos

12

Terminologia

Subgrafos

Dois grafos G1 e G2 são iguais se V1 = V2 e E1 = E2

Um grafo Gs é um subgrafo de G se e somente se os conjuntos

de vértices e arestas de Gs estão contidos nos conjuntos de

vértices e arestas de G

13

G2 é subgrafo de G1

Terminologia

Grafo Dirigido

Um grafo é dirigido (dígrafo) se suas arestas possuem

orientação

Denomina-se arco a aresta direcionada

Em um grafo não dirigido, uma aresta pode ser representada por

(i, j) ou por (j, i). O mesmo não ocorre em um grafo dirigido

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

E = {(2, 3), (3, 1), (3, 5), (4, 3), (6, 6)}

14

Terminologia

Grafo Dirigido

Na versão dirigida G’ de um grafo não dirigido G = (V, E), cada

aresta não dirigida (i, j) de G dá origem a dois arcos (i, j) e (j, i)

em G’

15

Terminologia

Grafo Dirigido

Grau de vértices em grafo dirigido. Os vértices possuem:

Grau de entrada din(v): número de arcos que chegam ao vértice v

Grau de saída dout(v): número de arcos que saem do vértice v

din(a) = 1

dout(a) = 1

din(b) = 4

dout(b) = 2

din(c) = 2

dout(c) = 3

din(d) = 0

dout(d) = 1 16

TerminologiaExercício

1. Para cada grafo abaixo, identifique vértices isolados e

pendentes e determine se o grafo é simples, se é regular e se é

completo

2. Apresente o grafo complementar dos grafos G1 e G2 da

questão anterior

3. Determine se G1 é subgrafo de G2

17

1

1

2

3 4

5

6

2

3

4

6

5

4

G1

G2G3

TerminologiaSolução do exercício

Vert. isolados = ∅ Vert. isolados = ∅ Vert. isolados ={5}

Vert. pendentes = ∅ Vert. pendentes = ∅ Vert. pendentes = {4}

Simples Simples Não-simples

Regular Regular Não-regular

Não-completo Completo Não-completo

G1 G2

18

1

1

2

3 4

5

6

2

3

4

6

5

4

G1

G2G3

1

2

3

4

1

2

3

6

5

4

1.

2. 3.

Sim

Isomorfismo

Dois grafos G1 e G2 são isomorfos se existe uma

correspondência um a um entre os vértices (função f) de

G1 e G2, sendo que v1 e v2 são adjacentes em G2 se e

somente se f(v1) e f(v2) também adjacentes em G1

G1 G2

19

= ?

Isomorfismo

Dois grafos G1 e G2 são isomorfos se existe uma

correspondência um a um entre os vértices (função f) de

G1 e G2, sendo que v1 e v2 são adjacentes em G2 se e

somente se f(v1) e f(v2) também adjacentes em G1

G1 G2

f(a) = 2

f(b) = 1

f(c) = 3

f(d) = 4

f(e) = 6

f(f) = 5

20

=

Isomorfismo

Informalmente, G1 e G2 são isomorfos se podem ser

desenhados com um mesmo diagrama

G1 G2

f(1) = a

f(2) = b

f(3) = c

f(4) = d

21

Isomorfismo

Condições necessárias mas não suficientes para que G1

e G2 sejam isomorfos

Mesmo número de vértices

Mesmo número de arestas

Mesmo número de vértices com o mesmo grau

Não existe algoritmo eficiente para determinar se dois grafos são

isomorfos

Esse problema é NP-Completo (discutido posteriormente)

22

Isomorfismo

Exemplo de aplicação: Bioquímica

Componentes moleculares, como proteínas

são representadas como grafos

Cada vértice representa um átomo e arestas representam ligações entre

os átomos

Quantas vezes e onde os sub-grafos ocorrem em uma molécula

Predizer ou incrementar funcionalidade de novas ou conhecidas

moléculas

23

⊇ ?

IsomorfismoExercício

1. Determine se os pares de grafos a seguir são isomorfos e,

caso afirmativo, o correspondente de cada vértice no grafo

isomorfo

24

v1

v2 v3

v5v4

e

ab

cd

12

4

7

3

65

8

12 4

7

3 6

5

8

1

2 3

4

5

a

b c

d e

IsomorfismoExercício

25

12

4

7

3

65

8

12 4

7

3 6

5

8

1

2 3

4

5

a

b c

d e

São isomorfos:

f(v1) = e

f(v2) = a

f(v3) = b

f(v4) = d

f(v5) = c

Não são isomorfos.

São isomorfos:

f(1) = a

f(2) = d

f(3) = c

f(4) = e

f(5) = b

v1

v2 v3

v5v4

e

ab

cd

Sobre a complexidade

Duas classes importantes de problemas

computacionais:

NP (Não determinístico em tempo polinomial)

Não há algoritmo de ordem polinomial para resolver...

Algoritmos têm ordem exponencial de complexidade

O(2n)

O(n!)

P (Tempo polinomial)

Há algoritmos polinomiais (eficientes) para resolver:

Ordenação

Bubble sort O(n2)

Quick sort O(n log n)26

Sobre a complexidade

Problema? Ordem de crescimento:

27

n O(n2) O(2n)

4 16 16

5 25 32

10 100 1024

100 10000 1,3 x 1030

1000 1000000 1,0 x 10301

P NP

Sobre a complexidade

P vs. NP questão do milênio!

Se P = NP várias tarefas seriam triviais:

Reconhecimento de visão

Compreensão de linguagens

Otimização de processos, transporte, produção..

Fim da criptografia!!

Se P != NP pouco mudaria pois é o que é assumido até então

28

Revisão

Definições

Ordem e Grau

Incidência

Adjacência

Terminologia

Vértice isolado e pendente

Grafo nulo, trivial, regular, completo

Laço, aresta paralela

Complemento de grafo

Subgrafo

Isomorfismo29

Bibliografia

Goldbarg, M.; Goldbarg, E. Grafos: Conceitos, algoritmos e

aplicações. 1ª edição. Elsevier, 2012.

Vishveshwara, S.; Brinda, K. V.; Kannan, N. Protein Structure

Insights from Graph Theory. Journal of Theoretical and

Computational Chemistry, Vol. 1, No. 1, 2002. [link]

30