ΜΟΝΟΚΟΝΤΥΛΙΕΣ

1. Το παιχνίδι

1.1 Οι κανόνες

Μονοκοντυλιά είναι ένα παιχνίδι στο οποίο καλούμαστε να σχεδιάσουμε κάτι

1. χωρίς να σηκώσουμε το μολύβι απ’ το χαρτί και
2. χωρίς να διπλοπεράσουμε μια γραμμή.

Όταν έμαθα μικρός αυτό το παιχνίδι, με είχε πιάσει μανία να ψάχνω πώς θα μπορούσα να ζωγραφίσω σχήματα μονοκοντυλιά. Κάποια στιγμή έθεσα στον εαυτό μου τον (απλό φαινομενικά) στόχο της σχεδίασης ενός ρόμβου με τις διαγωνίους του. Ήταν αδύνατο… Το προσπαθούσα για καιρό, μέχρι που, μεγάλος πια, κατάλαβα πως απλά δεν γίνεται.

1.2 Δοκιμάστε μόνοι σας

Πριν δούμε ποια σχήματα μπορούν να γίνουν μονοκοντυλιά και ποιο είναι το μυστικό της επίλυσής τους, δοκιμάστε τα παρακάτω σχέδια. Θα ’ναι πιο διασκεδαστική η προσπάθεια, αν δεν γνωρίζετε το κόλπο.

2. Ορισμοί και θεωρήματα

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

[ Εικόνα: meme.png — τοποθετήστε το αρχείο ]

Ορισμός 1 — Γράφημα

«Γράφημα» ονομάζουμε ένα σύνολο από κόμβους (μαύροι κύκλοι) συνδεδεμένους με οδούς (κόκκινοι διάδρομοι).

Ορισμός 2 — Διαδρομή

«Διαδρομή του γραφήματος» ονομάζουμε κάθε ακολουθία κόμβων συνδεδεμένων με οδούς. Συμβολικά γράφουμε $K_1 \to K_2 \to \dots \to K_n$ για την διαδρομή που ξεκινάει από τον κόμβο $K_1$ και καταλήγει στον $K_n$.

Λέμε ότι «η διαδρομή αυτή διατρέχει τους κόμβους $K_1, K_2, \dots, K_n$».

Ο $K_1$ ονομάζεται «εναρκτήριος κόμβος» (μοβ), ο $K_n$ «καταληκτήριος» (πράσινος) και κάθε άλλος καλείται «κόμβος διέλευσης» (μπλε).

Ομοίως, η οδός $K_1 \to K_2$ ονομάζεται «εναρκτήρια οδός» (μοβ), η $K_{n-1} \to K_n$ «καταληκτήρια» (πράσινη) και κάθε άλλη καλείται «οδός διέλευσης» (μπλε).

Ορισμός 3 — Συνεκτικό γράφημα

Ένα γράφημα ονομάζεται «συνεκτικό» όταν κάθε κόμβος μπορεί να ενωθεί μέσω μιας διαδρομής με οποιονδήποτε άλλον. Το παραπάνω γράφημα είναι συνεκτικό.

Ορισμός 4 — Μονοκοντυλιά

Ένα γράφημα ονομάζεται «μονοκοντυλιά», όταν υπάρχει διαδρομή που να διατρέχει όλους τους κόμβους και τις οδούς ενός γραφήματος, χωρίς να χρησιμοποιεί δύο φορές την ίδια οδό.

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

Ορισμός 5 — Άρτιο και περιττό γράφημα

Ένα γράφημα ονομάζεται «άρτιο», όταν σε κάθε κόμβο του συνδέεται άρτιο πλήθος οδών.

Όταν υπάρχουνε κόμβοι με περιττό πλήθος οδών, τότε το γράφημα ονομάζεται «περιττό».

Τα παραπάνω γραφήματα ήταν περιττά, το παρακάτω είναι άρτιο.

Θεώρημα 1

Κάθε περιττή μονοκοντυλιά έχει δύο ακριβώς περιττούς κόμβους, οι οποίοι αποτελούν την αρχή και το τέλος της.

Απόδειξη

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

Το να υπάρχει μόνο ένας περιττός κόμβος πάλι αποκλείεται, καθόσον ξεκινώντας την διαδρομή από τον $K_1$, στον $K_1$ παραμένει άρτιο πλήθος οδών, άρα μόνο οδοί διέλευσης, όπως άλλωστε και σε κάθε κόμβο. Δηλαδή δε θα έχουμε καταληκτίριο κόμβο.

Ορισμός 6 — Κλειστή μονοκοντυλιά

Ονομάζουμε «κλειστή» κάθε μονοκοντυλιά που ο εναρκτήριος κόμβος της ταυτίζεται με τον καταληκτήριο.

Θεώρημα 2

Κάθε άρτια μονοκοντυλιά είναι κλειστή.

Απόδειξη

Έστω η διαδρομή που διατρέχει το γράφημα καθιστώντας το μονοκοντυλιά. Ξεκινώντας την διαδρομή $K_1 \to K_2 \to \dots \to K_n$ από τον $K_1$ (μοβ βέλος), στον $K_1$ παραμένει περιττό πλήθος οδών. Το άρτιο πλήθος οδών περί του $K_1$ αναλώνεται σε διελεύσεις (όσοι μπαίνουν, τόσοι βγαίνουν, μπλε και πορτοκαλί βέλη) και μένει μία οδός, η οποία δεν είναι διέλευσης, άρα θα αποτελεί την καταληκτήρια οδό (πράσινο βέλος).

Θεώρημα 3

Σε κάθε άρτια μονοκοντυλιά η διαδρομή επίλυσης είναι ανεξάρτητη της αφετηρίας.

Απόδειξη

Έστω $K_1 \to K_2 \to \dots \to K \to \dots \to K_n$ η διαδρομή επίλυσης, η οποία διέρχεται από έναν κόμβο $Κ$. Αφού η μονοκοντυλιά είναι άρτια, θα ισχύει $K_1 = K_n$ (Θ.2), άρα έχουμε $K_1 \to K_2 \to \dots \to K \to \dots \to K_{n-1} \to K_1$. Προφανώς και η διαδρομή $K \to \dots \to K_{n-1} \to K_1 \to K_2 \to \dots \to K$ επιλύει την μονοκοντυλιά.

Θεώρημα 4

Κάθε άρτιο γράφημα ($Γ$) γράφεται σαν ένωση άρτιων μονοκοντυλιών.

Απόδειξη

Καταρχάς οποιοδήποτε γράφημα (άρτιο ή περιττό) γράφεται ως ένωση μονοκοντυλιών με έναν προφανή τρόπο: Παίρνοντας τα (προφανώς περιττά) υπο-γραφήματα που σχηματίζονται από την κάθε οδό.

Έστω $\Gamma = M_1 \cup M_2 \cup \dots \cup M_m$, όπου όμως η $M_k$ είναι περιττή μονοκοντυλιά και ας είναι $Κ$ ένας περιττός κόμβος της. Αφού το $Γ$ είναι άρτιο γράφημα, θα υπάρχει περιττό πλήθος οδών από άλλες μονοκοντυλιές (π.χ. $M_p, M_q$ κ.τ.λ.) που θα καταλήγουν στον $Κ$.

Είναι αδύνατον κάθε μονοκοντυλιά $M_p, M_q$ κ.τ.λ. να συνδέεται με τον $Κ$ με άρτιο πλήθος οδών, διότι τότε θα του προσέφεραν συνολικά άρτιο πλήθος οδών. Άρα έστω $M_i$ η μονοκοντυλιά που του προσφέρει περιττό πλήθος οδών.

Σ’ αυτή την περίπτωση μπορούμε να θεωρήσουμε τον $Κ$ καταληκτήριο κόμβο της $M_i$ και εναρκτήριο της $M_k$. Συνεπώς, αν οι διαδρομή $K_{i,1} \to K_{i,2} \to \dots \to K$ επιλύει την $M_i$ και η $K \to K_{k,2} \to \dots \to K_{k,t}$ επιλύει την $M_k$, τότε η διαδρομή $K_{i,1} \to K_{i,2} \to \dots \to K \to K_{k,2} \to \dots \to K_{k,t}$ επιλύει την $M_i \cup M_k$.

