Introdução à Teoria dos Grafos - Atividade 3

Prévia do material em texto

Os grafos são ferramentas matemáticas que possibilitam propor soluções para diversos problemas, dessa forma, são comumente utilizadas na busca de soluções em diversos segmentos. Uma indústria de insumos para produtos farmacêuticos faz entregas em uma determinada região do país, e devido ao baixo tempo que esses produtos químicos podem permanecer nas condições de transporte no caminhão. São necessários alguns planejamentos de qual o melhor caminho a seguir. O trajeto é representado pela Tabela 1.   
	 
	AAA
	BBB
	CCC
	DDD
	EEE
	FFF
	GGG
	HHH
	III
	JJJ
	AAA
	 
	20
	20
	38
	39
	46
	 
	 
	 
	 
	BBB
	20
	 
	27
	44
	 
	 
	 
	 
	 
	 
	CCC
	20
	27
	 
	45
	 
	 
	 
	 
	 
	32
	DDD
	38
	44
	45
	 
	21
	20
	26
	 
	 
	 
	EEE
	39
	 
	 
	 
	 
	 
	 
	 
	 
	 
	FFF
	46
	 
	21
	 
	 
	 
	 
	17
	 
	 
	GGG
	 
	 
	 
	20
	 
	 
	 
	 
	 
	17
	HHH
	 
	 
	 
	26
	 
	 
	 
	 
	36
	 
	III
	 
	 
	 
	 
	 
	17
	 
	36
	 
	 
	JJJ
	 
	 
	32
	 
	 
	 
	17
	 
	 
	 
Tabela 01 - Rotas de Entrega
Fonte: Elaborada pelo autor.
 
Porém, para que não ocorra aumento no tempo de entrega, é necessário desenvolver um grafo planar, com os seus respectivos custos, de forma que se encontre o menor trajeto entre as cidades AAA e FFF. 
Caro(a) estudante, considerando o problema apresentado, para buscar a solução é necessário fazer o grafo planar, e analisar o menor custo de deslocamento para minimizar o tempo de entrega dos insumos. Sendo assim, haveria uma forma de propor uma solução do problema apresentado, com a utilização de alguma técnica encontrada na teoria dos grafos?
Como proposto no exercício, foi construído um grafo planar com as informações da tabela supracitada. Após uma rápida visualização na mesma é inconfundível que o caminho mais rápido de AAA até FFF é o caminho direto, sem passar por nenhuma outra cidade.
Abaixo está o grafo construído a partir da ferramenta de visualização online graphonline.ru/pt/#