Aula de redes 2

1Aula 2 Introduo a Teoria dos Grafos

BC0506 - Comunicao e Redes

David Correa Martins [email protected]

2Aula passada

Sistema complexo.Uma representao atravs de uma rede.Em matemtica, uma rede = grafo.

3Roteiro da aula

Histrico- O problema das Pontes de Knigsberg.

Grafos- Definies e Propriedades - Exemplos

Representao de grafos- Matriz e lista de adjacncias

Atividade prtica

4I. O problema das Pontes de Knigsberg

5As 7 Pontes de Knigsberg

Cidade de Knigsberg(na antiga Prssia, parte do antigo imprio Alemo)Ficava em ambos os lados do Rio Pregel.Tinha 2 ilhas centrais, com as reas conectadas por 7 pontes.


Problema:Ser que existe um caminho que passe por todas as pontes, visitando cada ponte uma nica vez?

Exerccio: Encontre uma soluo para este problema


Um caminho uma sequncia de regies visitadas.Para passar de uma regio para outra necessrio usar uma ponte.

Exemplo: um caminho,mas no um caminho.

2

1

3

4


Problema:Existe um caminho que pase por todas as pontes, mas cada ponte visitada uma nica vez?

Exemplo: um caminho que visita algumas pontes, uma nica vez, mas no todas.

2

1

3

4


Em 1735, Euler mostrou que no existe uma soluo para o problema.

A demonstrao foi baseada em grafos.

22

1

3

4 1 4

3

10

Grafos

Chamamos a estrutura matemtica resultante de grafo. Cada aresta conecta um par de vrtices.Existem diferentes maneiras de desenhar um grafo:- Diferentes desenhos influenciam apenas na visualizao.- Diferentes desenhos no alteram as propriedades matemticas do grafo.

11

As 7 Pontes de Knigsberg

Diferentes desenhos.

21 43

2

1 4

3

21

4

3

12


Se uma pessoa entra em um pedao de terra e sai dele, preciso que o vrtice correspondente tenha um nmero par de arestas.

Com exceo dos vrtices onde a caminhada comea e termina.

Olhando o grafo ao lado, porque impossvel encontrar um caminho que cruze cada ponteuma nica vez?

2

1 4

3

13


Exerccio: Tente resolver o problemade 2 modos:

(a) Construndo uma nova ponte.(b) Derrubando uma ponte existente.

2

1 4

3

2

1 4

3

2

1 4

3

2

1 4

3

(a) (b) (b)

14

Caminho Euleriano

Euler demonstrou que, para que exista um caminho que percorra todos os vrtices passando por cada aresta uma nica vez: necessrio que ou 0 ou 2 dos vrtices tenham um nmero impar de arestas.

Um Caminho Euleriano um caminho em um grafo que visita uma aresta apenas uma vez.

E assim comeou o desenvolvimento da Teoria dos Grafos.

15

Circuito Euleriano

Um Circuito Euleriano um caminho Euleriano onde tanto o vrtice de origem como o de destino o mesmo.

Neste caso, preciso que todos os vrtices do grafo tenham um nmero par de arestas.

Exerccio: Inclua um novo vrtice no problema das 7 pontes de modo a formar um Circuito Euleriano.

2

1 4

3

2

1 4

3

5

Circuito:

16

Circuito Euleriano




2

1 4

3

2

1 4

3

5

Circuito:

17

Circuito Euleriano




2

1 4

3

2

1 4

3

5

Circuito:

18

Circuito Euleriano




2

1 4

3

2

1 4

3

5

Circuito:

19

Circuito Euleriano




2

1 4

3

2

1 4

3

5

Circuito:

20

Circuito Euleriano




2

1 4

3

2

1 4

3

5

Circuito:

21

Circuito Euleriano




2

1 4

3

2

1 4

3

5

Circuito:

22

Circuito Euleriano




2

1 4

3

2

1 4

3

5

Circuito:

23

Circuito Euleriano




2

1 4

3

2

1 4

3

5

Circuito:

24

Circuito Euleriano




2

1 4

3

2

1 4

3

5

Circuito:

25