Η διαδικασία αυτή συνεχίζει όσο έχουμε περιττές μονοκοντυλιές, οπότε τερματίζει όταν θα έχουν σχηματίσει σύνολα άρτιων μονοκοντυλιών. Στα σχήματα που παρατίθενται παραπάνω είχαμε αρχικά ένα άρτιο γράφημα που σχηματιζόταν σαν ένωση 3 άρτιων μονοκοντυλιών (γκρι, μοβ και πορτοκαλί) και 4 περιττών μονοκοντυλιών (σκούρα πράσινη, φωτεινή πράσινη, κίτρινη και μπλε). Κατόπιν συγχωνεύθηκαν οι πράσινες μονοκοντυλιές μαζί με την κίτρινη, τη μοβ και την μπλε και έγιναν η μεγάλη άρτια μονοκοντυλιά του δεύτερου σχήματος, το οποίο πλέον αποτελείται μονάχα από άρτιες μονοκοντυλιές.

Θεώρημα 5

Κάθε άρτιο γράφημα είναι μονοκοντυλιά.

Απόδειξη

Για το $Γ$ ισχύει $\Gamma = M_1 \cup M_2 \cup \dots \cup M_m$, όπου οι μονοκοντυλιές αυτές είναι άρτιες (Θ. 4). Έστω ότι οι $M_x$ και $M_y$ έρχονται σε επαφή στον κόμβο $Κ$. Από το Θ. 3 έχουμε ότι μπορεί ο $Κ$ να θεωρηθεί εναρκτήριος και για τις δύο μονοκοντυλιές. Από το Θ. 2 έχουμε ότι θα αποτελεί και καταληκτίριο κόμβο της κάθε μίας. Άρα αν ξεκινήσουμε από τον $Κ$, επιλύσουμε την $M_x$, καταλήξουμε στον $Κ$, επιλύσουμε την $M_y$ και καταλήξουμε στον $Κ$, έχουμε επιλύσει την $M_x \cup M_y$. Ομοίως φθάνει να επιλυθεί όλο το $Γ$.

Θεώρημα 6

Κάθε γράφημα με δύο περιττούς κόμβους είναι μονοκοντυλιά με αρχή τον έναν τους και τέλος τον άλλον.

Απόδειξη

Έστω $K_1, K_2$ οι δύο περιττοί κόμβοι του $Γ$. Θεωρούμε το γράφημα $Γ’$, το οποίο έχει τους ίδιους κόμβους και δρόμους με το $Γ$ μόνο που οι κόμβοι $K_1, K_2$ συνδέονται με την οδό $δ$.

Έχουμε ότι:

• στους $K_1, K_2$ προσθέθηκε ένας δρόμος, οπότε έγιναν άρτιοι και
• οι υπόλοιποι κόμβοι δεν αλλάξανε, άρα παραμένουν άρτιοι.

Άρα έχουμε μονάχα άρτιους κόμβους, οπότε το $Γ’$ είναι άρτιο γράφημα. Ως εκ τούτου από το Θ. 5 θα είναι μονοκοντυλιά.

Από το Θ. 3 έχουμε ότι αυτή μπορεί να επιλυθεί αρχίζοντας από τον $K_1$. Η περίπτωση $K_1 \to K_2 \to K_s \to \dots \to K_r \to K_1$ μπορεί να αποφευχθεί πηγαίνοντας ανάποδα την επίλυση αυτή, δηλαδή $K_1 \to K_r \to \dots \to K_s \to K_2 \to K_1$.

Έτσι, όσον αφορά το Γ, έχουμε την επίλυση του $Γ’$ χωρίς απλά να κάνουμε την μετάβαση $K_2 \to K_1$, δηλαδή έχουμε τη διαδρομή επίλυσης $K_1 \to K_r \to \dots \to K_s \to K_2$.