Grafo

Teoria dos Grafos

Exemplos de Aplicação de Grafos
•• Planejamento eficiente de roteamento de pacotes na Planejamento eficiente de roteamento de pacotes na Internet. Internet. •• Definir melhor rota de distribuição de correspondência nos Definir melhor rota de distribuição de correspondência nos postos de distribuição da ECT. postos de distribuição da ECT. •• Determinar se uma mensagem pode ser trocada por dois Determinar se uma mensagem pode ser trocada por dois computadores em uma rede (possivelmente usando links computadores em uma rede (possivelmente usando links intermediários) intermediários)

Caminhos e Conectividade de Grafos

Idéia básica: determinar alcançabilidade entre os vértices através de caminhamento em arestas.

Teoria dos Grafos

© Jorge Figueiredo, DSC/UFCG

Teoria dos Grafos

© Jorge Figueiredo, DSC/UFCG

Passeio (walk)
•• Um passeio em um grafo G= (V, E) é uma seqüência Um passeio em um grafo G= (V, E) é uma seqüência alternada de vértices e arestas que começa e termina com alternada de vértices e arestas que começa e termina com vértices. vértices. •• A seqüência v11, …, vkk ,, ∀ v11, …, vkk ∈ V, é um passeio de v11 a A seqüência v , …, v ∀ v , …, v ∈ V, é um passeio de v a vkk ,, se (vj,j, vj+1)) ∈ E, 1 ≤ jj ≤ |k – 1|. v se (v vj+1 ∈ E, 1 ≤ ≤ |k – 1|. •• Um passeio com k vértices possui k – 1 arestas. Um passeio com k vértices possui k – 1 arestas. – Neste caso teríamos as seguintes arestas: (v11, v22) ,, (v22, v33), – Neste caso teríamos as seguintes arestas: (v , v ) (v , v ), …, (vk-1,, vkk) …, (vk-1 v ) •• O comprimento de um passeio é o número de arestas do O comprimento de um passeio é o número de arestas do passeio. passeio.

Passeio (walk)

1 u 4 3

2 v

5

Teoria dos Grafos

© Jorge Figueiredo, DSC/UFCG

Teoria dos Grafos

© Jorge Figueiredo, DSC/UFCG

Passeio (walk)

Passeio (walk)

1 u 4 3

2 v u 5

1 3 4

2 v

5

Passeio: a seqüência u, 1, 4, 5, v

O que dizer da seqüência u, 1,