capÍtulo 7 - teoria dos grafos paulette · capÍtulo 7 - teoria dos grafos paulette 90 os grafos...

CAPÍTULO 7 - Teoria dos grafos Paulette

89

TEORIA DOS GRAFOS

1. INTRODUÇÃO

Muitos problemas foram apresentados ao longo da história e na tentativa de resolvê-los foram

geradas novas teorias na matemática. O mais famoso deles é conhecido como as pontes de Königsberg,

que levou o grande matemático Leonardo Euler a inventar um novo ramo da matemática na tentativa de

resolvê-lo, esse ramo denominou-se Teoria dos grafos.

Leonardo Euler foi o matemático mais prolífico de todos os tempos, nasceu em Basiléia, na Suíça,

em morreu em 1783. Escreveu mais de 800 artigos científicos e vários livros. A cidade de Königsberg é

cortada pelo rio Pregelarme e nele há duas ilhas, ligadas às margens e entre elas por 7 pontes. O

problema apresentado a Euler era: Seria possível encontrar um caminho que atravesse cada ponte

exatamente uma vez?

Euler provou em 1736, que tal percurso era impossível, provando não existir nenhuma solução

para esse problema.

Figura das pontes

Fig. 01

O problema das pontes se reduz a uma simples rede de pontos unidos por linhas, mostrados aqui por

sobreposição ao mapa. São 4 pontos A,B,C e D, e 7 arestas uma para cada ponte. Simplificando o

problema inicial podemos perguntar: Será possível encontrar um trajeto que atravesse a rede passando

por cada aresta exatamente uma vez?

2. GRAFOS

Definição 01:

Grafo é uma terna ordenada (V,A,g) sendo

i) V: um conjunto não vazio de vértices ou nós.

ii) A: um conjunto de arestas ou arcos.

iii) g: uma função que associa cada aresta a um par não ordenado x-y de vértices chamados extremos

da aresta..


90

Os grafos são normalmente representados por meio de diagramas no plano.

Exemplo 1:

Seja o grafo:

Fig. 02

Este grafo contem quatro vértices e cinco arestas.

i) V: vértices ou nós, A,B,C e D.

ii) A: um conjunto de arestas (arcos)

iii) g: uma função que associa cada aresta a um par não ordenado:

1( )g a A B ,2( )g a B C ,

3( )g a C D ,4( )g a A C e

5( )g a B D .

Exemplo 2:

O grafo que segue tem 5 vértices e 6 arestas. A função g que associa as arestas aos seus

vértices.

6a

1a 4a

3a 3 4

2a 5a

Fig. 03

5

A função g que associa as arestas aos seus vértices é dada por:

1( ) 1 2g a , 2( ) 1 3g a ,

3( ) 1 3g a , 4( ) 2 3g a ,

5( ) 3 5g a , 6( ) 2 2g a .

Definição 02: Arestas paralelas

São as arestas que possuem os mesmos extremos. No exemplo 02, 2a e 3a são ditas paralelas.

Definição 03: Vértices adjacentes

Dois vértices são adjacentes se forem extremos de uma mesma aresta. No exemplo 02, tem-se: 1

e 3 são adjacentes e o vértice 2 é adjacente a ele mesmo.

A

B

D

3a

C

1a

2a

4a5a

1

2


91

Definição 04: Vértice isolado

Não é adjacente a qualquer outro vértice. No exemplo 02, tem-se: o vértice 4 é um vértice

isolado.

Definição 05: Laço

Laço é uma aresta com extremos no mesmo vértice. No exemplo 02, tem-se: a aresta 6a sai do

vértice 2 e volta ao mesmo vértice 2.

Definição 06: Grafo simples

São grafos que não têm arestas paralelas e nem laços.

Definição 07: Grau de um vértice

O grau de um vértice de um grafo é o número de arestas incidente nesse vértice.

No exemplo 02, tem-se: (1) 3g , (2) 4g , (3) 4g e (4) 0g e (5) 1.g

Observação: A soma dos graus dos vértices de um grafo G é igual a duas vezes o número de arestas.

No exemplo 02, tem-se, 6 arestas e g(G)=12

Definição 08: Grau par ou ímpar

Um vértice é par ou ímpar dependendo de seu grau ser par ou ímpar.

Um vértice de grau zero é dito vértice isolado.

Definição 09: Grafo completo

Um Grafo se diz completo se todos os seus vértices distintos são adjacentes.

O exemplo 1 é um grafo completo.

Definição 10: Subgrafo

Subgrafo de um grafo G é um subconjunto de arestas e vértices do grafo original. Podemos dizer

que o subgrafo é um grafo obtido apagando-se parte o gráfico original.

Definição 11: Caminho

Caminho de um vértice 1A a um vértice nA é uma sequência alternada de vértices e arestas:

1 1 2 2 3 3 1 1, , , , , ,...., , , ,n n nA a A a A a A a A sendo que cada aresta ia contém os vértices 1i iA A .

No exemplo 1, tem-se o caminho do vértice A a D: 1 2 3, , , , , , .A a B a C a D

Definição 12: Comprimento de um caminho

Comprimento de um caminho é o número de arestas que ele contém

O caminho indicado no exemplo 1, o caminho do vértice A a D: 1 2 3, , , , , ,A a B a C a D é de

comprimento 3.

Definição 13: Grafo conexo

Um grafo se diz conexo se existir um caminho entre quaisquer dois vértices.

O grafo do exemplo 1 é conexo, porém o exemplo 2 não é conexo.


92

Definição 14:Ciclo

Ciclo em um grafo é o caminho de algum vértice 0 0 até n n de novo, de forma que nenhum

vértice ocorra mais de uma vez no caminho.

Definição 15: Árvores

Uma árvore é um grafo acíclico e conexo com um nó designado como raiz da árvore. Os grafos

que seguem são duas árvores.

Fig. 04

Um grafo acíclico e conexo sem a designação de um vértice como raiz é chamado de árvore não

enraizada. Um único vértice é uma árvore e esse vértice é a raiz.

Dado que a árvore é um grafo conexo, existe um caminho entre a raiz e todos os vértices da

árvore e como a árvore é acíclica, esse caminho é único.

Definição 16:Profundidade de um vértice

Profundidade de um vértice de uma árvore é o comprimento do caminho da raiz até o vértice. A

raiz tem profundidade zero.

Definição 17: Altura da árvore

Altura da árvore é a maior profundidade de todos seus vértices. É o comprimento do maior

caminho entre a raiz e um vértice.

Definição 18: Folha

Um vértice sem filhos é denominado de folha.

Definição 19: Vértices internos

Os vértices que não são folhas são denominados vértices internos.

Definição 20: Floresta

Floresta é um grafo acíclico, portanto uma floresta é uma coleção de árvores disjuntas.

Definição 21: Árvore binária

Uma árvore se diz binária se cada nó tem no máximo dois filhos, sendo um filho denominado

filho à direita e filho à esquerda.

r

r


93

Definição 22: Árvore binária completa

Uma árvore binária se diz completa se todos os nós internos têm dois filhos e todas as folhas têm

a mesma profundidade.

A Fig.05a é uma árvore binária de altura 4 e a Fig.05b é uma árvore binária completa de altura

3.

Fig. 05 a Fig. 05 b

Exemplo 3:

Construir um grafo que tenha os vértices {1,2,3,4,5} e as arestas 1 2 3 4 5 6{ , , , , , }a a a a a a e a função

1( ) 1 2g a , 2( ) 1 3g a ,

3( ) 3 4g a , 4( ) 3 4g a ,

5( ) 4 5g a , 6( ) 5 5g a .

a)Construir o grafo

Fig.06

Com relação ao grafo obtido, responda as questões.

b) dois vértices que não sejam adjacentes. f) um vértice que seja adjacente a ele mesmo

Resp: 1 e 4 Resp: 5

c) um laço. g) duas arestas paralelas.

Resp: 5 Resp: 3 4a e a

d) o grau do vértice 3. h) este gráfico é conexo

Resp: 3 Resp: Sim

e)este grafo é completo?

