Grafo

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1027 palavras )
  • Download(s) : 0
  • Publicado : 19 de novembro de 2012
Ler documento completo
Amostra do texto
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 podeser 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/UFCGTeoria 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 umpasseio é 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,4, 3, 5, 4, 3, 5, v ?

Teoria dos Grafos

© Jorge Figueiredo, DSC/UFCG

Teoria dos Grafos

© Jorge Figueiredo, DSC/UFCG

1

Caminho (Path)
•• Um caminho ou caminho simples em um grafo é um passeio Um caminho ou caminho simples em um grafo é um passeio em que todos os seus vértices são distintos. em que todos os seus vértices são distintos.

Trilha (Trail), Circuito e Ciclo
•• Umatrilha ou trajeto em um grafo é um passeio em que Uma trilha ou trajeto em um grafo é um passeio em que todas as suas arestas são distintas. todas as suas arestas são distintas. •• Um trajeto fechado ou circuito em um grafo é um trajeto em Um trajeto fechado ou circuito em um grafo é um trajeto em que o vértice inicial e o vértice final são iguais. que o vértice inicial e o vértice final sãoiguais. •• Um cricuito em que todos os vértices são distintos (com Um cricuito em que todos os vértices são distintos (com exceção do primeiro e do último) é chamado de ciclo. exceção do primeiro e do último) é chamado de ciclo. •• Um grafo acíclico é aquele que não possui ciclos. Um grafo acíclico é aquele que não possui ciclos. •• Um triângulo é um ciclo de tamanho 3. Um triângulo é um ciclo detamanho 3.

1 u 4 3

2 v

5

O passeio u, 1, 4, 3, 5, 4, 3, 5, v não constitui um caminho.

Teoria dos Grafos

© Jorge Figueiredo, DSC/UFCG

Teoria dos Grafos

© Jorge Figueiredo, DSC/UFCG

Grafos Conectados (ou Conexos)
a

b

d

c

•Um grafo é conectado se e somente se existe um caminho •Um grafo é conectado se e somente se existe um caminho entre qualquer par de vértices dografo. entre qualquer par de vértices do grafo. •Um componente de um grafo é um subgrafo conectado •Um componente de um grafo é um subgrafo conectado maximal. maximal. •Um grafo com apenas um componente é um grafo conectado. •Um grafo com apenas um componente é um grafo conectado.

e

f

Forneça exemplos de: -Passeio que não é nem trilha nem caminho. -Passeio que é trilha e não é caminho....
tracking img