Circuito Euleriano




2

1 4

3

2

1 4

3

5

Circuito:

26

Circuito Euleriano




2

1 4

3

2

1 4

3

5

Circuito:

27

II. Grafos:Definies, Propriedade e Exemplos

28

Definies

Podemos definir um grafo por um par ordenado:G = (V,A)

onde:V um conjunto de vrtices, e A um conjunto de arestas.

29

Definies

Podemos definir um grafo por um par ordenado:G = (V,A)

onde:V um conjunto de vrtices, e A um conjunto de arestas.

2

1 3

4

5

6

7

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

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

30

Definies

Um caminho do vrtice s ao vrtice t uma sequncia de vrtices , onde cada par de vrtices consecutivos conectado por uma aresta.

Dizemos que o caminho comea em s e termina em t.

2

1 3

4

5

6

7

Exemplo:

um caminho.

no um caminho.

31

Definies

O comprimento de um caminho o total de arestas usadas no caminho.

2

1 3

4

5

6

7

Exemplo:

O caminho tem um comprimento de 4.

32

Definies

No exemplo temos o tipo mais simples de grafo:No orientado.No possui mltiplas arestas nem loops.

2

1 3

4

5

6

7 Exemplo de caminhos:

33

Definies

Grafo simples:no-direcionado, no-ponderado

2

1 3

2

1 3

2

1 3

25

1

2

1 3

Multi-grafo(pseudo-grafo)

Grafo direcionado (orientado)

Grafo ponderado

34

Definies

Grafo no-direcionado

2

1 3

4

5

6

7

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

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

Pares no ordenados

35

Definies

Grafo direcionado

2

54

3

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

A = { {1,2}, {2,3}, {2,4}, {3,4}, {3,5}, {4,2} }

Pares ordenados

36

Grafos: Propriedades

A Ordem de um grafo o nmero total de vrtices.

Exemplo:

O grafo possui 7 vrtices, neste caso, dizemos que ele tem ordem 7.

2

1 3

4

5

6

7

37


O Tamanho de um grafo o nmero total de arestas.

Exemplo:

O grafo tem tamanho 9.2

1 3

4

5

6

7

38


O Dimetro o maior dosmenores caminhos entrecada par de vrtices.

2

1 3

4

5

6

7

39



Caminhos entre os vrtices:

1-2: 1-3: 1-4: 1-5: 1-6: 1-7: 2-3: 2-4: 2-5: 2-6: 2-7:

2

1 3

4

5

6

7 3-4: 3-5: 3-6: 3-7: 4-5: 4-6: 4-7: 5-6: 5-7: 6-7:

40




1-2: 1-3: 1-4: 1-5: 1-6: 1-7: 2-3: 2-4: 2-5: 2-6: 2-7:

2

1 3

4

5

6

7 3-4: 3-5: 3-6: 3-7: 4-5: 4-6: 4-7: 5-6: 5-7: 6-7:

41




1-2: 1-3: 1-4: 1-5: 1-6: 1-7: 2-3: 2-4: 2-5: 2-6: 2-7:

2

1 3

4

5

6

7 3-4: 3-5: 3-6: 3-7: 4-5: 4-6: 4-7: 5-6: 5-7: 6-7: Diametro = 3

42


Exerccio: Qual a ordem, tamanho e dimetro dos grafos abaixo?

1

2

3

4

5

66

5

4

3

2

1

7

8

43

Grafos

Um grafo conexo se existe um caminho entre quaisquerpares de vrtices.

2

1 3

4

5

6

7

Conexo

2

1

4

5

6

7

No-conexo

44


A Conectividade dos Vrtices o nmero mnimo de vrtices cuja remoo desconecta o grafo.

2

1 3

4

5

6

7

Conexo

2

1

4

5

6

7

No-conexo

Conectividade dos Vrtices = 1

3

45


A Conectividade das Arestas o nmero mnimo de arestas cuja remoo desconecta o grafo.

2

1 3

4

5

6

7

Conexo No-conexo

Conectividade das Arestas = 1

2

1 3

4

5

6

7

46


Exerccio: Quais so as conectividades dos vrtices e das arestas dos grafos abaixo?

