Algoritmo sui grafi
Ciao ragazzi, devo fare un esercizio sul diametro di un grafo. L'esercizio in pratica è questo:
Dato un generico grafo con diametro (distanza massima tra due nodi) D, viene data la possibilità di togliere uno degli archi presenti e di aggiungerne uno nuovo in modo da minimizzare la distanza massima fra due nodi, ovvero il massimo numero di archi necessari per "viaggiare" fra qualunque coppia di nodi.
Comunque il testo completo è questo https://www.dropbox.com/s/9d95njfcokx6yhs/traghetti.pdf (la parte riguardante i grafi che sono una linea l'ho già fatta).
Se qualcuno riuscisse a darmi una mano sarei molto grato!
Dato un generico grafo con diametro (distanza massima tra due nodi) D, viene data la possibilità di togliere uno degli archi presenti e di aggiungerne uno nuovo in modo da minimizzare la distanza massima fra due nodi, ovvero il massimo numero di archi necessari per "viaggiare" fra qualunque coppia di nodi.
Comunque il testo completo è questo https://www.dropbox.com/s/9d95njfcokx6yhs/traghetti.pdf (la parte riguardante i grafi che sono una linea l'ho già fatta).
Se qualcuno riuscisse a darmi una mano sarei molto grato!
Risposte
Earthsea 
Il tuo professore deve essere un appassionato di fantascienza.. A prima vista direi che l'obiettivo è quello di trovare l'arco che divide il grafo nei due sottografi di diametro minimo ottenibili in questo modo. Per poi collegare tra di loro i due nodi che stanno "al centro" di questi due sottografi (sono un po' arrugginito in teoria dei grafi e i termini non sono forse molto precisi ma spero che si sia capito).
Ho alcune idee ma ho bisogno di un po' di tempo per pensarci e verificare le mie idee.
Il tuo professore deve essere un appassionato di fantascienza.. A prima vista direi che l'obiettivo è quello di trovare l'arco che divide il grafo nei due sottografi di diametro minimo ottenibili in questo modo. Per poi collegare tra di loro i due nodi che stanno "al centro" di questi due sottografi (sono un po' arrugginito in teoria dei grafi e i termini non sono forse molto precisi ma spero che si sia capito). Ho alcune idee ma ho bisogno di un po' di tempo per pensarci e verificare le mie idee.
Questo problema mi suona molto molto familiare. E' di sicuro una specializzazione di un problema più famoso.
Il problama principale è sicuramente quel: "togliere uno degli archi presenti e di aggiungerne uno nuovo". Mi vengono in mente solo metodi iterativi che testano su ogni singolo arco, quindi di complessità non interessante.
Il problama principale è sicuramente quel: "togliere uno degli archi presenti e di aggiungerne uno nuovo". Mi vengono in mente solo metodi iterativi che testano su ogni singolo arco, quindi di complessità non interessante.
Ci sono alcune osservazioni semplici da fare:
1. Il grafo è aciclico.
2. L'eliminazione di ogni arco divide il grafo in due componenti connesse (ovviamente disgiunte).
3. L'arco da eliminare dovrà essere preso da un percorso di lunghezza massimale D.
4. L'arco da inserire dovrà collegare tra di loro due nodi, uno per componente connessa, scelti in modo che il massimo della distanza tra loro e tutti i nodi della componente connessa sia minimo.
5. La minima distanza sarà uguale al minimo tra questa lunghezza e la lunghezza del percorso più lungo del grafo escludendo il percorso scelto per togliere l'arco. Il caso peggiore si avrà con un grafo fatto a croce in cui ogni braccio ha la stessa distanza. Qualsiasi cosa si faccia non cambierà il risultato.
1. Il grafo è aciclico.
2. L'eliminazione di ogni arco divide il grafo in due componenti connesse (ovviamente disgiunte).
3. L'arco da eliminare dovrà essere preso da un percorso di lunghezza massimale D.
4. L'arco da inserire dovrà collegare tra di loro due nodi, uno per componente connessa, scelti in modo che il massimo della distanza tra loro e tutti i nodi della componente connessa sia minimo.
5. La minima distanza sarà uguale al minimo tra questa lunghezza e la lunghezza del percorso più lungo del grafo escludendo il percorso scelto per togliere l'arco. Il caso peggiore si avrà con un grafo fatto a croce in cui ogni braccio ha la stessa distanza. Qualsiasi cosa si faccia non cambierà il risultato.
Intanto grazie per le risposte ragazzi...Il professore mette giù così gli esercizi anche per farceli digerire meglio credo, è molto più gradevole da leggere un testo che parla di isole e traghetti piuttosto che uno su nodi e archi 
. Comunque, il nostro obbiettivo effettivamente è quello di ridurre al minimo la complessità, ma anche partire da una idea base iterativa e di complessità elevata non fa di certo male .
In ogni caso apatriarca inizierò seguendo i tuo consigli, quindi cominciando con il trovare il percorso con lunghezza massimale e "spezzare" il grafo in 2 sottografi, trovare i nodi "centrali" di questi due e infine unirli.
Se avrò bisogno di ulteriori aiuti tornerò a chiedere .
. Comunque, il nostro obbiettivo effettivamente è quello di ridurre al minimo la complessità, ma anche partire da una idea base iterativa e di complessità elevata non fa di certo male .In ogni caso apatriarca inizierò seguendo i tuo consigli, quindi cominciando con il trovare il percorso con lunghezza massimale e "spezzare" il grafo in 2 sottografi, trovare i nodi "centrali" di questi due e infine unirli.
Se avrò bisogno di ulteriori aiuti tornerò a chiedere
.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo