Πώς να ενώσεις τα χωριά με καθορισμένο αριθμό δρόμων;

[Angelos Karasavvidis]

Το παρακάτω πρόβλημα αποτέλεσε πρόβλημα που μας έθεσε ο καθηγητής μας στο πολυτεχνείο:

Έστω ότι το οδικό δίκτυο στη χώρα σας έχει καταστραφεί και υπάρχουν Ν χωριά. Επίσης έχουν επιζήσει Μ δρόμοι(διπλής κατεύθυνσης) οι οποίοι συνδέουν κάποια χωριά, όμως δεν συνδέονται όλα με όλα τα χωριά. Αυτά που συνδέονται μεταξύ τους, δημιουργούν μια ομάδα και χωριά από διαφορετικές ομάδες δεν συνδέονται. Με ένα νέο πρόγραμμα, λοιπόν, της κυβέρνησης αποφασίζεται να δημιουργηθούν Κ νέοι δρόμοι οι οποίοι θα έχουν ως σκοπό να ανασυγκροτηθεί το δίκτυο. Πώς θα μπορέσουμε να υπολογίσουμε τον ελάχιστο αριθμό ομάδων χωριών που θα έχουμε μετά την κατασκευή των Κ δρόμων; Ακολουθεί παράδειγμα:

Έστω ότι έχουμε Ν = 7 χωριά(το 1, 2, 3, 4, 5, 6, 7) και Μ = 2 δρόμους αρχικά, οι οποίοι συνδέουν τα χωριά 1-2 και 5-6, άρα τα χωριά 3,4,7 είναι εκτός ομάδας. Έστω ότι θα φτιαχτούν Κ = 2 νέοι δρόμοι. Αποφασίζεται ότι αυτοί οι δρόμοι θα συνδέσουν τα 3-4 και 3-7. Άρα τελικά θα έχουμε τις ομάδες {1,2}, {5,6}, {3,4,7}, δηλαδή τρεις, όσος είναι και ο ελάχιστος αριθμός ομάδων που μπορούν να φτιαχτούν με αυτά τα στοιχεία

[mick7]

Γεια σας. Νομίζω ότι είναι ένα πρόβλημα της θεωρίας γραφημάτων. Η μάλλον πρέπει να το μετατρέψεις σε τέτοιο πρόβλημα. Παρακάτω δίνω δυο λινκ σχετικά. Δεν έχει νόημα (νομίζω) να σου δώσει κάποιος την λύση χωρίς την κατανόηση της (πολύπλοκης) θεωρίας απο την πλευρά σου.

https://en.wikipedia.org/wiki/Travellin ... an_problem

https://en.wikipedia.org/wiki/Minimum_spanning_tree