Το Διάσημο Άλυτο Γρίφο: Γιατί Δεν Λύνεται το Πρόβλημα των Τριών Σπιτιών;

🔺 Το πρόβλημα:

Θέλουμε να συνδέσουμε τρία σπίτια με τρεις πηγές (ή υπηρεσίες) — δηλαδή να συνδέσουμε κάθε σπίτι με κάθε πηγή — χωρίς γραμμές που τέμνονται, σε επίπεδο χαρτί (δισδιάστατο χώρο), χωρίς τρίτες διαστάσεις, υπόγεια ή υπέργεια περάσματα.

---

📐 Το μαθηματικό ισοδύναμο: Το πλήρες διμερές γράφημα K₃,₃

Στην θεωρία γραφημάτων, το πρόβλημα μοντελοποιείται ως το γράφημα K₃,₃, ένα πλήρες διμερές γράφημα, όπου:

• Το ένα σύνολο έχει 3 κόμβους (τα σπίτια)

• Το άλλο σύνολο έχει 3 κόμβους (οι υπηρεσίες)

• Κάθε κόμβος στο ένα σύνολο συνδέεται με κάθε κόμβο του άλλου.

Το K₃,₃ έχει 9 ακμές και 6 κορυφές.

---

❌ Γιατί δεν λύνεται στο επίπεδο;

Το γράφημα K₃,₃ είναι μη επίπεδο γράφημα (non-planar graph), δηλαδή δεν μπορεί να σχεδιαστεί σε επίπεδο χωρίς να τέμνονται οι ακμές.

Αυτό αποδεικνύεται με δύο βασικά θεωρήματα:

---

1. Θεώρημα του Κουρατόφσκι (Kuratowski's Theorem):

Ένα γράφημα είναι μη επίπεδο αν περιέχει ως υπογράφημα είτε το K₃,₃ είτε το K₅ (πλήρες γράφημα 5 κόμβων).

Το πρόβλημα μας είναι το ίδιο το K₃,₃, άρα δεν είναι επίπεδο.

---

2. Τύπος του Όιλερ (Euler's Formula):

Για συνδεδεμένο επίπεδο γράφημα ισχύει:

V − E + F = 2

• V = 6 κορυφές

• E = 9 ακμές
  Άρα 6 − 9 + F = 2 → F = 5

Ωστόσο, αν μελετήσουμε τους ελάχιστους κύκλους (faces) που μπορούν να δημιουργηθούν από τις ακμές, βλέπουμε ότι για 9 ακμές και 6 κορυφές δεν μπορούμε να δημιουργήσουμε 5 περιοχές χωρίς να έχουμε διασταυρώσεις. Ο συνδυασμός αριθμού κορυφών/ακμών παραβιάζει τους όρους σχεδίασης χωρίς τέμνουσες.

---

🌀 Πώς μπορεί να λυθεί;

Αν περάσουμε σε άλλες τοπολογικές επιφάνειες, τότε η λύση γίνεται δυνατή.

✔️ Π.χ.:

• Σε τόρο (δλδ. επιφάνεια ντόνατ): το K₃,₃ μπορεί να σχεδιαστεί χωρίς τέμνουσες.

• Σε ταινία Möbius ή άλλες μη επίπεδες επιφάνειες: υπάρχουν τρόποι τοποθέτησης χωρίς διασταύρωση.

Άρα, το πρόβλημα δεν είναι άλυτο — είναι άλυτο μόνο στο επίπεδο.

---

🔍 Συνοπτική απάντηση στην ερώτηση:

Γιατί δεν έχουμε καταφέρει να λύσουμε το πρόβλημα των τριών σπιτιών, των τριών πηγαδιών εδώ και χρόνια;

Επειδή δεν λύνεται σε επίπεδο δύο διαστάσεων. Το αντίστοιχο γράφημα (K₃,₃) είναι μη επίπεδο και έχει αποδειχτεί μαθηματικά ότι οποιαδήποτε απόπειρα να σχεδιαστεί χωρίς διασταυρώσεις στο επίπεδο είναι αδύνατη. Η μόνη λύση βρίσκεται σε πιο σύνθετες τοπολογικές επιφάνειες, όπως ο τόρος.