Apostila Teoria dos Grafos

Teoria dos Grafos

Valeriano A. de OliveiraSocorro Rangel

Departamento de Matemtica [email protected], [email protected]

AULA 1Introduo, Conceitos Iniciais, Isomorfismo

Preparado a partir do texto:

Rangel, Socorro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.

Introduo

Introduo Aplicaes Conceitos Iniciais Isomorfismo

O que um Grafo?Introduo Aplicaes Conceitos Iniciais Isomorfismo

Teoria dos Grafos (Antunes&Rangel) 3

Um grafo G constitudo de um conjunto V no-vazio de objetos,chamados vrtices (ou ns), e um conjunto A de pares no ordenados deelementos de V , chamados de arestas. Denotamos o grafo por G(V,A)ou simplesmente G.

Exemplo 1.

a) V = {v1, v2, v3, v4, v5} eA = {(v1, v2), (v1, v3), (v2, v4), (v3, v4), (v4, v5), (v1, v2), (v2, v2)}.

b) V = {1, 2, 3, 4, 5} e A = {(1, 2), (2, 3), (1, 4), (1, 3)}.

c) V = {a, b, c} e A = { }.



Os grafos podem ser representados atravs de um diagrama onde osvrtices so representados por pontos e cada aresta representada poruma linha ligando os pares de vrtices que a definem. A representaogrfica dos grafos dados no Exemplo 1 so dadas na figura a seguir.

v1

v2

v3 v4

v5

1

2

3

4

5

a

b c

Em algumas aplicaes, as arestas so definidas como pares ordenadosde vrtices. Neste caso dizemos que o grafo orientado ou direcionado eo chamamos de Digrafo.

O que um Digrafo?Introduo Aplicaes Conceitos Iniciais Isomorfismo


Um grafo orientado (ou direcionado) G(V,A) constitudo pr umconjunto V no-vazio de objetos, chamados vrtices (ou ns), e umconjunto A de pares ordenados de elementos de V , chamados de arestasou arcos.

Os digrafos podem ser desenhados atravs de um diagrama onde osvrtices so representados por pontos e cada aresta (vi, vj) representada por uma linha ligando vi a vj com uma seta apontandopara vj.

casaHighlight



Exemplo 2. V = {v1, v2, v3, v4, v5} eA = {(v1, v2), (v1, v3), (v2, v4), (v3, v4), (v4, v5), (v1, v2), (v2, v2)}.

v1

v2

v3

v4

v5



Um mesmo grafo, ou um mesmo digrafo, pode ter diferentesrepresentaes grficas. Ver figura abaixo:

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

Figura 1: Um mesmo grafo com diferentes representaes grficas.



O que que caracteriza um grafo? O conjunto de vrtices e de arestas,ou seja, um conjunto de objetos (vrtices) e a relao entre estes objetos(arestas). Durante o curso, a distino entre grafos e digrafos ser feitade acordo com o tpico estudado.

Assim, podemos dizer que a Teoria de Grafos um ramo damatemtica que estuda as relaes entre os objetos de umdeterminado conjunto.

Objetivos do curso:

n Desenvolver a Teoria dos Grafos

n Modelar problemas de forma a serem resolvidos utilizando conceitose resultados de Teoria dos Grafos.

Aplicaes


O problema das pontes de KnigsbergIntroduo Aplicaes Conceitos Iniciais Isomorfismo


Na cidade de Konigsberg (Hoje Kaliningrado - Rssia) sete pontescruzam o rio Pregel estabelecendo ligaes entre uma ilha e o continenteconforme a figura abaixo:

Ser que possvel fazer um passeio pela cidade, comeando eterminando no mesmo lugar e passando pr cada uma das pontes apenasuma vez?

Problema do Carteiro ChinsIntroduo Aplicaes Conceitos Iniciais Isomorfismo


Determinar a rota de menor custo que saia da agncia central doscorreios, passe pr todas as ruas de um determinado bairro, e volte aorigem.

O Problema de ligaes de eletricidade, gs e gua



Considerem que existam 3 casas e que cada uma delas precisa ser ligadaao sistema de eletricidade, gs e gua. Por questes de segurana,deseja-se saber se possvel fazer as ligaes sem que haja cruzamentodas tubulaes. Represente este problema atravs de um grafo.

O problema do caixeiro viajanteIntroduo Aplicaes Conceitos Iniciais Isomorfismo


Um viajante necessita visitar um certo nmero de cidades. possveldeterminar um roteiro de viagem tal que cada cidade seja visitada apenasuma vez?

Considere, por exemplo, um trecho do mapa rodovirio que inclui acidade de So Jos do Rio Preto (SJRP). Suponha que o viajante tenhaque sair de SJRP e visitar as cidades de Marilia, Araatuba, Bauru e SoCarlos. Represente este problema atravs de um grafo.

possvel encontrar uma rota que passe pr todas as cidades apenasuma vez e retorne a cidade SJRP? Caso existam mais de uma rota, qual a rota que minimiza o trecho viajado?

ExercciosIntroduo Aplicaes Conceitos Iniciais Isomorfismo


1. Considere o problema de ligaes de eletricidade, gs e gua.Desenhe grafos representando as seguintes situaes:(a) 2 casas e 3 servios;

(b) 4 casas e 4 servios (gua, eletricidade, gs e telefone).

2. Descreva 10 situaes (jogos, atividades, problemas, etc.) quepodem ser representadas atravs de grafos ou digrafos. Explique oque os vrtices e as arestas esto representando. Sugesto deleitura: Capitulo 1, seo 1.3 de [2] e Captulo3 e 5 de [3].

3. O Problema da decantao - Considere trs vasos, A, B, e C comcapacidades de 8, 5 e 3 litros respectivamente. O vaso A est cheioe os vasos B e C esto vazios. Divida o lquido que est no vaso Aem duas quantidades iguais. Represente o problema usando umgrafo.

BibliografiaIntroduo Aplicaes Conceitos Iniciais Isomorfismo


1. N. Deo, Graph Theory with applications to engineering andcomputer science, 1974.

2. R.K. Ahuja, T. Magnanti e J.B. Orlin, Network Flows, PrenticeHall, 1993.

3. R.J.Wilson, Introduction to graph theory, 3rd ed. The pitman PressLtda, Bath, 1985.

Conceitos Iniciais




Definio 3. Seja G(V,A) um grafo. Dada uma arestaa = (vi, vj) A dizemos que:

a) vi e vj so os extremos da aresta a.

b) A aresta a dita ser incidente nos vrtices vi e vj.

c) vi e vj so chamados de vrtices adjacentes.

d) Se vi = vj a aresta a chamada de loop ou lao.

e) Se existir uma aresta f = (v , v ) tal que v = v e v = v , as arestas



Exerccio Analise o grafo da figura abaixo e exiba exemplos dos termoscitados na Definio 3.

v1

v2

v3 v4

v5

Figura 2:



Definio 4. Um grafo simples se no possui loops e/ou arestasparalelas.

Definio 5. Duas arestas so ditas adjacentes se elas incidem nomesmo vrtice.

Definio 6. O grau de um vrtice v, d(v), em um grafo sem loops determinado pelo nmero de arestas incidentes em v. Caso haja loops,estas arestas contribuem com grau 2.

Exemplo 7. Determine os graus dos vrtices do grafo dado na figuraacima.

casaHighlight



Definio 8. Dizemos que:

a) Um vrtice v isolado se d(v) = 0.

b) Um vrtice v pendente se d(v) = 1.

c) Um grafo G(V,A) dito nulo se o conjunto de arestas vazio.

d) Um grafo G(V,A) dito regular se todos os seus vrtices tem omesmo grau.

e) Um grafo G(V,A) dito completo se existe uma aresta entre cadapar vrtices. representado por Kn, onde n o nmero de vrticesdo grafo.

f) Um grafo G(V,A) dito valorado (ou rede) se so atribudos valorespara os vrtices e/ou arestas.

casaHighlight

casaHighlight



Figura 3: Grafos regular e nulo.

Figura 4: Grafos completos K4 e K5.



Proposio 9. Dado um grafo G com n vrtices, v1, v2, . . . , vn e marestas, temos que:

n

i=1

d(vi) = 2m. (1)

Porque este resultado vlido? Observe que cada aresta contribui com 2graus para cada vrtice. Assim a soma dos graus de todos os vrtices igual a duas vezes o nmero de arestas.

Teorema 10. O nmero de vrtices de grau mpar em um grafo sempre par.



Demonstrao. Vamos dividir a soma em (1) em duas parcelas. Osvrtices com grau par e os vrtices com grau mpar:

n

i=1

d(vi) =

grau par

d(vi) +

grau mpar

d(vi). (2)

O lado esquerdo da equao (2) par (pela Proposio 9). A primeiraparcela do lado direito tambm par, pois a soma de nmeros pares.Para que a igualdade seja vlida, a segunda parcela em (2) tambm deveser par:

grau mpar

d(vi) par. (3)

Como cada parcela d(vi) em (3) mpar temos que ter um nmero parde elementos para que a soma seja um nmero par (lembre-se que umnmero mpar da forma 2k + 1).



Exerccios:

1. Desenhe todos os grafos simples com 1,2, 3 e 4 vrtices.

2. Represente os seguintes compostos orgnicos atravs de grafos: (a)CH4; (b) C2H2; (c) N2O3.

3. Convena a voc mesmo que o grau mximo de um vrtice em umgrafo simples com n vrtices n 1.

Isomorfismo




Ns j vimos que possvel representar um mesmo grafo de vriasmaneiras. Como determinar se dois grafos so equivalentes, ou seja sepossuem as mesmas propriedades? Isto como determinar se dois grafosso isomorfos? A palavra isomorfismo vem do grego iso (mesmo) emorfo (mesma forma).

Definio 11. Dizemos que dois grafos G e H so isomorfos se existiruma correspondncia biunvoca entre os vrtices de G e os vrtices de Hque preserve a relao de adjacncia entre vrtices e arestas. Em outraspalavras, possvel obter o grafo H a partir de uma nova rotulao dosvrtices de G.

casaHighlight



Exemplo 12. Considere os grafos da Figura 5. Construir acorrespondncia biunvoca.

a

b

c

1 2

3 4

5

Figura 5:



Aplicaes: O estudo de isomorfismo pode ser aplicado na descobertade novos compostos orgnicos. Os qumicos mantm uma tabela decompostos orgnicos. Cada vez que um novo composto descoberto necessrio determinar se ele isomorfo a algum composto j existente.



Aplicaes: O estudo de isomorfismo pode ser aplicado na descobertade novos compostos orgnicos. Os qumicos mantm uma tabela decompostos orgnicos. Cada vez que um novo composto descoberto necessrio determinar se ele isomorfo a algum composto j existente.

Determinar se dois grafos so isomorfos no uma tarefa muito simples.De fato a determinao de isomorfismos uma rea de intensa pesquisaem teoria de grafos. Condies necessrias para que dois grafos sejamisomorfos so facilmente determinadas atravs da Definio 11:



Condies necessrias para Isomorfismos entre os dois grafos Ge H:

1. G e H devem possuir o mesmo nmero de vrtices;

2. G e H devem possuir o mesmo nmero de arestas;

3. G e H devem possuir o mesmo nmero de vrtices com umdeterminado grau.

As condies 1,2 e 3 acima so suficientes?

casaHighlight



Vamos verificar este fato atravs do seguinte exemplo:

G: H:

x

u

v

y

w

Observe que G e H:

a) possuem mesmo nmero de vrtices;

b) possuem mesmo nmeros de arestas;

c) possuem: 3 vrtices com grau 1; 2 vrtices com grau com grau 2; 1vrtice com grau 3. Porm...



Porm estes dois grafos no so isomorfos! No possvel fazer umacorrespondncia biunvoca entre os vrtices que preserve a relao deadjacncia entre vrtices e arestas. Observe que necessrio associar ovrtice x do grafo G ao vrtice y do grafo H, pois no existe nenhumoutro vrtice com grau 3 em H. Mas o vrtice y adjacente a apenasum vrtice de grau 1, enquanto que x em G adjacente a dois vrticesde grau 1. Portanto, no possvel fazer uma correspondncia biunvocaentre os vrtices de G e H que preserve a relao de adjacncia entrevrtices e arestas.

No captulo 11, seo 11.7 de [N. Deo, Graph Theory with applicationsto engineering and computer science, 1974] feita uma discusso arespeito de algoritmos para se determinar isomorfismos entre grafos.



Exerccios:

1. Desenhe todos os grafos simples, no isomorfos com 1,2, 3 e 4vrtices.

2. Verifique se os grafos abaixo so isomorfos:

(a)G: H:

(b) G: H:

Teoria dos Grafos

Valeriano A. de Oliveira

Socorro Rangel

Departamento de Matemtica Aplicada

[email protected], [email protected]

AULA 2Subgrafos, Operaes com Grafos

Preparado a partir do texto:Rangel, Socorro. Teoria do Grafos, Notas de aula, IBILCE, Unesp, 2002-2013.

Subgrafos

Subgrafos Operaes com grafos



Definio 1. Um grafo H(V , A) um subgrafo de um grafo G(V,A)se todos os vrtices e todas as arestas de H pertencem a G(V V, A A), e cada aresta de H possui as mesmas extremidadesque em G. Denotamos um subgrafo atravs da mesma notao usadapara conjuntos, isto H G.



Exemplo 2. Dado o grafo

1

23

4 5

a b

c d

e f

67

8 9 10

11

G:

os seguintes grafos so subgrafos de G:

1

3

4 5

a b

d

e f

6

9 10

11

G1:

2 5

a b

c d

e

8

G2:



As seguintes observaes podem ser feitas:

1. Todo grafo um subgrafo de si prprio.

2. Um subgrafo de um subgrafo de um grafo G tambm um

subgrafo de G.

3. Um vrtice de um grafo G um subgrafo de G.

4. Uma aresta de um grafo G um subgrafo de G.

Definio 3. Dois subgrafos de um grafo G, G1 e G2, soaresta-disjuntos se eles no possuem arestas em comum. Se G1 e G2 nopossurem vrtices em comum, os dois subgrafos so chamados devrtice-disjuntos.



Exerccio: Considere os grafos

a

c d

e

G3: a

d

e

G4: b

c

G5:

Determine quais so:

- Aresta-disjuntos:

- Vrtices-disjuntos:

Operaes com grafos




Definio 4. A unio de dois grafos G1(V1, A1) e G2(V2, A2) umgrafo G3(V3, A3) onde:

G3 = G1 G2, V3 = V1 V2 e A3 = A1 A2.

Definio 5. A interseco de dois grafos G1(V1, A1) e G2(V2, A2) um grafo G3(V3, A3) onde:

G3 = G1 G2, V3 = V1 V2 e A3 = A1 A2.

Observao 6. Se V3 = , dizemos que a interseco entre G1 eG2, G1 G2, vazia.Pelas definies dadas fcil verificar que as operaes de unio einterseco de grafos so comutativas, isto :

G1 G2 = G2 G1,

G1 G2 = G2 G1.



Exemplo 7. Determine a unio e a interseco dos grafos dados abaixo:

v1

v2 v3

v4 v5

G1:

v1

v2

v3 v5

v6

G2:



Definio 8. Um grafo G dito decomposto em dois sub-grafos G1 eG2 se:

G1 G2 = G e G1 G2 = grafo nulo.

Ou seja, cada aresta de G pertence a G1 ou a G2. Alguns vrtices noentanto podem pertencer aos dois.

Exemplo 9. O grafo G1 do exemplo anterior decomposto nossubgrafos G1a e G1b abaixo:

G1a:

G1b:



Definio 10. Se aj uma aresta de um dado grafo G, ento G aj um sub-grafo de G obtido pela remoo da aresta aj do grafo G.

Se vi um vrtice de G, ento G vi um sub-grafo de G obtido pelaremoo do vrtice vi do grafo G.

A remoo de um vrtice implica na remoo das arestas a eleincidentes.

De maneira similar possvel incluir vrtices e arestas em um grafo.



Definio 11. A soma de dois grafos G1(V1, A1) e G2(V2, A2) umgrafo G3(V3, A3) onde:

G3 = G1+G2, V3 = V1V2 e A3 = A1A2{(vi, vj) : vi V1, vj V2}.

Definio 12. A soma direta de dois grafos G1(V1, A1) e G2(V2, A2) um grafo G3(V3, A3) onde:

G3 = G1 G2, V3 = V1 V2 e A3 = [A1 A2] \ [A1 A2]



Exemplo 13. A seguir esto ilustradas algumas das operaes definidas.

G:

1

2

3

4

5

6

G - (2,6):

1

2

3

4

5

6

G - 1:

2

3

4

5

6

G + (1,4):

1

2

3

4

5

6



Definio 14. A fuso de um par de vrtices a e b em um Grafo G feita substituindo os dois vrtices por um nico vrtice ab , de tal formaque toda aresta que era incidente no vrtice a e/ou no vrtice b passa aser incidente no novo vrtice ab.

Observao 15. A fuso de vrtices em um grafo no altera seunmero de arestas, apenas diminui o nmero de vrtices.

Definio 16. A contrao de dois vrtices a e b feita atravs dafuso dos vrtices a e b e a remoo dos loops e arestas paralelas queso formadas no processo.

Definio 17. A contrao de uma aresta (a, b) feita removendo-se aaresta (a, b) e fazendo a contrao dos vrtices a e b. denotado porG \ (a, b).



Exemplo 18. Na figura abaixo temos, esquerda, um grafo G; nocentro, o grafo obtido aps a fuso dos vrtices 1 e 2; e direita o grafoobtido aps a contrao da aresta (1, 2).

G: 1 2

3 4

56

12

3 4

56

12

3 4

56



Exerccios: Considere o grafo:

1

2

3

4 5

ab

c

de

f

6

1. Remova o vrtice 5 deste grafo e acrescente a aresta (2, 7).

2. Decomponha este grafo em trs sub-grafos.

3. Contraia a aresta (2, 3).

Teoria dos Grafos



AULA 3Trajetos, Caminhos, Circuitos, Grafos Conexos


Trajetos, Caminhos,

Circuitos,

Trajetos, Caminhos, Circuitos, Grafos Conexos



Vamos discutir aqui alguns tipos especiais de subgrafos de um grafo G.Quando discutimos o problema das Pontes de Knigsbergh, estvamosinteressados em determinar um roteiro que passasse por todas as pontesapenas uma vez. Se estudarmos este problema atravs de grafos, vamosprecisar de alguns conceitos para achar a soluo do problema.

Definio 1. Dado um grafo G(V,A), um passeio em G consiste deuma sequncia finita alternada de vrtices e arestas, comeando eterminando por vrtices, tal que cada aresta incidente ao vrtice que aprecede e ao que a sucede.

Definio 2. Dado um grafo G(V,A), um trajeto em G consiste deuma sequncia finita alternada de vrtices e arestas, comeando eterminando por vrtices, tal que cada aresta aparece apenas uma vez e incidente ao vrtice que a precede e ao que a sucede.

casaHighlight

casaHighlight

casaHighlight

casaHighlight

casaHighlight



Exerccio 3. Considere o grafo G abaixo

1

23

4 5

a b

c d

e f

67

8 9 10

11

G:

Determine:

- um trajeto onde h repetio de vrtices.

- um trajeto onde no h repetio de vrtices.



Definio 4. Dado um grafo G(V,A), um caminho em G consiste deuma sequncia finita alternada de vrtices e arestas, comeando eterminando por vrtices, tal que cada aresta incidente ao vrtice que aprecede e ao que a sucede e no h repetio de vrtices. Em outraspalavras, um caminho um trajeto onde no repetio de vrtices.

Exerccio: Considere o grafo G do Exerccio 3. Identifique caminhosentre os vrtices a e f .

Observao: Em grafos simples podemos mencionar um caminho outrajeto listando apenas os vrtices (ou arestas), sem meno explcita sarestas (ou vrtices).

casaHighlight

casaHighlight

Questes:Trajetos, Caminhos, Circuitos, Grafos Conexos


1. Qual o grau dos vrtices pertencentes a um caminho?




Os vrtices finais de um caminho possuem grau 1 e os demais,vrtices intermedirios, possuem grau 2.

2. Qual o comprimento de um caminho/trajeto em grafos novalorados? E em grafos valorados?




Os vrtices finais de um caminho possuem grau 1 e os demais,vrtices intermedirios, possuem grau 2.

2. Qual o comprimento de um caminho/trajeto em grafos novalorados? E em grafos valorados?

Para grafos no valorados o comprimento igual ao nmero dearestas includas no caminho, e em grafos valorados igual somados valores das arestas.



Definio 5. Um trajeto no qual o vrtice inicial e o final so iguais chamado de trajeto fechado.

Definio 6. Um trajeto fechado no qual nenhum vrtice (com exceodo inicial e do final) aparece mais de uma vez chamado de Ciclo(circuito ou caminho fechado).

Exemplo 7. A sequncia {c, a, d, e, c} um exemplo de ciclo no grafodo Exemplo 3. J a sequncia {a, b, d, a, e, c, a} um contra-exemplo.Observe neste contra-exemplo que o vrtice inicial . . . . . . e o vrticefinal . . . . . .. Qual o 4o vrtice desta sequncia? Esta sequncia no um ciclo pois o 4o vrtice aparece mais de vez.

casaHighlight



Estes conceitos podem ser resumidos atravs do seguinte diagrama:

Subgrafo

Trajeto

Caminho Circuito

Exerccios:Trajetos, Caminhos, Circuitos, Grafos Conexos


1. Considere o grafo:1

2

3

4 5

ab

c

de

f

6

g

h

i

j

(a) Liste todos os trajetos existentes entre os vrtices 5 e 6.

(b) Liste todos os caminhos existentes entre os vrtices 5 e 6.

(c) Quais dos trajetos obtidos no item (a) so caminhos?

(d) D o comprimento de cada um dos caminhos do item (b).

2. Sejam a, b e c trs vrtices distintos em um grafo. Se existe umcaminho entre a e b e tambm existe um caminho entre b e c,mostre que existe um caminho entre a e c.

Grafos Conexos




Considere os grafos abaixo:

v1v2

v1

v2

G1 G2

E possvel achar um caminho entre os vertices v1 e v2?

Definio 8. Um grafo dito conexo se existir pelo menos um caminhoentre cada par de vrtices do grafo. Caso contrrio, o grafo chamadode desconexo.

O grafo G1 acima conexo, e o grafo G2 desconexo.



Cada um dos subgrafos conexos maximais de um grafo desconexo chamado de uma componente do grafo. Ou seja, uma componente umsubgrafo conexo que no esteja estritamente contido em outrossubgrafos conexos. 1

Dado um grafo qualquer, como determinar se o grafo conexo?

Teorema 9. Um grafo G(V,A) desconexo se e somente se seuconjunto de vrtices V puder ser particionado em dois conjuntosdisjuntos e no-vazios, V1 e V2, de forma que no exista uma aresta comuma extremidade em V1 e outra extremidade em V2.

1Sejam S e S tais que S S. S maximal em relao a uma propriedade Pquando S satisfaz P e no existe S S que tambem satisfaa P .

DemonstraoTrajetos, Caminhos, Circuitos, Grafos Conexos


[] Suponhamos que G seja desconexo e mostremos que existe umapartio de V , V1 e V2, tal que no existe uma aresta com umaextremidade em V1 e outra extremidade em V2.

Seja G um grafo desconexo. Precisamos encontrar uma partio de Vque satisfaa a propriedade acima.

Considere um vrtice vi V qualquer. Forme o conjunto V1 com todosos vrtices de V que estejam ligados a vi por um caminho.

Como G desconexo, V1 no contm todos os vrtices de G. Assim osvrtices restantes formam um conjunto no-vazio V2, e no existenenhuma aresta de G com uma extremidade em V1 e outra em V2.

Portanto V1 e V2 formam a partio desejada.



[] Suponhamos que exista uma partio de V , V1 e V2, tal que noexiste uma aresta com uma extremidade em V1 e outra extremidade emV2 e mostremos que G desconexo.

Considere dois vrtices quaisquer em V , por exemplo vi e vj, tais quevi V1 e vj V2.

No pode existir nenhum caminho entre vi e vj, pois se existisse, haveriauma aresta com uma extremidade em V1 e outra em V2.

Portanto se uma partio existe ento o grafo desconexo.

vi

vj

V1 V2



Questo: Qual o nmero mximo de arestas que um grafo simplescom n vrtices pode ter?Cada vrtice pode ser ligado pr uma aresta a cada um dos outrosvrtices do grafo, isto aos outros (n 1). Isto nos d (n 1) arestas.Com existem n vrtices, teremos ento n(n 1) arestas. No entanto,cada aresta interliga dois vrtices e portanto est sendo considerada duasvezes. Assim, para obtermos o nmero correto de arestas necessriodividir o valor que temos at o momento por 2. O nmero mximo dearesta ento:

n(n 1)/2.

Teorema 10. Seja G um grafo simples com n vrtices. Se G possui kcomponentes, ento o nmero m de arestas de G satisfaz

n k m (n k)(n k + 1)/2.

DemonstraoTrajetos, Caminhos, Circuitos, Grafos Conexos


Vamos provar m n k por induo sobre o nmero de arestas de G.

claro que o resultado verdadeiro para um grafo nulo (m = 0).

Suponha que a desigaldade verdadeira para todo grafo com menos doque m0 arestas, onde m0 um inteiro positivo.

Vamos supor ainda, sem perda de generalidade, que G possui o menornmero de arestas possvel, no sentido de que a retirada de qualqueraresta de G aumenta o nmero de componentes em uma unidade.

Neste caso, o grafo resultante teria os mesmos n vrtices, k + 1componentes e m0 1 aretas.

Segue da hiptese de induo que

m0 1 n (k + 1) m0 n k.



Agora mostremos que vale a segunda desigualdade, supondo, sem perdade generalidade, que cada componente de G um grafo completo.

Suponhamos que existam dois componentes Ci e Cj com ni e njvrtices, respectivamente, onde ni nj > 1.

Se trocarmos Ci e Cj por grafos completos com ni + 1 e nj 1 vrtices,ento o nmero total de vrtices permanece o mesmo, e o nmero dearestas alterado para

[(ni+1)nini(ni1)]/2[nj(nj1)(nj1)(nj2)]/2 = ninj+1 > 0.

Segue que, para que o nmero mximo de arestas seja atingido, G deveconsistir de um grafo completo com n (k 1) vrtices e k 1 vrticesisolados.



Exemplo 11. Para n = 6 e k = 2:

(a) Componente 1: K4, Componente 2: uma aresta;

(b) Componente 1: K3, Componente 2: K3;

(c) Componente 1: K5, Componente 2: 1 vrtice.

Exerccios:Trajetos, Caminhos, Circuitos, Grafos Conexos


1. Desenhe um grafo conexo que se torna desconexo quando qualqueraresta removida.

2. Mostre que um grafo conexo G se mantm conexo aps a remoode uma aresta aj se e somente se a aresta pertence a algum circuitode G.

3. Mostre que qualquer grafo simples com n vrtices e mais do que(n 1)(n 2)/2 arestas conexo.

Teoria dos Grafos



Grafos direcionados (Digrafos)


Grafos Direcionados(Digrafos)

Grafos Direcionados (Digrafos) Grafos e Algoritmos



At o momento trabalhamos com grafos tais que as arestas so paresno ordenados de vrtices.

Vrias situaes prticas requerem que associemos sentido s arestasdo grafo.

Pr exemplo, considere um grafo representando as ruas de uma cidade.Nem todas as ruas so de mo dupla. Ao se estudar rotas de nibus necessrio considerar se as ruas so de mo nica, isto permitem fluxoapenas no sentido (vi, vj) ou se so de mo dupla.

Outras situaes so: fluxograma de programas computacionais ondeos vrtices representam instrues e as arestas a seqncia de execuo;redes eltricas; fluxos em redes que possuem vlvulas nos encanamentos.

Quando associamos sentido s arestas do grafo temos um grafodirecionado ou digrafo.



A maioria dos conceitos e terminologia usados para grafosno-orientados so tambm aplicveis para digrafos. Pr exemplo o conceito de planaridade independe do sentido associados arestas.Vamos chamar ateno neste tpico apenas para as propriedades econceitos que se aplicam apenas a digrafos. O conceito formal de umgrafo direcionado dado a seguir.

Definio 1. Um grafo direcionado G(V,A) constitudo pr umconjunto V = {v1, v2, . . . , vn} no-vazio de objetos, chamados vrtices(ou ns), e um conjunto A = {a1, a2, . . . , am} de arestas ou arcos, euma aplicao que associa cada aresta a um par ordenado de vrtices.

Os digrafos so representados atravs de um diagrama onde os vrticesso representados por pontos e cada aresta (vi, vj) representada poruma linha ligando vi a vj com uma seta apontando para vj.



Exemplo 1

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

A = {(v1, v2), (v1, v3), (v2, v4), (v3, v4), (v4, v5), (v1, v2), (v2, v2)}.

v1

v2

v3

v4

v5



Exemplo 2



Em digrafo, quando dizemos que uma aresta incidente a um vrticequeremos saber em que sentido, isto , se a aresta convergente oudivergente a este vrtice.

natural dizer que uma aresta a associada ao par (vi, vj) convergentea vj e divergente de vi.

Em relao ao grau de um vrtice vi queremos tambm saber:

n o nmero de arestas convergentes, chamado grau de entrada edenotado de(vi) (ou d(vi));

n o nmero de arestas divergentes, chamado grau de sada edenotado ds(vi) (ou d+(vi)).



Exerccio Seja G(V,A) um digrafo. Mostre que

viV

de(vi) =

viV

ds(vi) = m,

onde m o nmero de arestas de G.



Mais definies:Temos uma fonte quando o grau de entrada nulo e um sumidouroquando o grau de sada nulo.

Duas arestas so paralelas se elas incidem nos mesmos vrtices epossuem a mesma orientao.

Muitas das propriedades de grafos no orientados so vlidas paradigrafos e portanto muitas vezes a orientao do grafo desconsiderada.

Definimos o grafo associado a um digrafo G como sendo o grafo obtidodesconsiderando a orientao de G.



Orientao de um grafoA operao oposta tambm pode ser considerada:

Dado um grafo (no orientado) G podemos definir alguma orientaopara suas arestas obtendo assim um digrafo ~G chamado de um digrafoassociado a G.

Observemos que enquanto o grafo associado a um digrafo nico (amenos de isomorfismos), um digrafo associado a um grafo pode tervrias orientaes distintas.



Digrafos Isomorfos Dados digrafos G e H, dizemos que eles soisomorfos quando os grafos associados so isomorfos e alm disso aorientao das arestas coincide.Exerccio: Verifique se os pares de digrafos abaixo (G1 e G2, G3 e G4 )so isomorfos.

G1 G2

Tipos de digrafosGrafos Direcionados (Digrafos) Grafos e Algoritmos


Seja G(V,A) um digrafo. Ento G dito

n Simples se no possui loops ou arestas paralelas;

n Assimtrico se possui no mximo uma aresta orientada entre cadapar de vrtices;

n Simtrico se para cada aresta (a, b) existe tambm uma aresta(b, a);

n Completo Simtrico se G simples e existe exatamente uma arestadirecionada de todo vrtice para todos os outros vrtices;

n Completo Assimtrico se G assimtrico e existe exatamente umaaresta entre cada par de vrtices;

Tipos de digrafos (cont.)Grafos Direcionados (Digrafos) Grafos e Algoritmos


n Balanceado se de(vi) = ds(vi) para todo vi V ;

n Regular se existe um inteiro k tal que tal que de(vi) = ds(vi) = kpara todo vi V . Dizemos que o digrafo k-regular.

ExercciosGrafos Direcionados (Digrafos) Grafos e Algoritmos


1. Mostre que um digrafo completo assimtrico com n vrtices possuin(n 1)/2 arestas.

2. Mostre que um digrafo completo simtrico com n vrtices possuin(n 1) arestas.

Caminhos OrientadosGrafos Direcionados (Digrafos) Grafos e Algoritmos


n Definimos passeios, trajetos, caminhos e circuitos da mesma forma que paragrafos. No entanto, a orientao das arestas deve coincidir:

isto , dado um par de arestas consecutivas onde v o vrtice comum, a

primeira aresta converge para v enquanto a segunda diverge de v. Neste caso

podemos chamar a sequencia de passeio orientado, ou simplesmente passeio.

Quando a orientao das arestas no coincide, dizemos que a sequncia um

semi-passeio.

n De forma similar definimos semi-trajetos, semi-caminhos e semi-circuitos.

Digrafos ConexosGrafos Direcionados (Digrafos) Grafos e Algoritmos


Definio 2. Um digrafo D(V,A) fortemente conexo se existe umcaminho orientado de vi para vj e de vj para vi, quaisquer que sejamvi, vj V .

Um digrafo D(V,A) fracamente conexo se o grafo associado conexomas D no fortemente conexo.

G1 G2

PropriedadesGrafos Direcionados (Digrafos) Grafos e Algoritmos


Um digrafo dito ser acclico se no possui circuitos.

n Um digrafo acclico se e somente se todo trajeto orientado tambm um caminho orientado.

n Todo digrafo acclico possui pelo menos uma fonte e um sumidouro.

Exerccio: Encontre exemplos que ilustrem as propriedades acima.

Teoria dos Grafos



Grafos e Algoritmos


Algoritmos e contagem do nmero de Operaes


n Problemas de otimizao e problemas computacionais em geral soresolvidos por meio de algoritmos.

n De uma forma vaga, podemos dizer que um algoritmo umconjunto de finito de instrues do tipo usado em linguagens deprogramao tais como: operaes aritmticas, instruescondicionais, instrues de leitura e escrita.

n O tempo de execuo de um algoritmo depende de vrios fatores,entre eles: boa prtica de programao, codificao das instruesde forma inteligente, estrutura de dados, equipamento onde estasendo executado.

n Apesar da importncia destes fatores, estamos interessados emavaliar a qualidade de um algoritmo independentemente da formaem que est codificado ou da mquina onde esta sendo executado.


n Uma maneira de avaliar o desempenho computacional de umalgoritmo independentemente de uma implementao particular calcular aproximadamente o nmero de operaes (aritmticas,condicionais, etc) que o mesmo executa.

n Esta prtica em geral satisfatria, apesar de desconsiderar queoperaes com nmeros inteiros de poucos dgitos so menostrabalhosas que operaes envolvendo nmeros reais de altapreciso, ou nmeros inteiros de muitos dgitos.

n Um clculo mais preciso considera tambm os dados do problema.

n Neste curso, iremos considerar apenas os dados relativos dimenso do problema. Um tratamento mais detalhado sobre aavaliao do desempenho computacional de um algoritmo pode serencontrado em [1], [2] e [3].

Exemplo 1 - Produto Escalar entre dois vetores

(Algoritmo 1)


Calcula o produto escalar p entre os vetores v, w Rn.

incio

p = v(1) w(1)

Para i = 2 at n faa

p = p+ v(i) w(i)

fim

escreva p

fim

Exemplo 2 - Produto de duas matrizes

(Algoritmo 2)


Calcula o produto C de duas matrizes A Rmn, B Rnp.

incio

para i = 1 at m faa

para j = 1 at p faa

c(i, j) = a(i, 1) b(1, j)

para k = 2 at n

c(i, j) = c(i, j) + a(i, k) b(k, j)

fim

fim

fim

fim

Contagem do nmero de operaes


n Note que no Algoritmo 1 temos n multiplicaes e n 1 adies totalizando2n 1 operaes.

n O algoritmo 2 calcula os elementos c(i, j) da matriz C fazendo o produtoescalar entre a linha i da matriz A e a coluna j da matriz B. Isto , socalculado m p produtos escalares que por sua vez requerem 2n 1 operaes,totalizando m p(2n 1) operaes.

n Para os algoritmos 1 e 2 foi possvel fazer a contagem exata do nmero deoperaes que cada um executa. Porm, nem sempre a contagem do nmerode operaes trivial.

n Procura-se ento fazer uma estimativa do crescimento do nmero de operaesem funo dos parmetros que definem o problema.

n Assim, para o Algoritmo 1 suficiente dizer que o nmero de operaesexecutadas uma funo linear de n, enquanto que o nmero de operaes doAlgoritmo 2 uma funo cbica de n,m e p.

Definio 1: Sejam f e g : ++ RR n dizemos que: a) f(n) O(g(n)) (f da ordem de g) se existirem constantes c, 0>on

tal que )()( ncgnf para onn . (complexidade no pior caso)b) f(n) ))(( ng (f da ordem de g) se existirem constantes c, 0>on

tal que )()( ncgnf para onn . (complexidade no melhor caso) c) f(n) ))(( ng se f(n) O(g(n)) e f(n) ))(( ng . (Complexidade exata)

Para maior preciso na estimativa do nmero de operaes utilizada aexpresso ordem de magnitude, Definida 1.




Exemplos:

1. f(p) = 3p3 + 2p2 da ordem de p3, ou simplesmente f O(p3), pois parap0 = 0 e c = 5, temos 3p

3 + 2p2 5p3.

2. f(p) = (p+ 1)2 da ordem de O(p2). Neste caso, para p0 = 1 e c = 4, temos(p+ 1)2 4p2.

3. f(p) = 542 O(1).

4. Observe que com esta definio as funes f(x) = 1010n3 + n2 eg(x) = n3 + n2 possuem complexidade O(n3).

Exerccio: Verificar que:

a) f(p) = 3p3 + 2p2 + 10 (n3).

b) f(n) = n logn O(n2) e (n).

Como avaliar se a complexidade de um dado

algoritmo boa ou ruim?