Resp: não, pois 2 e 3 não são adjacentes.

r r

1

2

3

4

5

1a

3a4a

2a

5a

6a

r r


94

Exercícios de aplicação 20:

1) Responder as questões observando o grafo.

Fig.07

a)Este grafo é simples?

b)Este grafo é completo?

c)Este grafo é conexo?

d)Existem dois caminhos entre os vértices 7 e 3?

e)Este grafo possui ciclo?

f)O grafo possui alguma aresta cuja remoção o tornaria

uma árvore.

2) Esboce um diagrama para cada um dos seguintes grafos.

a)Um grafo simples com 3 vértices, cada qual com 2 graus.

b)Uma árvore com cinco vértices de altura 1.

3) Responder as questões observando a

árvore.

Fig.08

a)Qual a altura?

b)Qual é o filho à esquerda do nó B?

c)Qual a profundidade do nó E?

A

B

C

D1a

2a

3a

4a

E

5

6a

2

3

6

7 1a

2a

3a4a

5a 7a

4

1


95

4) Responder as questões observando a

árvore.

Fig.09

a)A árvore é binária?

b)A árvore é binária completa?

c)Qual o pai do vértice f ?

d)Qual é o filho à esquerda do vértice h?

e)Qual a altura de g?

f)Qual a altura da árvore?

5)No grafo a seguir:

a) Descreva formalmente o grafo.

b) Dê o grau de seus vértices.

c) Qual a soma dos graus dos vértices?

Definição 23: Grafos direcionados

Muitas vezes há interesse que as arestas de um grafo comecem em um vértice e terminem em

outro, neste caso, podemos usar o grafo direcionado.

Grafo direcionado é uma terna ordenada (V, A, g) sendo

i) V: um conjunto não vazio de vértices ou nós.

ii) A: um conjunto de arestas ou arcos.

iii) g: uma função que associa cada aresta a um par ordenado (x,y) de vértices chamados extremos da

aresta, sendo x ponto inicial e y ponto final.

A

B

C

D

1a 2a

3a

4a

5a7a8a

6a

E

b

c

d

e

f g hi

a


96

Exemplo 4:

O grafo que segue é um grafo direcionado e apresenta três caminhos do vértice A para o vértice C.

Fig.10


1)Responder as questões observando o grafo direcionado.

Fig.11

a) Quais são os nós acessíveis a partir do vértice A?

b) Qual o caminho mais curto de A para C?

c) Qual o caminho de comprimento 6 de A a para D?

A

B C

D

1a2a

3a4a

5a7a

9a

10a

8a

F6a E

11a

D

3a

A

B C

1a

2a

4a5a


97

2) Transforme o grafo em grafo direcionado de tal forma que partindo de um vértice passe por todos

os vértices, sem usar duas vezes a mesma aresta. Se isto for feito teremos um grafo atravessável.

Fig.12

Definição 24: Grafos isomorfos

Os grafos G= (V,A,g) e G’= (V’,A’,g’) são isomorfos se, existir uma aplicação bijetora

: 'f V V tal que se ea b são duas arestas de G, então ( )e ( )f a f b são arestas de G’.

Exemplo 5: Os grafos que seguem são isomorfos (Mostre você)

Fig.13

Exemplo 6:

Os grafos que seguem não são isomorfos

Fig.14

Os grafos possuem 6 vértices e 7 arestas, o vértice A´ de grau 2, é adjacente aos vértices

A

não é isomorfo a

A

B

C

D

E

F

´B

´C

A

B

2aC

D

1a 3a4a5a

6a7a

8a

é isomorfo a

E

´D

´E

´F

é isomorfo a


98

B´ e F´ de grau 3, porém, o vértice A correspondente o vértice A´ é adjacente aos vértices B de grau 3 e

F de grau 2, portanto, os grafos não são isomorfos.

Condições para verificar se dois grafos são isomorfos:

Existem certas condições sob as quais se torna mais fácil ver se dois grafos não são isomorfos.

1.Um grafo tem mais vértices que o outro.

2.Um grafo tem mais arestas que outro.

3.Um grafo tem mais arestas paralelas e outro não.

