Τα μονοπατια

[nonlinear]

Οι παρακατω χαρτες δειχνουν δυο οδικα δικτυα το πρωτο συνδεει 10 πολεις και το δευτερο 14 πολεις.Να βρειτε μια διαδρομη η οποια περναει απο καθε πολη ακριβως μια φορα.

[mathxl]

Για το τρίγωνο..
Ξεκινάμε από την πάνω κορυφή και κινούμαστε κατά την φορά των δεικτών του ρολογιού διαγράφοντας την περίμετρο του μέχρι το μέσο της αριστερής του πλευράς. Εκεί πίνουμε ένα αναψθκτικό γιατί διψάσαμε και συνεχίζουμε κινο΄΄υμενοι κατά μήκος του τμήματος που ενώνει τα μέσα των πλευρών (αριστερή και δεξιά του μεγάλου τριγώνου). έπειτα μεταβαίνουμε στο μέσο της δεξιάς πλευράς του τριγώνου που έχει κορυφές τα μέσα των πλευρών του μεγάλου τριγώνου και καταλήγουμε στο μέσο της αριστερής πλευράς του ίδιου τριγώνου. Φινίτο λα μούζικα πασάτο λα φιέστα

[Demetres]

Μάκη, κάτι δεν καταλαβαίνω στην εξήγησή σου. Εγώ νομίζω πως τουλάχιστον για τον πρώτο χάρτη τέτοια διαδρομή δεν υπάρχει.

[mathxl]

Μάκη ο Δημήτρης έχει δίκιο διότι περνάς από το μέσο της δεξιάς πλευράς δις! Αχ αχ...Θόδωρε...

[Νασιούλας Αντώνης]

Θεωρώ ότι δεν υπάρχει τέτοιος δρόμος για καμία από τις δυο εικόνες.
Κάθε πόλη/τελεία/κόμβος συνδέεται με κάθε άλλο κόμβο με ένα μόνο δρόμο. Άρα μια διαδρομή που θα περνάει μόνο μια φορά από κάθε κόμβο θα περνάει μόνο μια φορά και από κάθε δρόμο. Για να συμβεί αυτό πρέπει ο αριθμός των κόμβων που προσεγγίζονται κατά περιττό αριθμό δρόμων να είναι ακριβώς 0 ή 2. Και στις δυο περιπτώσεις όμως υπάρχουν περισσότεροι από δυο κόμβοι που προσεγγίζονται από περιττό αριθμό δρόμων. Άρα δεν μπορεί να υπάρξει η ζητούμενη διαδρομή.
ΥΣ: Αν υπάρχει κάποιο λάθος στο συλλογισμό μου παρακαλώ τους πιο έμπειρους να μου το υποδείξουν.
Ευχαριστώ, Αντώνης

[Mihalis_Lambrou]

Θεωρώ ότι δεν υπάρχει τέτοιος δρόμος για καμία από τις δυο εικόνες.
Κάθε πόλη/τελεία/κόμβος συνδέεται με κάθε άλλο κόμβο με ένα μόνο δρόμο. Άρα μια διαδρομή που θα περνάει μόνο μια φορά από κάθε κόμβο θα περνάει μόνο μια φορά και από κάθε δρόμο. Για να συμβεί αυτό πρέπει ο αριθμός των κόμβων που προσεγγίζονται κατά περιττό αριθμό δρόμων να είναι ακριβώς 0 ή 2. Και στις δυο περιπτώσεις όμως υπάρχουν περισσότεροι από δυο κόμβοι που προσεγγίζονται από περιττό αριθμό δρόμων. Άρα δεν μπορεί να υπάρξει η ζητούμενη διαδρομή.
ΥΣ: Αν υπάρχει κάποιο λάθος στο συλλογισμό μου παρακαλώ τους πιο έμπειρους να μου το υποδείξουν.
Ευχαριστώ, Αντώνης

Αντώνη, κάτι δεν πάει καλά με τον συλλογισμό.
Θα ήταν σωστός αν έπρεπε η διαδρομή να περάσει και από κάθε δρόμο. Αλλά δεν το ζητάει το πρόβλημα.
Επισυνάπτω παράδειγμα που ο αριθμός των κόμβων που προσεγγίζονται κατά περιττό πλήθος δρόμων είναι 4 (πάντως όχι 0 ή 2) αλλά υπάρχει διαδρομή.

Φιλικά,

Μιχάλης

[Νασιούλας Αντώνης]

Έχετε δίκιο. Θεώρησα πως λέγοντας "Κάθε πόλη/τελεία/κόμβος συνδέεται με κάθε άλλο κόμβο με ένα μόνο δρόμο. Άρα μια διαδρομή που θα περνάει μόνο μια φορά από κάθε κόμβο θα περνάει μόνο μια φορά και από κάθε δρόμο." είχα μετατρέψει το πρόβλημα στη μορφή του "μονοπατιού του Όιλερ". Αλλά τελικά δεν ισχύει κάτι τέτοιο. Υπάρχει μια λεπτή διαφορά που δεν διέκρινα. Στην περίπτωση μας με αυτό που είπα συμπεραίνουμε ότι κάθε δρόμος θα διασχιστεί το πολύ μια φορά (αλλά μπορεί να υπάρξει και κάποιος που να μην διασχιστεί -όπως στο παράδειγμά σας-) ενώ σ αυτή του μονοπατιού του Όιλερ κάθε δρόμος πρέπει να διασχιστεί ακριβώς μια φορά.
Αντώνης

[lne]

Στη θεωρια γραφηματων, αυτο ειναι το προβλημα του να βρουμε ενα μονοπατι Χαμιλτον στο γραφημα (της πρωτης εικονας στη προκειμενη περιπτωση), ας το ονομασουμε Γ. Αυτο το προβλημα ειναι ισοδυναμο με το να βρουμε εναν κυκλο Χαμιλτον (δηλαδη ενα μονοπατι που να διερχεται απο καθε κομβο μια φορα αλλα να καταληγει στον αρχικο κομβο) στο γραφημα Γ*, οπου Γ* ειναι το γραφημα που δημιουργειται (απο το Γ) αν προσθεσουμε στο αρχικο γραφημα Γ εναν νεο κομβο γ ο οποιος ενωνεται με γραμμη με καθε εναν απο τους 10 κομβους του Γ.

Στο γραφημα Γ (βλεπε τη συνημμενη εικονα), παρατηρουμε οτι το συνολο κομβων (α1,α2,α3,α4,α5,α6) ειναι ανεξαρτητο (δηλαδη δεν υπαρχει καμμια γραμμη αναμεσα τους). ---εχει σημασια αυτο το συνολο να ειναι μεγιστο----
Θα αποδειξουμε οτι δεν υπαρχει κανενα μονοπατι Χαμιλτον στο γραφημα Γ αποδεικνυοντας με εις ατοπο, οτι δεν υπαρχει κυκλος Χαμιλτον στο γραφημα Γ* :

Εστω οτι υπαρχει κυκλος Χαμιλτον στο Γ* (βλεπε την εικονα κατω). Αν απο το γραφημα Γ* αφαιρεσουμε τους πεντε κομβους β1,β2,β3,β4,γ τοτε μας μενουν οι εξι ανεξαρτητοι κομβοι α1,α2,α3,α4,α5,α6. Αυτο ειναι αδυνατο αφου ο κυκλος Χαμιλτον, που εχουμε υποθεσει οτι υπαρχει καπου στο γραφημα Γ*, αποτελειται απο 11 κομβους και αρα αφαιρωντας 5 απο αυτους θα επρεπε να εμενε αθικτη τουλαχιστον ΜΙΑ γραμμη μεταξυ των 6 κομβων α1,α2,α3,α4,α5,α6.