Suponha que possamos escolher entre dois algoritmos, A e B. O tempode execuo do algoritmo A 10n/100, isto O(10n) (exponencial) e doalgoritmo B 10n3, isto O(n3) (polinomial).

Para valores bem pequenos de n, por exemplo n = 3, o algoritmo A mais eficiente que o algoritmo B. Veja a tabela abaixo:

n 10n/100 10n3

3 10 904 100 6405 1000 12506 10000 2160


Mas o que acontece para valores maiores de n?

Suponha que dispomos de uma mquina capaz de executar 107

operaes aritmtica por segundo, e que estamos dispostos a executar osdois algoritmos por 1000 segundos.

Qual a dimenso dos problemas que poderamos resolver com cada umdos algoritmos dentro deste intervalo de tempo?

Se a mquina executa 107 operaes por segundo, o algoritmo A,executado nesta mquina pode realizar quantas operaes em 1000segundos?


Uma simples regra de trs:

1 s 107

1000 s 10n/100

nos leva a seguinte equao:

10n

100= 107 1000 n = 12.

Isto , neste tempo o algoritmo A resolve problemas com n 12.

Fazendo um raciocnio similar para o algoritmo B, temos que este resolveproblemas com n 1000.

Estes clculos indicam que algoritmos polinomiais permitem a resoluode problemas maiores dentro de um mesmo intervalo de tempo.


n De uma maneira geral algoritmos com complexidade computacional polinomialso considerados rpidos e eficientes enquanto que os algoritmos comcomplexidade exponencial so vistos como lentos e ineficientes.

n Este ponto de vista se justifica em muitas, mas no todas, situaes.

n A otimizao linear um exemplo onde algoritmos exponenciais (baseados nomtodo simplex) e algoritmos polinomiais (mtodos de ponto interior)competem em p de igualdade.

n O estudo de complexidade de algoritmos ser til para determinamos o grau dedificuldade de resoluo de problemas em Grafos.

n Em geral as medidas de complexidade so feitas em funo da dimenso doproblema.

n No caso de grafos em funo do nmero de vrtices, n, e do nmero de arestas,m.

Teoria dos Grafos



Representao de Grafos




A representao computacional de um grafo (ou digrafo) deve usar umaestrutura que:

n corresponde de forma nica a um grafo dado;

n pode ser armazenada e manipulada em um computador.

A representao grfica de um grafo atravs do diagrama de pontos elinhas no satisfaz a segunda condio acima.

Vamos discutir a seguir algumas estruturas que satisfazem estes doiscritrios.

Considere um grafo G(V,A) com n vrtices e m arestas.

Matriz de AdjacnciaRepresentao de Grafos


uma matriz n n, denotada por X = [xij] e definida como:

xij =

{1 se existe uma aresta entre os vrtices vi e vj,0 caso contrrio.

Observaes:

n necessrio fazer uma rotulao nos vrtices de G.

n A complexidade em termos de espao de memria de um algoritmoque use uma matriz de adjacncia para armazenar o grafo O(n2).

n Qualquer tipo de grafo pode ser armazenado nesta estrutura?

Matriz de AdjacnciaRepresentao de Grafos


uma matriz n n, denotada por X = [xij] e definida como:

xij =

{1 se existe uma aresta entre os vrtices vi e vj,0 caso contrrio.

Observaes:

n necessrio fazer uma rotulao nos vrtices de G.

n A complexidade em termos de espao de memria de um algoritmoque use uma matriz de adjacncia para armazenar o grafo O(n2).

n Qualquer tipo de grafo pode ser armazenado nesta estrutura? No!Apenas grafos que no possuam arestas paralelas.

ExemploRepresentao de Grafos


ObservaesRepresentao de Grafos


n As entradas ao longo da diagonal principal de X so todas nulas se,e somente se, o grafo no possui laos. Quando h um lao em umvrtice vi temos xii = 1.




n Se o grafo simples, o grau de um vrtice dado pela soma doselementos de sua linha (ou coluna) correspondente.





n Permutaes de linhas e das colunas correspondentes implicam emuma reordenao dos vrtices. Portanto dois grafos simples G1 eG2 so isomorfos se, e somente se, X(G2) = R1X(G1)R, onde R uma matriz de permutao.






n Dado uma matriz qualquer Q Rnn simtrica e binria, sempre possvel construir um grafo G com n vrtices tal que X(G) = Q.






n Dado uma matriz qualquer Q Rnn simtrica e binria, sempre possvel construir um grafo G com n vrtices tal que X(G) = Q.

n Quantos elementos diferentes de zero esta matriz possui?



n Um grafo G desconexo com dois componentes G1 e G2 se, esomente se,

X(G) =

[X(G1) 0

0 X(G2)

].



n Um grafo G desconexo com dois componentes G1 e G2 se, esomente se,

X(G) =

[X(G1) 0

0 X(G2)

].

n O que representa a matriz B = X2? Os elementos bij, i 6= j,representam o nmero de caminhos distintos de comprimento 2entre os vrtices vi e vj. De fato:

bij =n

k=1

xikxkj = xi1x1j + xi2x2j + . . .+ xinxnj

e existe um caminho se xik = xkj = 1, e o caminho dado por{i, (i, k), k, (k, j), j}.



Teorema 1. Seja X a matriz de adjacncia de um grafo simples G.Ento a ij-sima entrada de Xr o numero de passeios diferentes decomprimento r entre os vrtices vi e vj .




Corolrio 5. Em um grafo conexo, a distncia entre dois vrtices vi evj, i 6= j, k se, e somente se, k o menor inteiro para o qual aij-sima entrada em Xk no-nula.




Corolrio 8. Em um grafo conexo, a distncia entre dois vrtices vi evj, i 6= j, k se, e somente se, k o menor inteiro para o qual aij-sima entrada em Xk no-nula.

Corolrio 9. Se X a matriz de adjacncia de um grafo com nvrtices, e

Y = X +X2 +X3 + . . .+Xn1,

ento G desconexo se, e somente se, existe ao menos uma entrada namatriz Y que igual a zero.



possvel utilizar esta estrutura para armazenar digrafos?

Sim. Dado um digafo D(V,A) com n vrtices e sem arestas paralelas,definimos

xij =

{1 se existe uma aresta direcionada do vrtice vi para o vrtice vj ,0 caso contrrio.



n Neste caso a matriz s ser simtrica se o digrafo for simtrico.

n O grau de sada do vrtice vi dado pela soma dos elementos dalinha i.

n O grau de entrada do vrtice vi dado pela soma dos elementos dacoluna i.

n Se X a matriz de adjacncia de um digrafo D, ento a suatransposta X a matriz de adjacncia do digrafo obtido pelainverso da orientao das arestas de D.

Matriz de IncidnciaRepresentao de Grafos


Seja G um grafo com n vrtices e m arestas. Sua matriz de incidncia uma matriz de ordem nm, denotada por A = [aij ], definida como

xij =

{1 se a aresta aj incidente no vi,0 caso contrrio.

Observaes:

n necessrio fazer uma rotulao nos vrtices e nas arestas de G.

n A complexidade em termos de espao de memria de um algoritmoque use uma matriz de adjacncia para armazenar o grafo O(nm).

n Qualquer tipo de grafo pode ser armazenado nesta estrutura?

Matriz de IncidnciaRepresentao de Grafos


Seja G um grafo com n vrtices e m arestas. Sua matriz de incidncia uma matriz de ordem nm, denotada por A = [aij ], definida como

xij =

{1 se a aresta aj incidente no vi,0 caso contrrio.

Observaes:

n necessrio fazer uma rotulao nos vrtices e nas arestas de G.

n A complexidade em termos de espao de memria de um algoritmoque use uma matriz de adjacncia para armazenar o grafo O(nm).

n Qualquer tipo de grafo pode ser armazenado nesta estrutura? No!Apenas grafos que no possuam arestas lao.



n Como cada aresta incidente em exatamente dois vrtices, cada coluna deA(G) possui exatamente dois 1s.

n O nmero de 1s em cada linha igual ao grau do vrtice correspondente.

n Uma linha de 0s representa um vrtice isolado.

n Arestas paralelas correspondem a colunas idnticas.

n Um grafo G desconexo com dois componentes G1 e G2, ento

A(G) =

[A(G1) 0

0 A(G2)

].

n Dois grafos G1 e G2 so isomorfos se, e somente se, suas matrizes de incidnciaA(G1) e A(G2) diferem apenas por permutaes de linhas e colunas.

n Quantos elementos diferentes de zero esta matriz possui?



possvel utilizar esta estrutura para armazenar digrafos?

Sim. Com uma pequena modificao, uma vez que ao dizer que umaaresta incide em um vrtice necessrio especificar se ela converge paraou diverge para este vrtice.

Seja D um digrafo com n vrtices e m arestas e sem arestas lao. Suamatriz de incidncia A = [aij] Rnm definida como

xij =

1 se a aresta aj diverge do vrtice vi,1 se a aresta aj converge para o vrtice vi,0 caso contrrio.



As duas representaes dadas (matrizes de adjacncia e de incidncia)so importantes porque elas facilitam a recuperao de uma srie deinformaes a respeito de um grafo.

Por exemplo o grau de um vrtice, determinar se dois vrtices soadjacentes, entre outras.

No entanto elas no valem para qualquer grafo dado, e demandam muitoespao de memria: O(n2) e O(nm) para armazenar apenas 2melementos diferentes de zero.

possvel encontrar formar mais eficientes de armazenamento de dados.

bom salientar no entanto que a melhor maneira de armazenar umgrafo ou digrafo vai depender do algoritmo a ser implementado.

Lista de ArestasRepresentao de Grafos


O digrafo (ou grafo) G representado por dois vetores m-dimesionaisF = (f1, f2, . . . , fm) e H = (h1, h2, . . . , hm).

Cada elemento destes vetores recebe o rtulo de um vrtice, de modoque a i-sima aresta diverge do vrtice fi e converge para o vrtice hi.

Qual o espao necessrio para esta estrutura? O(2m).

Lista de sucessoresRepresentao de Grafos


Quando a razo m/n no muito alta, conveniente usar uma lista desucessores.

Para isto definimos n vetores. Cada vetor associado a um vrtice.

O primeiro elemento do vetor k o vrtice vk e os demais elementos soos vrtices adjacentes ao vrtice vk (em um digrafo, os vrtice que estoligados ao vrtice k por um caminho de comprimento 1).

Supondo que dmed o grau mdio (ou grau de sada mdio), o espao dememria necessrio para esta estrutura O(ndmed).

ExerccioRepresentao de Grafos


n Construa a lista de arestas e a lista de sucessores para o grafo abaixo.

n Escreva um algoritmo para transformar a matriz de incidncia de um grafo (oudigrafo) na matriz de adjacncias. Codifique o algoritmo na sua linguagem deprogramao favorita. Teste com grafos de diversas densidades. Qual acomplexidade computacional do seu algoritmo?

Teoria dos Grafos



AULACaminho mnimo - Algoritmo de Djskstra


Caminho Mnimo em

Grafos

Introduao

Teoria dos Grafos 3

Considere a rede:

s t

a b

cd

9

15

4

2

2

3

35

16

6

5

7

21

Teoria dos Grafos 4

Dado dois vrtices nesta rede, queremos determinar o menor caminhoentre eles.

Uma primeira questo como representar os valores associados sarestas neste grafo. Isto pode ser feito atravs da matriz de pesos.

Seja D um digrafo simples cujas arestas possuem pesos associados,digamos, a cada aresta (vi, vj) est associado um nmero real wij 0(que pode representar comprimento, distncia, valor, etc).

Vamos definir wii = 0 para todo i e wij = quando no existe umaaresta entre os vrtices vi e vj .

Assim a matriz de pesos uma matriz n n definida como W = [wij],onde n o nmero de vrtices.

Exemplo

Teoria dos Grafos 5

Construir a matriz de pesos para a rede abaixo:

s t

a b

cd

9

15

4

2

2

3

35

16

6

5

7

21

Teoria dos Grafos 6

Observao 1. Em geral

n wij 6= wji e

n wij + wjk pode ser menor ou igual a wik.

Por exemplo, na rede anterior,

wsd + wda = 9 + 4 15 = wsa.

Teoria dos Grafos 6

Observao 2. Em geral

n wij 6= wji e

n wij + wjk pode ser menor ou igual a wik.

Por exemplo, na rede anterior,

wsd + wda = 9 + 4 15 = wsa.

O algoritmo que ns vamos ver foi proposto por Dijkstra em 1959 e um dos mais eficientes at hoje. Vamos supor ento que queremosencontrar o caminho mnimo entre s e t na rede acima.

Idia do Algoritmo:

Teoria dos Grafos 7

n Rotular os vrtices do digrafo.

n A partir do vrtice inicial s, proceder em direo ao vrtice final t(seguindo as arestas orientadas) rotulando os vrtices com as suasdistncias ao vrtice s, medida at aquele momento.

n A cada estgio do algoritmo teremos vrtices que possuem rtulostemporrios e outros rtulos permanentes.

n O rtulo de um vrtice vj feito permanente quando este rtulorepresenta a menor distncia de s at vj .

n Comeamos associando rtulo permanente igual a zero para o vrtice s, eum rtulo temporrio igual a para os outros n 1 vrtices do grafo.

n A cada iterao, um novo vrtice recebe um rtulo permanente deacordo com as seguintes regras:

Teoria dos Grafos 8

1. Cada vrtice vj com um rtulo temporrio, recebe um novo rtulotemporrio dado por:

min{rtulo de vj , (rtulo de vi) + wij}

onde vi o vrtice que recebeu rtulo permanente na iterao anterior ewij o valor da aresta entre o vrtice vi e o vrtice vj .

2. Encontre o menor valor entre os rtulos temporrios.

Este ser o rtulo permanente do respectivo vrtice.

Em caso de empate selecione qualquer um dos candidatos e atribuartulo permanente ao escolhido.

Repetir 1 e 2 at que o vrtice destino, t, receba um rtulo permanente.

Exemplo

Teoria dos Grafos 9

Vamos aplicar a ideia acima rede abaixo:

s t

a b

cd

9

15

4

2

2

3

35

16

6

5

7

21

Aplicao do algoritmo:

Teoria dos Grafos 10

Inicializaao: rot(s) = 0 permanente,

rot(a) = rot(b) = rot(c) = rot(d) = rot(t) = so temporrios

it = 1

Regra 1 Novo rtulo

Novo rot(a) = min{, 0 + wsa} = min{, 15} = 15

Novo rot(b) = min{, 0 + wsb} = min{,} =

Novo rot(c) = min{, 0 + wsc} = min{,} =

Novo rot(d) = min{, 0 + wsd} = min{, 9} = 9

Novo rot(t) = min{, 0 + wst} = min{,} =

Regra 2 Rtulo permanente

min{15,,, 9,} = 9 rot(d) torna-se permanente

Aplicao do algoritmo cont.:


it = 2

Regra 1 Novo rtulo

Novo rot(a) = min{15, 9 + wda} = min{15, 9 + 4} = 13

Novo rot(b) = min{, 9 + wdb} = min{,} =

Novo rot(c) = min{, 9 + wdc} = min{, 9 + 2} = 11

Novo rot(t) = min{, 9 + wdt} = min{,} =


min{13,, 11,} = 11 rot(c) torna-se permanente



it = 3

Regra 1 Novo rtulo

Novo rot(a) = min{13, 11 + wca} = min{13, 11 +} = 13

Novo rot(b) = min{, 11 + wcb} = min{, 11 +} =

Novo rot(t) = min{, 11 + wct} = min{, 11 + 7} = 18


min{13,, 18} = 13 rot(a) torna-se permanente



it = 4

Regra 1 Novo rtulo

Novo rot(b) = min{, 13 + wab} = min{, 13 + 35} = 48

Novo rot(t) = min{18, 13 + wat} = min{18, 13 +} = 18


min{48, 18} = 18 rot(t) torna-se permanente

Fim



it = 4

Regra 1 Novo rtulo

Novo rot(b) = min{, 13 + wab} = min{, 13 + 35} = 48

Novo rot(t) = min{18, 13 + wat} = min{18, 13 +} = 18


min{48, 18} = 18 rot(t) torna-se permanente

Fim

Podemos parar pois o vrtice destino, t, recebeu rtulo permanente.

Assim o menor caminho entre s e t tem comprimento igual a 18.

Como recuperar o caminho? A partir do vrtice destino t, verificamos o vrtice com

rtulo permanente usado na obteno do rtulo de t. No nosso exemplo, o vrtice c.

Repetimos o processo a partir de c at alcanar o vrtice inicial s. Assim temos

t, c, d, s. O caminho obtido invertendo a ordem obtida: s, d, c, t.

Exemplo


Rastrear o algoritmo de Dijkstra usando o digrafo com vrticess, a, b, c, d, t cuja matriz de pesos associada :

W =

0 7 4 9 7 7 0 1 64 1 0 3 9 3 0 1 37 1 0 5 6 3 5 0

.

Observaes


1. Outros Algoritmos para problemas de Caminho Mnimo em grafospodem ser encontrados por exemplo na pgina 283 de: [OtimizaoCombinatria e Programao Linear, M.C. Goldbarg e H.P.L. Luna,Ed. Campus, 2000].

2. O algoritmo de Dijskstra funciona apenas se wij 0 para todosi, j. Verifique este fato aplicando o algoritmo seguinte rede paraencontrar o menor caminho entre v1 e v3:

v1

v2 v3

15

Teoria dos Grafos



Grafos Eulerianos


Grafos Eulerianos

Grafos Eulerianos Digrafos Eulerianos

IntroduoGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 3

No incio do curso ns estudamos o problema das Pontes de Konigsberge representamos o problema atravs do seguinte grafo::

A

C

B

D

Queramos saber se possvel fazer um passeio pela cidade, comeando eterminando no mesmo lugar e passando por cada uma das pontes apenasuma vez.

Em outras palavras queramos encontrar no grafo acima um

trajeto fechado que inclusse todas as arestas do grafo.

DefiniesGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 4

Definio 1. Um trajeto que inclua todas as arestas de um dado grafo

G(V,A) chamado de trajeto euleriano.

Seja G um grafo conexo. Dizemos que G euleriano se possui um

trajeto euleriano fechado.

Um grafo G no-euleriano dito ser semi-euleriano se possui um

trajeto euleriano.

Observao: Note que em um grafo euleriano cada aresta percorridauma, e uma nica, vez.

ExemplosGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 5

A seguir temos exemplos de grafos euleriano, semi-euleriano eno-euleriano:

Resultado auxiliarGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 6

Lema 2. Se G(V,A) um grafo tal que d(v) 2 para todo v V ,ento G contm um ciclo.

Demonstrao. Se G possui laos ou arestas paralelas, no h o queprovar.

Vamos supor que G um grafo simples. Seja v0 V um vrticearbitrrio de G. Como d(v) 2 para todo v V , podemos construir umpasseio v0 v1 v2 indutivamente escolhendo vi+1 como sendoqualquer vrtice adjacente a vi exceto vi1.

Como G possui uma quantidade finita de vrtices, em algum momentoescolheremos algum vrtice, digamos vk, pela segunda vez.

A parte do passeio entre e primeira e a segunda ocorrncia de vkconstitui um ciclo.

Condio necessria e suficienteGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 7

Teorema 3 (Euler, 1736). Um grafo conexo G(V,A) euleriano se, esomente se, o grau de cada vrtice de G par.

Demonstrao. () Seja T um trajeto euleriano fechado de G. Cadavez que um vrtice v ocorre no trajeto T , h uma contribuio de duasunidades para o grau de v (uma aresta para chegar a v e outra parasair).

Isto vale no s para os vrtices intermedirios mas tambm para ovrtice final, pois samos e entramos no mesmo vrtice no incio e nofinal do trajeto.

Como cada aresta ocorre exatamente uma vez em T , cada vrtice possuigrau par.

Cont. da demonstraoGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 8

() A prova por induo no nmero de arestas de G. Suponhamosque o grau de cada vrtice de G par. Como G conexo, d(v) 2 paratodo v V . Segue ento do lema anterior que G contm um ciclo C.

Se C contm todas as arestas de G, o teorema est provado.

Se no, removemos de G as arestas de C, resultando num grafo H,possivelmente desconexo, com menos aretas do que G.

C

H

H

Cont. da demonstraoGrafos Eulerianos Digrafos Eulerianos

Teoria dos Grafos 9

fcil ver que todos os vrtices de H possuem grau par. Logo, pelahiptese de induo, cada componente de H possui um trajeto eulerianofechado.

Alm disso, pela conexidade de G, cada componente de H possui aomenos um vrtice em comum com C.

Portanto, concatenando os trajetos euleriados fechados de cadacomponente de H com o ciclo C obtemos um trajeto euleriano fechadoem G, ou seja, G um grafo euleriano.

ExercciosGrafos Eulerianos Digrafos Eulerianos


Corolrio 4. Um grafo conexo euleriano se, e somente se, puder ser

decomposto em circuitos disjuntos:

G =

i

Ci, Ci Cj = grafo nulo.

Corolrio 5. Um grafo conexo semi-euleriano se, e somente se, possui

exatamente dois vrtices de grau mpar.

Algoritmo de DecomposioGrafos Eulerianos Digrafos Eulerianos


Considere um grafo conexo G(V,A), onde d(v) par v V .

Passo 1: Determine um circuito C1 em G.

Defina T1 = C1 e G1 = G.

Se T1 possui todas as arestas de G, pare. T1 o trajeto procurado.

Faa k = 1.

Passo 2: Faa k = k + 1. Construa o subgrafo Gk(Vk, Ak) removendo de Gk1 asarestas pertencentes a Tk1(Vk1, Ak1). Remova de Gk os vrtices isolados.

Passo 3: Determine um vrtice v Vk Vk1. A partir de v determine um circuito

Ck em Gk.

Passo 4: Determine Tk = Tk1 Ck.

Se Tk possui todas as arestas de G, v para o Passo 5.

Caso Contrrio, retorne ao Passo 2.

Passo 5: Pare. Tk o trajeto procurado e G =

k

i=1

Ci.

ExercciosGrafos Eulerianos Digrafos Eulerianos


Verifique se os grafos abaixo so eulerianos. Se possvel exiba um trajetoeuleriano.

Algoritmo de FleuryGrafos Eulerianos Digrafos Eulerianos


Considere um grafo conexo G(V,A), onde d(v) par v V .

Comece em qualquer vrtice v e percorra as arestas de forma aleatria,seguindo sempre as seguintes regras:

1. Exclua as arestas depois de passar por elas;

2. Exclua os vrtices isolados, caso ocorram;

3. Passe por uma ponte1 somente se no houver outra alternativa.

1Uma aresta dita ser uma ponte se a sua remoo torna o grafo desconexo.

ExemploGrafos Eulerianos Digrafos Eulerianos


Aplique o Algoritmo de Fleury para encontrar um trajeto euleriano nografo abaixo a partir do vrtice 5.

Digrafos Eulerianos

Grafos Eulerianos Digrafos Eulerianos



Definio 6. Um trajeto orientado que inclua todas as arestas de um

dado digrafo G(V,A) chamado de trajeto euleriano.

Seja G um digrafo conexo. Dizemos que G euleriano se possui um


Um digrafo G no-euleriano dito ser semi-euleriano se possui um

trajeto euleriano.



Definio 7. Um trajeto orientado que inclua todas as arestas de um

dado digrafo G(V,A) chamado de trajeto euleriano.

Seja G um digrafo conexo. Dizemos que G euleriano se possui um


Um digrafo G no-euleriano dito ser semi-euleriano se possui um

trajeto euleriano.

Observaes:

1. Um digrafo conexo euleriano necessariamente fortemente conexo.

2. Entretanto, nem todo digrafo fortemente conexo euleriano.

ExemplosGrafos Eulerianos Digrafos Eulerianos


Teorema de Euler para digrafosGrafos Eulerianos Digrafos Eulerianos


Teorema 8. Um digrafo conexo D(V,A) euleriano se, e somente se,D balanceado, i.e., de(v) = ds(v) v V .

Demonstrao: Exerccio.

Teorema de Euler para digrafosGrafos Eulerianos Digrafos Eulerianos


Teorema 9. Um digrafo conexo D(V,A) euleriano se, e somente se,D balanceado, i.e., de(v) = ds(v) v V .

Demonstrao: Exerccio.

Corolrios? Exerccios.

Teoria dos Grafos



Grafos Hamiltonianos


Grafos Hamiltonianos

Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

IntroduoGrafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 3

Um trajeto euleriano caracterizado pelo fato de incluir todas as arestasde um dado grafo, uma nica vez.

Entretanto os vrtices podem se repetir em um trajeto euleriano. Surgeento a questo da possibilidade de se obter um trajeto fechado (nonecessariamente euleriano) que inclua cada vrtice uma nica vez1; comopor exemplo, nos grafos exibidos a seguir.

1Neste caso o trajeto um circuito com n arestas.

DefiniesGrafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 4

Definio 1. Um circuito hamiltoniano em um grafo conexo umcircuito que contm todos os vrtices do grafo.

Um grafo chamado de grafo hamiltoniano se possui um circuitohamiltoniano.

Um grafo no-hamiltoniano semi-hamiltoniano se possui umcaminho que contm todos os seus vrtices (caminho hamiltoniano)

Exemplos:


Teoria dos Grafos 5

Os grafos abaixo no so hamiltonianos. Por que?

Quais so as condies necessrias e suficientes para definir se um grafo hamiltoniano?


Teoria dos Grafos 6

Esta uma questo em aberto e foi formulada pelo matemtico SirWilliam Hamilton em 1859.


Teoria dos Grafos 7

Algumas consideraes podem ser feitas:

1. Arestas paralelas e laos no podem pertencer a um circuitohamiltoniano.

2. Se um vrtice possui grau 2, as arestas a ele incidentes devempertencer ao circuito hamiltoniano.

3. Nenhum subcircuito prprio, isto , um circuito que no possuitodos os vrtices de G, pode ser formado durante a construo docircuito hamiltoniano.

4. Um vez includo um vrtice, todas as arestas a ele incidentes e queno foram inseridas no circuito podem ser desconsideradas.

ExerccioGrafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos

Teoria dos Grafos 8

Verificar se o grafo abaixo hamiltoniano:


Teoria dos Grafos 9

Para que tipo de grafo podemos garantir a existncia de um circuitohamiltoniano?

Definio 2. Um Grafo Completo um grafo simples tal que existeuma aresta entre cada par de vrtices.

Um grafo completo com n vrtices denotado por Kn.

Exemplos:



Como obter um circuito hamiltoniano em um grafo completo Kn, comn 3?

Numere os vrtices do grafo de 1 a n. Como existe uma aresta entrecada par de vrtices, a sequncia 1, 2, . . . , n um circuito hamiltoniano.

Quantos circuitos hamiltonianos um grafo completo possui? Vamosexaminar o K4:

Os circuitos {a, b, c, d, a} e {a, d, c, b, a} so diferentes ou iguais?



Partindo do vrtices 1, temos n 1 escolhas de arestas para fazer.

Em seguida, a partir do vrtice 2, temos n 2 arestas para escolher;

e assim por diante at a escolha da ltima aresta.

Ou seja, h (n 1)! possibilidades; e se considerarmos que circuitos dotipo {vi1 , vi2 , . . . , vin , vi1} so iguais ao circuito{vi1 , vin , vin1, . . . , vi2 , vi1}, teremos que o nmero total de circuitos dado por (n 1)!/2.

Teorema 3. Em um grafo completo com n vrtices existem (n 1)/2circuitos hamiltonianos aresta-disjuntos, se n 3 mpar.

Demonstrao. Exerccio.

Condio necessria e suficiente?Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos


No caso de grafos eulerianos temos uma condio necessria e suficientefacilmente verificvel.

Porm, para grafos hamiltonianos no h. Na verdade, sabe-se pouco emgeral sobre grafos hamiltonianos.

A maioria dos teoremas so da forma: Se G possui arestas suficientes,ento G hamiltoniano.

Os dois teoremas mais celebrados esto enunciados a seguir.

Teorema de Ore (1960)Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos


Teorema 4. Se G(V,A) um grafo simples com n 3 vrtices, e se

d(v) + d(w) n

para cada par de vrtices no-adjacentes v e w, ento G hamiltoniano.

Demonstrao: Procederemos por contradio. Suponha que G no hamiltoniano, mas satisfaz a hiptese.

Vamos supor ainda que G quase hamiltoniano, no sentido de que aadio de qualquer outra aresta torna-o hamiltoniano.

Se este no for o caso, adicionamos arestas extras at que o seja.

Observe que a adio de arestas no quebra a hiptese.



Sejam v, w V vrtices no-adjacentes (existe pelo menos um par, casocontrrio, G seria completo e, por conseguinte, hamiltoniano).

Logo, a adio da aresta (v, w) torna G hamiltoniano, o que implica naexistncia de um caminho passando por todos os vrtices:

v = v1 v2 vn = w.

v1v2

vi-1 vi

vn-1 vn

..

..

..



Por hiptese, d(v1) + d(vn) n, ou seja existe um conjunto E com aomenos outras n 2 aretas incidentes em {v1, vn}.

Logo, existem vrtices vi e vi1 tais que vi adjacente a v1 e vi1 adjacente a vn. De fato, se todas as arestas de E incidem, digamos, emv1, teramos ao menos um par de arestas paralelas, contradizendo o fatode G ser simples. Similarmente se todas incidem em vn. Veja a figura.

v1v2

vi-1 vi

vn-1 vn

..

..

..

n novas arestas



v1v2

vi-1 vi

vn-1 vn

..

..

..

Mas neste caso, temos um circuito hamiltoniano:

v1 v2 vi1 vn vn1 vi+1 vi v1,

em contradio suposio de que G no hamiltoniano.

Teorema de Dirac (1952)Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos


Teorema 5. Se G um grafo simples com n 3 vrtices, e se

d(v) n

2

para cada vrtice v, ento G hamiltoniano.

Demonstrao. Temos que

d(v) + d(w) n

2+

2

2= n

para cada par de vrtices v e w (adjacentes ou no-adjacentes). Seguedo Teorema de Ore que G hamiltoniano.

ExerccioGrafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos


Verificar os dois teoremas atravs dos seguintes grafos:

Condio NecessriaGrafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos


Teorema 6. Se G(V,A) um grafo hamiltoniano, ento para todosubconjunto no-vazio, S V , o grafo G S possui no mximo |S|componentes.

Demonstrao. Seja C um ciclo hamiltoniano de G. Ao percorrer asarestas de C, quando passamos por um componente de G, ao deixar estecomponente temos, necessariamente, que passar por algum vrtice de S.

A cada passagem por um componente de G temos que usar um vrticediferente de S ao deixarmos o componente.

Consequentemente, a quantidade de vrtices de S deve ser maior ouigual ao nmero de componentes de G.

ExemplosGrafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos


O Problema do Caixeiro

Viajante


Colocao do ProblemaGrafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos


Um viajante necessita visitar um certo nmero de cidadesdurante uma viagem e retornar ao lugar de origem de talmaneira que cada cidade visitada exatamente uma vez e quea distncia total percorrida seja a menor possvel. Dada edistncia entre as cidades, que rota ele deve escolher?

Como resolver este problema?

Vamos representar o problema acima atravs de um grafo valorado. SejaV o conjunto de cidades, A o conjunto das estradas interligando ascidades e o valor de cada aresta como sendo a distncia entre asrespectivas cidades.



Vamos supor que o viajante deseja visitar 5 cidades cujas estradasexistentes entre cada par de cidade estejam representadas atravs doseguinte grafo:

Em princpio, este problema pode ser resolvido determinando-se todas asrotas possveis e escolhendo a que resultar na menor distncia percorrida.Neste exemplo, uma possvel rota dada por: {A,B,C,D,E,A} cujadistncia 5 + 2 + 4 + 3 + 4 = 18km.

A rota tima : {A,C,B,D,E,A} cuja distncia 14km.



Esta tcnica eficiente?

Considere que o problema que envolva 10 cidades.

O nmero mximo de possveis rotas seria de 9! = 362.880.

Uma mquina equipada com um programa que conseguisse examinar 1milho de rotas por segundo levaria 0, 36s para encontrar a melhor rota.

Se dobrssemos o nmero de cidades, teramos que examinar1, 22 1017 rotas (19!) e o mesmo programa levaria aproximadamente3.800 anos para encontrar a melhor rota!

ExercciosGrafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos


1. Quais dos grafos abaixo hamiltoniano e/ou Euleriano? Exiba umcircuito hamiltoniano e/ou trajeto euleriano em caso positivo.

2. D um exemplo de um grafo no hamiltoniano com n vrtices talque d(v) (n 1)/2.

3. D um exemplo de um grafo hamiltoniano que no satisfaa oTeorema de Dirac.

Digrafos Hamiltonianos


DefiniesGrafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos


Definio 7. Um digrafo D dito ser hamiltoniano se possuir umcircuito orientado que inclua todos os seus vrtices.

Um digrafo no-hamiltoniano dito ser semi-hamiltoniano se possuir umcaminho orientado que inclua todos os seus vrtices.

Pouco sabe-se sobre digragos hamiltonianos.

Muitos teoremas para grafos hamiltonianos no so generalizadosfacilmente para digrafos.

Teorema de Dirac (para digrafos)Grafos Hamiltonianos O Problema do Caixeiro Viajante Digrafos Hamiltonianos


Seja D um digrafo fortemente conexo com n vrtices. Se

ds(v) n

2e de(v)

n

2

para todo vrtice v de D, ento D hamiltoniano.

Notas de aula Teoria dos Grafos Prof. Maria do Socorro Rangel DMAp/UNESP

11 - rvores Vamos representar as situaes abaixo atravs de grafos. a)Jogo da velha b) rvore Genealgica x x x ... x x x ... o o o a) Vrtices: os estados do jogo arestas: existe uma aresta entre um estado do jogo e um estado que poder ser obtido atravs deste. b) vrtices: pessoas. arestas: relao de parentesco em primeiro grau (me (pai)- filho(a)). O que os grafos da situaes acima possuem em comum? Definio Uma rvore um grafo conexo e que no possui circuitos. Exemplos: a) b) E no caso de grafos orientados? Uma rvore orientada um digrafo conexo que no possui circuitos ou semi-circuitos.

rvore de 1

vrtice rvore de 2

vrtices rvore de 3

vrtices

a

b g h

c

i

d e f

rvores de 4

vrtices

rvore orientada

de 4 vrtices


11.1 - Propriedades de rvores Teorema 10.1 Um grafo G uma rvore se e somente existir um e apenas um caminho entre cada par de vrtices. Prova: G uma rvore ento existe apenas um caminho entre cada par de vrtices.

G uma rvore, ento por definio G conexo e sem circuitos. Como G conexo, ento existe um caminho entre cada par de vrtices. Precisamos mostrar que este caminho nico. Vamos supor que existam dois caminhos distintos entre um par de vrtices. Ora, se existem dois caminhos distintos entre um par de vrtices ento a unio destes caminhos contm um circuito. Mas por hiptese, o grafo no possui circuitos, portanto existe apenas um caminho entre cada par de vrtices.

Existe um e apenas um caminho entre cada par de vrtices ento G uma rvore. Como existe um caminho entre cada par de vrtice temos que G conexo. Vamos supor que

G contenha um circuito. A existncia de um circuito no grafo implica que existe pelo menos um par de vrtices a, b tais que existem dois caminhos distintos entre a e b. Mas por hiptese existe um e apenas um caminho entre cada par de vrtices e portanto o grafo no tem circuitos. Por definio um grafo conexo e sem circuitos uma rvore.

Outras caracterizaes de uma rvore podem ser resumidas no teorema abaixo. Teorema 10.2 -(Propriedades de rvores) Seja G(V,A) um grafo com n vrtices. As seguintes afirmativas so equivalentes: a) G uma rvore. b) G conexo e possui (n-1) arestas. c) G possui (n-1) arestas e no possui circuitos. d) Existe exatamente um caminho entre cada par de vrtices. e) G no contm circuitos, e para todo v,w V, a adio da aresta (v,w) produz no grafo

exatamente um circuito. Qualquer uma destas afirmativas podem ser usadas como definio de uma rvore. Prova: Para mostrar a equivalncia das afirmativas temos que mostrar que a) b), b)c), etc. Vamos ento comear mostrando que : a) ==> b: G uma rvore ento G conexo e possui (n-1) arestas.

Como por hiptese G uma rvore temos que G conexo. Precisamos mostrar apenas que G possui (n-1) arestas. Vamos mostrar usando induo matemtica sobre n. Vamos verificar o resultado para um valor particular de n. Por exemplo para n=1 e n=2. Para n=1, temos 0 arestas . Para n=2 temos 1 aresta. Vamos supor agora que o resultado vale para um grafo G com k-1 vrtices. Isto , G uma rvore ento G conexo e possui k-2 arestas. Vamos acrescentar uma nova aresta (v,w) a este grafo. Para manter o grafo conexo e sem circuitos um e apenas um dos vrtices (v,w) pode pertencer a G. Assim ao acrescentar a aresta (v,w) a G, precisamos acrescentar tambm um vrtice. Assim teremos um novo grafo G com k vrtices e k-1 arestas. A forma como G foi construdo garante que conexo e sem circuitos portanto temos que G'' uma rvore. Mostramos assim se G uma rvore ento G conexo com n-1 arestas.


11.2 - Razes e rvores Binrias Uma rvore na qual podemos distinguir um determinado vrtice, vrtice raiz, chamada de rvore enraizada. Por exemplo as rvores de 4 vrtices abaixo so enraizadas. Em geral, o vrtice raiz aparece naturalmente com a aplicao que o grafo representa. Uma rvore no

Documents

Apostila Teoria dos Grafos