EisatoponAI: Will Hunting και Θεωρία Γραφημάτων: Μπορείς να το Λύσεις;

🧠 Το Πρόβλημα του Will Hunting

(Mathematics Department, MIT)

Στην ταινία, ο καθηγητής Gerald Lambeau γράφει ένα πρόβλημα θεωρίας γραφημάτων στον πίνακα, για να προκαλέσει τους φοιτητές του. Ο Will το λύνει ανώνυμα.

✏️ Το πρόβλημα με απλά λόγια:

🔹 "Να βρείτε τον αριθμό των διαφορετικών δέντρων με 10 κόμβους."

❓ Τι σημαίνει αυτό;

Στη θεωρία γραφημάτων, ένα δέντρο είναι ένας συνδεδεμένος γράφος χωρίς κύκλους. Ο αριθμός των διαφορετικών μη κατευθυνόμενων, επισημασμένων δέντρων με $ $n$$ κόμβους δίνεται από τον τύπο του Cayley:

$T(n)=n^{n−2}$

✅ Επομένως, για $n = 10:$

T(10) = 10^{10-2} = 10^8 = \boxed{100,\!000,\!000}

📚 Πραγματικά Μαθηματικά Πίσω από την Ταινία:

Ο τύπος $T(n) = n^{n-2}$ είναι ένα από τα πιο διάσημα αποτελέσματα της θεωρίας γραφημάτων. Προτάθηκε από τον Arthur Cayley τον 19ο αιώνα. Χρησιμοποιείται για την καταμέτρηση των διαφορετικών τρόπων που μπορούν να συνδεθούν $n$ σημεία χωρίς να δημιουργηθούν κύκλοι.

💡

Quiz: "Πόσα διαφορετικά δέντρα υπάρχουν με 4, 5, 6 κόμβους;"
Challenge: "Μπορείς να σχεδιάσεις στο Geogebra ή Graph Editor όλα τα διαφορετικά δέντρα με 4 κόμβους;"