Il MAR non coincide sempre con l'albero dei cammini minimi
Ciao a tutti, sulle slide del corso di Algoritmi c'è scritto che il minimo albero ricoprente (MAR) di un grafo non coincide sempre con l'albero dei cammini minimi. E per provarlo consiglia di trovare appunto un grafo che dimostri ciò.
Qualcuno può aiutarmi a trovare questo grafo?
Grazie
Qualcuno può aiutarmi a trovare questo grafo?
Grazie
Risposte
Ciao stefano86 
Ti propongo di seguito un esempio tra i tanti che si possono trovare. Di seguito ti descrivo formalmente come è fatto il grafo. Successivamente puoi applicare gli algoritmi di Prim per il MAR (o MST per dirla all'inglese) e di Dijkstra per i cammini minimi e notare che gli alberi ottenuti sono differenti. Ovviamente al posto dell'algoritmo di Prim va benissimo anche quello di Kruskal. Abbiamo:
$$
V = \{a, b, c, d, e\}\\
E = \{(a, b), (a, c), (a, d), (b, c), (b, d), (b, e), (c, d), (c, e)\}\\
w: E \times E \rightarrow \mathbb{N}\\
w(a, b) = 3, w(a, c) = 1, w(a, d) = 2, w(b, c) = 4, w(b, d) = 1, w(b, e) = 8, w(c, d) = 1, w(c, e) = 16
$$
Ti propongo di seguito un esempio tra i tanti che si possono trovare. Di seguito ti descrivo formalmente come è fatto il grafo. Successivamente puoi applicare gli algoritmi di Prim per il MAR (o MST per dirla all'inglese) e di Dijkstra per i cammini minimi e notare che gli alberi ottenuti sono differenti. Ovviamente al posto dell'algoritmo di Prim va benissimo anche quello di Kruskal. Abbiamo:
$$
V = \{a, b, c, d, e\}\\
E = \{(a, b), (a, c), (a, d), (b, c), (b, d), (b, e), (c, d), (c, e)\}\\
w: E \times E \rightarrow \mathbb{N}\\
w(a, b) = 3, w(a, c) = 1, w(a, d) = 2, w(b, c) = 4, w(b, d) = 1, w(b, e) = 8, w(c, d) = 1, w(c, e) = 16
$$
Grazie, appena ho un pò di tempo lo faccio. Grazie mille!
Di nulla, fammi sapere se hai ancora dubbi.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo