Μια εταιρία παροχής υπηρεσιών διαδικτύου (internet service provider - ISP) θέλει να δημιουργήσει ένα νέο δίκτυο οπτικής ίνας.
Υπάρχουν επτά πόλεις που θα πρέπει να συνδεθούν, έτσι ώστε κάθε πόλη να μπορεί να στέλνει και να λαμβάνει μηνύματα από και προς οποιαδήποτε άλλη πόλη.
Η εταιρία θα πρέπει να πληρώσει για τη δημιουργία των συνδέσεων μεταξύ των πόλεων. Το αντίστοιχο κόστος φαίνεται πάνω στην κάθε γραμμή που συνδέει τις πόλεις στο παρακάτω διάγραμμα.
Εργασία:
Επιλέξτε τις συνδέσεις που θα πρέπει να δημιουργηθούν ώστε οι πόλεις να συνδεθούν με το μικρότερο δυνατό κόστος.