1

2

3

4

5

66

5

4

3

2

1

7

8

47

Jogo de Xadrez 3x3

Grafos podem ser utilizados para representar diversos problemas:

Em um tabuleiro 3x3, deseja-se mapeartodos os movimentos que podem serrealizados por um bispo que se movenas casas brancas.

O grafo direita representa osmovimentos desse bispo.

48

Jogo de Xadrez 3x3

Exerccio:Desenhe um grafo que represente todos os movimentos da torre.

49

Jogo de Xadrez 3x3

Exerccio:Desenhe um grafo que represente todos os movimentos da torre.

50

Ciclo (ou circuito)

Um ciclo (ou circuito) de comprimento r um caminho constitudo por r + 1 vrtices, onde o primeiro vrtice igual ao ltimo

Note que a escolha do vrtice inicial em um ciclo arbitrria.

2

1 3

4

5

6

7

Esse grafo tem quantos ciclos?

51

Ciclo

Um ciclo de comprimento r um caminho constitudo por r + 1 vrtices, onde o primeiro vrtice igual ao ltimo

A escolha do vrtice inicial em um ciclo arbitrria.

2

1 3

4

5

6

7

Esse grafo tem quantos ciclos?

3 ciclos de tamanho 32 ciclos de tamanho 41 ciclo de tamanho 5

52

Isomorfismo em grafos

Dois grafos G e H so isomorfos se existe uma funo bijetoraf : V(G) V(H) de tal forma que quaisquer dois vrtices u e v de G so adjacentes em G se e somente se f(u) e f(v) so adjacentes em H.

f(a) = 1f(b) = 6f(c) = 8f(d) = 3f(g) = 5f(h) = 2f(i) = 4f(j) = 7

53

III. Representao de grafos

54

Representao de grafos

Duas maneiras populares de representar um grafo:(A) Matriz de adjacncia.(B) Listas de adjacncia.

G = (V,A)

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

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

2

1 3

4

5

6

7

55


(A) Matriz de adjacncia.

2

1 3

4

5

6

7 1 1 11 1 1 11 1 1 1 11 1

1 11

1

1 2 3 4 5 6 71234567

56



2

1 3

4

5

6

7

1 2 3 4 5 6 71234567

0 1 1 1 0 0 01 0 1 0 1 0 11 1 0 1 1 1 01 0 1 0 0 0 00 1 1 0 0 0 00 0 1 0 0 0 00 1 0 0 0 0 0

57


(A) Matriz de adjacncia.O grafo representado poruma matriz onde cadaelementos (x,y) recebe ovalor 1 se houver umaconexo entre os ns x e y,e 0 caso contrrio.

Basta 1 bit para representarcada aresta.Se houveram poucas arestasa matriz ser esparsa.

1 2 3 4 5 6 71234567

0 1 1 1 0 0 01 0 1 0 1 0 11 1 0 1 1 1 01 0 1 0 0 0 00 1 1 0 0 0 00 0 1 0 0 0 00 1 0 0 0 0 0

58



2

1 3

4

5

6

7

1 2 3 4 5 6 71234567

0 0 0 1 0 0 11 0 0 0 0 0 01 0 0 0 0 1 00 0 1 0 0 0 00 1 0 0 0 0 00 0 0 0 0 1 00 1 0 0 0 0 0

Grafo direcionado

59


(B) Lista de adjacncia.

2

1 3

4

5

6

7 1: 4, 72: 13: 1, 64: 35: 26: 67: 2

Grafo direcionado

60


Matriz de adjacncia: Grafo de tamanho 33.

61


Matriz de adjacncia: Grafo de tamanho 33.

62

Resumo

At aqui vimos:Tipos de grafos.Ordem = total de vrtices.Tamanho = total de arestas.Conectividade dos vrtices de das arestas.

Algumas definies importantes:Caminho.Comprimento do caminho.ConexidadeIsomorfismo


63

IV. Atividade Prtica

64

Atividade Prtica

Questo 0: Desenhe um grafo que represente todos os movimentos do cavalo em um tabuleiro 3x3 e 5x5.

65

Atividade Prtica

Questo 0: Desenhe um grafo que represente todos os movimentos do cavalo.

66

Atividade Prtica


67

Atividade Prtica


Tipo: grafo direcionadoOrdem: 8Tamanho: 16

68

Atividade Prtica

Questo 1: Calcule as seguintes informaes do grafo:

Ordem.Tamanho.DimetroConectividade de vrticesConectividade de arestas.Representao por listade adjacncias.Existe um caminhoEuleriano?Se sim, indique o caminho.

2

1 5

4

6

8

3

7

69

Atividade Prtica

Ordem = 8.Tamanho = 15.Dimetro = 3.

2

1 5

4

6

8

3

7

70

Atividade Prtica

Conectividade de vrtices = 2

Conectividade de vrtices o nmero mnimo de vrtices cuja remoo desconecta o grafo.

2

1 5

4

6

8

3

7

71

Atividade Prtica

Em um grafo no-direcionado, a conectividade de arestas e de vrtices sempre mantem os mesmos valores?

Conectividade de vrtices = 1 Conectividade de arestas = 1

72

Atividade Prtica

Conectividade de arestas = 2

2

1 5

4

6

8

3

7

Conectividade de arestas o nmero mnimo de arestas cuja remoo desconecta o grafo.

73

Atividade Prtica

Conectividade de vrtices = ? Conectividade de arestas = ?

Em um grafo no-direcionado, a conectividade de arestas e de vrtices sempre mantm os mesmos valores?

74

Atividade Prtica

Represente o grafo abaixo por uma lista de adjacncias

2

1 5

4

6

8

3

7

75

Atividade Prtica

Represente o grafo abaixo por uma lista de adjacncias

2

1 5

4

6

8

3

7

1: 2,4,52: 1,3,5,63: 2,64: 1,5,7,75: 1,2,4,6,7,86: 2,3,5,87: 4,4,5,88: 5,6,7

76

Atividade Prtica

Existe um caminhoEuleriano?

Sim:

2

1 5

4

6

8

3

7

77

Atividade Prtica

O que um caminho Hamiltoniano?O que um ciclo/circuito Hamiltoniano?

2

1 5

4

6

8

3

7

Caminho Euleriano Ciclo Hamiltoniano

78

Atividade Prtica

Questo 2: Um grafo planar se ele pode ser desenhado sem cruzar arestas

Verifique se um cubo planar

79

Atividade Prtica

80

Atividade prtica

3. (para casa) O grafo dos estados do Brasil denido assim: cada vrtice um dos estados da Repblica Federativa do Brasil; dois estados so adjacentes se tm uma fronteira comum. Faa um desenho do grafo.

Quantos vrtices tem o grafo?Quantas arestas?

4. O grafo das palavras definido assim: cada vrtices uma palavra da lngua portuguesa e duas palavras so adjacentes se diferem em exatamente uma posio. Por exemplo, rato e ralo so adjacentes, enquanto ralo e rota no so. Faa uma figura da parte do grafo definida pelas palavras abaixo:

caiadocavadocavalogirafagiravaraloramorataratoremoretaretorotavaiadovaradoviradaviradovirava

Escreva a matriz de adjacncia do grafo.

81

Atividade para casa

5. verdade que o grafo do cavalo 3-por-3 um circuito (ciclo)?

6. O grafo do bispo t-por-t planar? (para t um nmero inteiro t=3, 5, 7)

7. O grafo da dama t-por-t planar? (para t um nmero inteiro t=3, 5, 7)

8. O grafo de Heawood tem conjunto de vrtices {0, 1, 2, . . . , 13}.Cada vrtice i vizinho de (i + 1) mod 14 e de (i + 13) mod 14. Alm disso, cada i vizinho de um terceiro vrtice, que depende da paridade de i: se i par ento ele vizinho de (i + 5) mod 14 e se i mpar ento ele vizinho de (i + 9) mod 14. Faa uma figura do grafo.

Nota: A expresso i mod j denota o resto da diviso de i por j.

First Slide ExampleSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Slide 80Slide 81

Documents

Aula de redes 2