(μαθηματικα εχω σπουδασει στην αγγλια και ελπιζω να εχω μεταφρασει σωστα στα ελληνικα τους ορους που χρησιμοποιησα

[Demetres]

Πολύ ωράια lne. στο

Η μέθοδός σου δουλεύει και για το δεύτερο γράφημα.

(Η μετάφραση νομίζω είναι σωστή αλλά επειδή και εγώ στην Αγγλία σπούδασα δεν είμαι απόλυτα σίγουρος.)

[Mihalis_Lambrou]

Πιο απλά η απόδειξη του αδυνάτου:

Βάφουμε μπλε (Μ) και κόκκινους (Κ) τους κόμβους, όπως στο σχήμα. Είναι σαφές ότι μία διαδρομή υποχρεωτικά θα πηγαίνει από μπλε κόμβο
σε κόκκινο, και αντίστροφα. Στο αριστερό σχήμα έχουμε 6 μπλε κόμβους και 4 κόκκινους άρα η διαδρομή, αν υπάρχει, ξεκινά από μπλε. Όμως
όταν κάνει Μ-Κ-Μ-Κ-Μ-Κ-Μ-Κ μας τελειώσανε οι κόκκινοι κόμβοι και μένουν δύο μπλε. ’Αρα οι δύο αυτοί μπλε δεν συνδέονται, οπότε δεν υπάρχει
η ζητούμενη διαδρομή. Όμοια στο δεύτερο σχήμα που οι μπλε κόμβοι είναι 8 και οι κόκκινοι 6.

Φιλικά,

Μιχάλης Λάμπρου

[lne]

Ευχαριστω για το καλωσορισμα !

[Νασιούλας Αντώνης]

Πολύ κομψή η λύση του κυρίου Λάμπρου. Κάτι που μετράει πολύ -όπως είχε πει και ο Χάρντι- στη μαθηματική απόδειξη. Μπράβο.
Αντώνης

[gbaloglou]

Η λύση του Μιχάλη θα ήταν ένα από τα θέματα που θα συμπεριλάμβανα σε βιβλίο γραμμένο για να μυήσει στα Μαθηματικά ανθρώπους άσχετους ή και εχθρικούς προς αυτά (Το ίδιο θα έλεγα -- έτσι για παράδειγμα -- και για την λύση του Σιλουανού (smar) στο πρόβλημα με τις τελείες )

Αλλά μια και αναφέρθηκα σε 'μη μαθηματικούς' θα ήθελα να γράψω κάποια πράγματα για την διδασκαλία τέτοιων φοιτητών σε Αμερικανικά πανεπιστήμια (και πιο συγκεκριμένα στο πολιτειακό πανεπιστήμιο της Νέας Υόρκης--Oswego (SUNY Oswego), όπου δίδαξα για 20 χρόνια), διδασκαλία που περιορίζεται σε ένα ή δυο μαθηματικά μαθήματα για φοιτητές των οποίων οι κύριες σπουδές δεν έχουν καμμία σχέση με τα Μαθηματικά (το λεγόμενο General Education, Γενική Μόρφωση). [Αντίστοιχα κάποιος που σπουδάζει Μαθηματικά είναι υποχρεωμένος να παρακολουθήσει κάποια μαθήματα Ανθρωπιστικών Σπουδών, Φυσικών Επιστημών, κλπ κλπ]

Στο SUNY Oswego λοιπόν είχαμε ένα μάθημα όπου καλύπταμε (σε πολύ χαμηλό επίπεδο) διάφορα θέματα που δεν είχαν σχέση ούτε μεταξύ τους ούτε, με εξαίρεση τον δισδιάστατο Γραμμικό Προγραμματισμό, με τα Γυμνασιακά/Λυκειακά Μαθηματικά -- Θεωρία Εκλογών (Voting), Δίκαιη Διαίρεση (Fair Division), Σχεδιασμό (Scheduling), και, βεβαίως και πάντοτε, Θεωρία Γραφημάτων.

Στην Θεωρία Γραφημάτων υπήρχαν δυο κύρια θέματα, οι κύκλοι και τα μονοπάτια Euler (Euler circuits και Euler paths) και οι κύκλοι και τα μονοπάτια Hamilton (Hamilton circuits και Hamilton paths). Στους κύκλους και στα μονοπάτια Euler μας ενδιαφέρει να περάσουμε μια ακριβώς φορά από κάθε ακμή (edge) ή 'δρόμο' (πρόβλημα καθαρίσματος δρόμων), ενώ στους κύκλους και στα μονοπάτια Hamilton μας ενδιαφέρει να περάσουμε μια ακριβώς φορά από κάθε κορυφή (vertex) ή 'γωνία' (πρόβλημα αποκομιδής απορριμάτων). [Κύκλος/circuit = αναχώρηση και επιστροφή στην ίδια κορυφή, Μονοπάτι/path = αναχώρηση και επιστροφή σε διαφορετικές κορυφές.]

Ανάμεσα στους δυο τύπους προβλημάτων υπάρχει μια βασική διαφορά: ενώ είναι εύκολο να χαρακτηρίσουμε τα γραφήματα όπου υπάρχουν κύκλοι Euler (καμμία περιττού βαθμού κορυφή, θέλουμε δηλαδή στην κάθε 'γωνία' να καταλήγει άρτιος αριθμός 'δρόμων') ή μονοπάτια Euler (ακριβώς δυο περιττού βαθμού κορυφές), δεν υπάρχουν ανάλογοι χαρακτηρισμοί για γραφήματα με κύκλους και μονοπάτια Hamilton! (Κατ' επέκταση είναι γενικά εύκολο να βρούμε κύκλους και μονοπάτια Euler όταν υπάρχουν, αλλά συχνά είναι δύσκολο να βρούμε κύκλους ή μονοπάτια Hamilton ακόμη και όταν υπάρχουν -- δείτε το αγαπημένο μου παράδειγμα στο συνημμένο )

Νομίζω πως είναι τώρα προφανές γιατί με εντυπωσιάζει τόσο η λύση του Μιχάλη: ύστερα από τόσα χρόνια διδασκαλίας του εν λόγω μαθήματος -- ναι, το προτιμούσα από Λογισμό κλπ -- δεν σκέφθηκα ποτέ αυτήν την υπέροχη 'διχρωματική' μέθοδο αποκλεισμού ύπαρξης μονοπατιού Hamilton! [Ακόμη και αν η μέθοδος δεν μπορεί να εφαρμοστεί σε όλα τα γραφήματα -- αν για παράδειγμα σε μια από τις 4 πλευρές του τετραγώνου (δεύτερο παράδειγμα) προστεθεί μια ενδιάμεση κορυφή, τότε το γράφημα εξακολουθεί να μην έχει μονοπάτια Hamilton, αλλά ο 'ετεροχρωματισμός' του Μιχάλη είναι πλέον αδύνατος.]

Γιώργος Μπαλόγλου

[Νασιούλας Αντώνης]

Που μπορώ να μπω να πάρω μια ιδέα για τη Θεωρία Γραφημάτων (κατά προτίμηση στα ελληνικά); Μου φαίνεται πολύ ενδιαφέρουσα.
Υπόψιν ότι είμαι μαθητής Β' Λυκείου και συνεπώς θέλω κάτι που να ξεκινάει απ την αρχή.
Ευχαριστώ, Αντώνης

[gbaloglou]

Που μπορώ να μπω να πάρω μια ιδέα για τη Θεωρία Γραφημάτων (κατά προτίμηση στα ελληνικά); Μου φαίνεται πολύ ενδιαφέρουσα.
Υπόψιν ότι είμαι μαθητής Β' Λυκείου και συνεπώς θέλω κάτι που να ξεκινάει απ την αρχή.
Ευχαριστώ, Αντώνης

Δες για παράδειγμα εδώ, και γενικά κάνε διαδικτυακές αναζητήσεις για "Θεωρία Γράφων", "γράφος" (η μάλλον ατυχής απόδοση του "graph" στα Ελληνικά), κλπ.

Γιώργος Μπαλόγλου

[Νασιούλας Αντώνης]

Ευχαριστώ πολύ,
Αντώνης

[gbaloglou]

Στο SUNY Oswego λοιπόν είχαμε ένα μάθημα όπου καλύπταμε (σε πολύ χαμηλό επίπεδο) διάφορα θέματα που δεν είχαν σχέση ούτε μεταξύ τους ούτε, με εξαίρεση τον δισδιάστατο Γραμμικό Προγραμματισμό, με τα Γυμνασιακά/Λυκειακά Μαθηματικά -- Θεωρία Εκλογών (Voting), Δίκαιη Διαίρεση (Fair Division), Σχεδιασμό (Scheduling), και, βεβαίως και πάντοτε, Θεωρία Γραφημάτων.

Επισκεφτείτε το https://www.oswego.edu/~klemenz/KlemenzMath102.htm για μια αρκετά καλή ιδέα σχετικά με το μάθημα που αναφέρω παραπάνω.

[Η σελίδα φτιάχτηκε από τον Curt Klemenz, συνταξιούχο μηχανικό που δίδασκε ως έκτακτος στο πρώην πανεπιστήμιο μου για αρκετά χρόνια^ σταμάτησε πριν έναν χρόνο, κατέβασε την ιστοσελίδα, μετάνοιωσε και επανέρχεται στην ενεργό δράση, οπότε μόλις ανέβασε και πάλι την ιστοσελίδα!]

Γιώργος Μπαλόγλου

[Νασιούλας Αντώνης]

Την πολύ όμορφη ιδέα -του χρωματισμού- που χρησιμοποίησε ο κ. Μιχάλης μπορεί κανείς να βρει και στο βιβλίο του Engel Problem Solving Strategies στην ενότητα Colouring Proofs.