Teoria de Grafos - Conceitos Básicos

Definição

• Grafo é uma coleção de vértices e arestas
• Vértice é um objeto simples que pode ter nomes e outros atributos
• Aresta é uma conexão entre dois vértices

Exemplo:
Dados os conjuntos: A={1,2,3,4} B={2,3,6} C={7,10} D={7,8,9} E={1,3} F={}
Modelagem:
Vértices = conjuntos
Arestas = conjuntos com interseção não vazia

Aplicações: As Pontes de Königsberg No século XVIII havia na cidade de Königsberg um conjunto de sete pontes que cruzavam o rio Pregel . Elas conectavam duas ilhas entre si e as ilhas com as margens.



Por muito tempo os habitantes daquela cidade perguntavam-se se era possível cruzar as sete pontes em uma caminhada contínua sem passar duas vezes por qualquer uma delas.

Aplicações: Problema do Desenho da Casa

No desenho abaixo, uma criança diz ter posto a ponta do lápis em uma das bolinhas e com movimentos contínuos (sem levantar e sem retroceder o lápis) traçou as linhas que formam o desenho da casa, traçando cada linha uma única vez.
A mãe da criança acha que ela trapaceou, pois a mãe não foi capaz de achar uma seqüência que pudesse produzir tal resultado. Você concorda com a mãe?


Aplicações: O Problema das três casas e três serviços

Suponha três casas e três serviços:
É possível conectar cada serviço a cada uma das três casas sem que haja cruzamento de tubulações?

Aplicações: Problema do caminho de custo mínimo

De forma a reduzir seus custos operacionais, uma empresa de transporte de cargas deseja oferecer aos motoristas de sua frota um mecanismo que os auxilie a selecionar o caminho de menor custo entre quaisquer duas cidades por ela servidas. Como realizar esta tarefa?



Aplicações: Problema do Caixeiro Viajante

Suponha que a área de venda de um caixeiro viajante inclua várias cidades, muitas das quais, aos pares, estão conectadas por rodovias. O trabalho do caixeiro requer que ele visite cada cidade pessoalmente. Sob que condições seria possível estabelecer uma viagem circular (que o leve ao ponto de partida) de forma a que ele visite cada cidade exatamente uma vez?

Referências: Material dos professores Max do Val Machado e Raquel Mini