4.Um grafo tem um laço e o outro não.

5.Um grafo tem um vértice de grau K e o outro não.

6.Um grafo é conexo e o outro não.

7.Um grafo tem um ciclo e o outro não.

Exemplo 7:

Os grafos que seguem são ou não isomorfos.

Fig.15

Verificando as condições para ver se dois grafos são ou não isomorfos.

1. Um grafo tem mais vértices que o outro. (não).

2. Um grafo tem mais arestas que outro. (não).

3. Um grafo tem mais arestas paralelas e outro não. (sim)

4. Um grafo tem um laço e o outro não. (não).

5. Um grafo tem um vértice de grau K e o outro não. ( O primeiro grafo tem o vértice A com

grau 4 e o vértice A´ correspondente tem grau 3)

6. Um grafo é conexo e o outro não. (não).

7. Um grafo tem um ciclo e o outro não. (não).

Portanto, os grafos não são isomorfos, pois não atendem o item 3 e o item 5.

A

B ´DD

A

´B

´CC


99


1) Qual dos grafos que seguem não é isomorfo aos outros? Por que?

Fig.16

2) Qual dos grafos que seguem não é isomorfo aos outros? Por que?

Fig.17

3) Verifique se os grafos são ou não isomorfos. Se forem apresente a função que estabelece o

isomorfismo entre eles, caso contrário explique por quê.

Fig.18

Fig.19

a b c d

)a

)b


100

Fig.20

Fig.21

Definição 25: Grafo Atravessável

Um grafo se diz atravessável se pode ser desenhado sem quebras nas curvas e sem repetição de

arestas, isto é, se existir um caminho que inclua todos os vértices e use cada aresta uma única vez.

Exemplo 8:

Foi pedido no exercício de aplicação 02 para transformar o grafo que segue em grafo

direcionado de tal forma que partindo de um vértice passe por todos os vértices, sem usar duas vezes a

mesma aresta. Se isto for feito teremos um grafo atravessável.

Fig.22a Fig.22b

Nestas condições o caminho é uma trilha, pois, nenhuma aresta pode ser usada duas vezes, e será

uma trilha atravessável, assim a trilha é:

1 7 6 8 4 3 5 2, , , , , , , , , , , , , , , ,B a A a E a D a A a C a D a B a C .

A

B

2aC

D

1a 3a4a5a

6a7a

8aA

B

2aC

D

1a 3a4a5a

6a7a

8a

E

)c

)d

E


101

Se a trilha passa por um vértice P de grau 2, neste caso a trilha entra e sai por esse vértice. Se P é

um vértice de grau 3, a trilha será atravessável se começar em P e terminar em outro vértice também de

grau 3. Se uma trilha possuir dois vértices P e Q de grau ímpar, a trilha deve começar por P e terminar

em Q. Se o caminho tiver 3 ou mais vértices ímpares, o caminho não é atravessável.

O caminho pelas pontes de Könisberg apresentam 4 vértices de graus ímpares, portanto não é

atravessável.

Definição 26: Grafo Euleriano e Hamiltonianos

Um grafo se diz euleriano se existir uma trilha atravessável fechada.(Ver Fig.22b)

Um grafo conexo finito é euleriano se, e somente se cada vértice tem grau par.

O caminho euleriano percorre cada aresta exatamente uma vez.

Um grafo se diz ciclo hamiltoniano (William Rowan Hamilton 1865-1905) se for fechado e

visita todos os vértices exatamente uma vez. Um caminho nessas condições deve ser um ciclo.

Um ciclo hamiltoniano percorre cada vértice exatamente uma vez

Exemplo 9:

Verifique se os grafos a seguir são ou não Ciclo hamiltoniano e Grafo euleriano.

.23Fig a (Ciclo hamiltoniano) .23Fig b(Grafo euleriano)

Definição 27: Grafo Bipartido Completo

Sabemos que os grafos que seguem são grafos simples completos com 1, 2, 3, 4 e 5 vértices.

Fig. 24

O grafo simples que segue não é um grafo completo, porque nem todo vértice é adjacente a todos

os demais vértices, mas, os vértices podem ser divididos em dois grupos disjuntos {A,B} e {C,D,E} de

tal forma que dentro do conjunto quaisquer dois vértices são adjacentes.

1k

2k

3k

4k 5

k


102

Fig. 25

Os grafos com essa característica são denominados grafos bipartidos completos e denotamos

por 2 ,3

k .

Exemplo 10:

Qual é o diagrama para o grafo 3,3

k ?

3,3

k é um grafo conexo simples com três conjuntos disjuntos, portanto, segue seu diagrama.

Fig. 26

Definição 28: Grafo planar

Um grafo se diz planar se pode ser desenhado em um plano de forma que suas arestas se

interceptem apenas nos vértices. Muitas vezes o grafo é planar e, é desenhado com cruzamentos de

arestas, no entanto, podemos determinar um grafo isomorfo sem cruzamentos.

Exemplo 11:

O grafo visto na Fig. 27a possui cruzamentos, mas é isomorfo ao grafo da Fig. 27b, assim são

planares.

A

B ´DD

A

´B

´CC

.27Fig a .27Fig b

A B C

D E F

A B

C D E


103

Exemplo 12:

O grafo visto na Fig. 28a possui cruzamento, mas é isomorfo ao grafo da Fig. 28b, assim são

planares.

Fig. 28a Fig. 28b

Exemplo 13:

O grafo 5

k visto na Fig. 29 é um grafo conexo, simples. Verifique se é planar.

Construindo 5

k por etapas e incluindo se possível novas arestas que não interceptem as já

concluídas. Na construção da Fig.c ,nota-se que não existe maneira de construir a última aresta 2-4 no

mesmo plano sem interceptar as outras arestas, portanto o grafo não é planar.

No exemplo 13 tentamos resolvê-lo por tentativa e erro, vejamos agora a fórmula de Euler para

resolução desses problemas.

Seja G um grafo conexo, simples e planar com:

n: vértices,

a: arestas e

r: regiões.

a b c

1 11

2 2

2

3 334 4 4

55

5

.30Fig


104

Definição 29: Região

Um grafo conexo simples e planar com seu diagrama planar sem interseções de arestas, divide o

plano em regiões. Do exemplo 13, a Fig.30a divide o plano em 2 regiões, Fig.30b divide o plano 4

regiões e Fig.30c divide o plano 6 regiões.

Formula de Euler

Se G é um grafo conexo, simples, planar e com r regiões, então

i) 2n a r .

ii) Se 3, então 3 6.n a n

iii) Se 3n e não existem ciclos de comprimento 3, então 2 4.a n

Exemplo 14:

Verifique se o grafo 5

k é planar.

Fig.31

Do diagrama podemos concluir que 5

k é conexo, simples com n =5 vértices e a =10 arestas e

pelo item ii) se 3, então 3 6n a n segue 10 3.5 6 10 9,a portanto 5

k não é

planar como já tínhamos visto no exemplo 13.


1)Verificar se o grafo 2 ,3

k é planar (ver Fig. 25 )

2)Verificar se o grafo 3,3

k é planar(ver Fig. 26 ).


105

3)Verificar se o grafo é planar e dar o número de regiões que divide o plano.

4) Se todos os vértices de um grafo simples conexo e planar tem grau 4 e o número de arestas é 12,

quantas regiões divide o plano?

3. COLORAÇÃO

Alguns problemas são fáceis de enunciar, porem difíceis de resolver. O teorema das quatro cores

é um bom exemplo. O estudante de pós-graduação Francis Guthrie da Universidade College, em

Londres (1852), ao colorir o mapa dos municípios da Inglaterra descobriu que conseguia fazê-lo usando

para isso 4 cores (ou menos) de modo que as regiões que possuem fronteiras comuns jamais tenham a

mesma cor. Ele se perguntou se esse fato seria uma particularidade para o mapa da Inglaterra.

Será possível colorir qualquer mapa no plano com quatro cores de modo que as regiões que

possuem fronteiras comuns jamais tenham a mesma cor?

Não se conseguiu até agora nenhuma prova conceitual para esse teorema. Famosos matemáticos

tentaram resolver esse problema sem sucesso, tais como: Augustus De Morgan, William Rowan

Hamilton, Arthur Cayley e Philip Franklin. Em 1976 dois matemáticos americanos Kenneth Appel e

Wolfang Haken usando computadores e testes de redutibilidade com 487 regras diferentes encontraram

cerca de 1405 configurações de mapas distintos e todas elas usaram 4 cores.

3.1 Grafo dual de um mapa

Seja M um mapa. Se colocarmos um vértice em cada região do mapa, e uma aresta entre dois

vértices que representem países adjacentes, então o problema de coloração do mapa, torna-se problema

de coloração de vértices de um grafo dual, de forma que não haja dois vértices adjacentes que tenham a

mesma cor.

3.2 Número cromático

É o menor número de cores necessárias para se obter uma coloração.


106

Exemplo 15:

Desenhe o grafo dual do mapa da figura que segue.

3.3 Algoritmo de welch-powell

Seja um grafo G. Uma coloração de vértices de G é uma atribuição de cores aos vértices de G de

tal forma que vértices adjacentes têm cores distintas. Utilizaremos a seguir o Algoritmo de Welch-

Powell para a coloração minimal de um gráfico G.

Passo 1: Ordenar os vértices de G em ordem decrescente de grau.

Passo 2: Atribuir a primeira cor, 1

C , ao primeiro vértice e, então sequencialmente atribua a mesma cor

1C para vértices não adjacente ao primeiro vértice.

Passo 3: Repetir o passo 2 com a segunda cor 2

C e os vértices subsequentes não coloridos.

Passo 4: Repetir o passo 3 com a terceira cor 3

C , depois com a cor 4

C e assim por diante.

Exemplo 16:

Utilize o Algoritmo de Welch-Powell para a coloração do grafo 5

k .

O grafo 5

k tem todos os vértices de mesmo grau e neste caso usamos a ordem natural do grafo.

Passo 1: Ordenar os vértices em ordem decrescente de

grau.(A,B,C,D,E)


C , vértice A


C , vértice B


C , vértice C


C , vértice D


C , vértice E

Fig.33

Sabemos que todo grafo planar é 4-colorizável, porém, 5

k não é planar e é 5-colorizável. De

modo geral n

k é n-colorizável.

A

B

CD

E

.32Fig


107


1) Encontre o número cromático para cada grafo.

2) Encontre o número cromático para o grafo.

4. MATRIZ DE ADJACÊNCIAS

Seja G um grafo com m vértices e sejam ordenados como1 2 3, , ,..., .

mn n n n A matriz de adjacências

ijA a do grafo G é a matriz m m definida por

1 se é adjacente

0 caso contrario

i j

ij

n na

Exemplo 16:

Dar a matriz de adjacência para o grafo.

A

11 12 13 14

21 22 23 24

31 32 33 34

41 42 43 44

0 1 0 1

1 0 1 1

0 1 0 0

1 1 0 0

a a a a

a a a aA

a a a a

a a a a

2

34

1


108

Exemplo 17:

Dar a matriz de adjacência para o grafo.

Solução

1 1 0 1

1 0 2 1

0 2 0 0

1 1 0 0

A matriz de adjacência dos exemplos são todas simétricas, isso não ocorre se a matriz de adjacência

for de grafos não direcionados.

Exemplo 18:

Dar a matriz de adjacência para o grafo direcionado.

Solução:

1 1 0 0

0 0 1 0

0 1 0 0

1 1 0 0

A matriz de adjacência desse exemplo não é simétrica, isso ocorreu por ser um grafo direcionado.


1) Dar a matriz de adjacência para o grafo.

2

34

1

3

2

4

1

2

34

1


109



4)Encontre o grafo direcionado para a matriz.

0 1 1 1

0 1 0 0

0 1 0 0

0 0 1 0

2

4

15

6

3

2

3

41

capÍtulo 7 - teoria dos grafos paulette · capÍtulo 7 - teoria dos grafos paulette 90 os grafos...

Documents