Μια τετράγωνη περιοχή έχει μία πόλη σε κάθε γωνία. Πρέπει να κατασκευαστεί ένα δίκτυο δρόμων που να συνδέει και τις τέσσερις πόλεις, ελαχιστοποιώντας το συνολικό μήκος των δρόμων.
Ένα πιθανό σχέδιο είναι το σχήμα Χ (διαγώνιες συνδέσεις), αλλά υπάρχει πιο αποδοτική λύση. Αν η πλευρά του τετραγώνου είναι $200$ χιλιόμετρα, ποιο είναι το ελάχιστο δυνατό μήκος των δρόμων;
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου