Teoria de Grafos - Outras Definições

Grafo Direcionado G é um par (V,E), onde V é um conjunto finito e E é uma relação binária em V.
Grafo Não Direcionado G = (V,E) é um par onde o conjunto de arestas E consiste em pares de vértices não orientados. A aresta (vi,vj) e (vj,vi) são consideradas a mesma aresta.


Outras definições:

• Loop: uma aresta associada ao par de vértices (vi,vi)
• Arestas paralelas: quando mais de uma aresta está associada ao mesmo par de vértices
• Grafo simples: um grafo que não possui loops e nem arestas paralelas
• Dois vértices são ditos adjacentes se eles são pontos finais de uma mesma aresta
• Duas arestas não paralelas são adjacentes se elas são incidentes a um vértice comum
• Quando um vértice vi é o vértice final de alguma aresta ej, vi e ej são incidentes

O número de arestas incidentes a um vértice vi é chamado de grau, d(vi), do vértice i
A soma dos graus de todos os vértices de um grafo G é duas vezes o número de arestas de G.



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

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

Grafos: introdução