Teoria de Grafos

Teoria de Grafos

DAC- Geografia e Macs

Índice

• Conclusão

• Algoritmo de Kruskal

• Comparação dos algoritmos

• Algoritmo do peso das arestas

• Algoritmo da cidade mais próxima

• Grafo ponderado

• Tabela de distâncias

• Problema tipo exame

• Caracterização de 5 pontos de interesse

• Introdução

Introdução

• Aplicação da teoria dos grafos á região agrária do Douro e do Minho
• Objetivo: analisar conexôes e distâncias entre diferentes pontos de interesse da regiâo

Caracterização de 5 pontos de interesse

Ponte da Barca

Terras de Bouro

Arco de Valdevez

Vila Verde

Amares

Problema Tipo Exame

Problema tipo Exame:

1- Para planear uma viagem, de ida e volta, de sua casa Amares (A) até Arcos de Valdevez (AV),o Osvaldo construiu o grafo apresentado na Figura 1. No grafo, os cinco vértices representam cinco locais: Amares (A), Terras de Bouro(T) e os outros três locais por onde pretende passar. As arestas representam os percursos mais curtos entre os nove locais. Nesse grafo, estão indicadas as distâncias que são do conhecimento do Osvaldo, sendo as restantes determinadas a partir da consulta do mapa, que não está à escala.

1.1 -

1.2 -

1.3 -

Figura 1

1.1- Resolução:

Algoritmo da cidade mais próxima

Tabela- Distâncias aproximadas em km, entre as localidades da região do Douro e Minho

a) Iniciando em Amares aplica o algoritmo:

A-VV (10km) VV-T (25km) T-P (15km) P-V (10km) V-A (35km)

Amares- Vila Verde- Terras de Bouro- Ponte da Barca- Arcos de Valdevez- Amares

1.2- Resolução:

Algoritmo do peso das arestas

Tabela- Distâncias aproximadas em km, entre as localidades da região do Douro e Minho

V-P : 10 VV-A : 10 P-T: 15 A-T: 20 V-T : 25 VV-T: 25 A-P: 30 P-VV: 35 A-V: 35 VV-V: 40

10+10+15+20+40=95 km

Problema Tipo Exame

Problema tipo Exame:

2- O Osvaldo quer planear uma rede de estradas que ligue as localidades de Amares (A), Arcos de Valdevez (V), Ponte da Barca (P), Terras de Bouro (T) e Vila Verde (VV).As distâncias entre as localidades estão representadas nas arestas do grafo seguinte.

2.1 -

1.2- Resolução:

1) Arestas ordenadas por peso (crescente):

2) Algoritmo de Kruskal:

1. A–P, 10 2. T–VV, 15 3. P–T, 20 4. V–VV, 25 5. A–T, 30 6. V–P, 30 7. P–VV, 30 8. A–VV, 35 9. A–V, 40 10. V–T, 45

A-P : 10 T-VV : 10 P-T : 20 V-VV: 25 A-T : 30 V-P: 30 P-VV: 30 A-VV: 35 A-V: 40 V-T: 40

10+15 +20+25= 78 km

Conclusão

Conclusão

• A teoria dos grafos revelou-se útil para estudar a região agrária do Douro e Minho.

• A caracterização dos cinco concelhos permitiu compreender a diversidade agrícola, económica e territorial da zona.

• O estudo das distâncias e dos algoritmos (Cidade Mais Próxima, Peso das Arestas e Kruskal) ajudou a explorar diferentes formas de organizar percursos e interpretar ligações entre pontos.

• Cada algoritmo apresentou vantagens e limitações, dependendo do objetivo — otimizar distâncias, analisar custos ou estruturar ligações.

• A combinação entre Matemática e Geografia mostrou como a teoria dos grafos pode ser aplicada de forma prática, ajudando a compreender o território e a resolver problemas reais.

Fim!!!

Obrigada pela vossa atenção!

1.1- Descobre o caminho mais curto usando o seguinte algoritmo:

1ºPasso: Seleciona-se o ponto de partida2ºPasso: Partindo do vértice inicial,ir para o vértice mais próximo(ou seja, seguir pela aresta de menor peso possível).3ºPasso: De cada vértice;ir para o vértice mais próximo escolhendo apenas vértices que ainda não tenham sido visitados.Continuar até que todos os vértices tenham sido visitados.4ºPasso: Do último vértice,regressar ao vértice de partida.

Vila Verde

• Concelho com forte atividade agrícola, baseada em explorações familiares e policultura
• Produção de milho, batata, hortícolas e vinha
• Pecuária e agroindústria com peso importante na economia local
• Reconhecido pela preservação das tradições rurais e pelo associativismo agrícola

Etapas do trabalho:

• Identificação dos pontos de interesse
• Tabela de distâncias entre locais
• Aplicação de algoritmos de grafos

Ponte da Barca

• Agricultura diversificada: vinha, milho, hortícolas e produção animal
• Uso de socalcos e técnicas tradicionais devido ao relevo acidentado
• Importante centro de comercialização agrícola, com feiras e mercados regulares que ligam produtores e consumidores

Terras de Bouro

• Locaziado na Serra do Gerês com agricultura de montanha;
• Pecuária extensiva (gado bovino e caprino) e cultivo de forragens;
• Agricultura de subsistência, associado ao turismo de natureza e ao Parque Nacional da Peneda-Gerês

Amares

• Agricultura de minifundio com diversidade de culturas
• Destaque para a vitultura e produção de Vinho Verde
• Cultivo de frutos regionais

Arcos de Valdevez

• Concelho com forte tradição agrícola e pecuária
• Destaca-se pela carne de qualidade e pela produção de vinho
• Paisagens rurais bem conservadas
• Crescente aposta na modernização e na agricultura biológica, valorizando produtos locais

1.2- )Descobre o caminho mais curto usando o seguinte algoritmo:

1ºPasso:Ordene as arestas por ordem crescente dos seus pesos 2ºPasso:Escolhe-se sucessivamente as arestas de menor peso que verifiquem as seguintes condições: a) Um vértice nunca poderá aparecer três vezes; b) nunca se fecha um circuito havendo vértices por visitar; c) pretende-se visitar uma e uma só vez todos os vértices; 3ºPasso:Ordena-se a solução conforme o vértice de partida escolhida

Algoritmo da cidade mais próxima

• Método da teoria dos grafos para encontrar um percurso eficiente entre vários pontos
• Partindo de um ponto inicial, escolhe-se sempre o local mais próximo ainda não visitado
• O processo repete-se até percorrer todos os pontos
• Resulta num percurso completo com tentativa de minimizar a distância total

Algoritmo do peso das arestas

• Método da teoria dos grafos que analisa as ligações considerando o peso de cada aresta
• Cada peso representa custo, distância ou outra medida relevante
• O algoritmo compara os pesos para identificar conexões mais “caras” ou “baratas”
• Permite organizar a rede e selecionar caminhos ou estruturas de forma eficiente
• Ajuda a compreender melhor as relações entre vértices segundo o peso das arestas

1.1- Descobre o caminho mais curto usando o seguinte algoritmo:

1ºPasso: Ordena todas as arestas por ordem crescente dos seus pesos.2ºPasso: Começa pela aresta de menor peso.3ºPasso: Seleciona sucessivamente as arestas com menor peso que não formem circuitos.4ºPasso: Termina quando todos os vértices estiverem ligados.

Algoritmo de Kruskal

• Usado para encontrar a Árvore Geradora Mínima de um grafo ponderado e conexo
• Seleciona as arestas em ordem crescente de peso
• Cada aresta escolhida não deve formar um circuito com as já selecionadas
• O processo continua até todos os vértices estarem ligados
• Resulta numa árvore com custo total mínimo

1.3- O Osvaldo diz que o primeiro algoritmo lhe permitirá fazer o circuito mais rápido.Diz se o Osvaldo tem ou não resultado.

• Peso das Arestas e Cidade Mais Próxima seguem caminhos diferentes
• Apesar das rotas distintas, a distância total é a mesma: 95 km