Το βιβλίο ζωγραφικής για το δρόμο μου προς το σχολείο. Ζωγραφιές κανόνες του δρόμου

Ενημέρωση ιστότοπου
10.12.2006 15:46
Για τους λάτρεις των αυτοκινήτων και των κινούμενων σχεδίων - σελίδες ζωγραφικής από το καρτούν Cars.

Χάρη στη Disney και την Pixar, τον Ιούνιο του 2006 όλος ο κόσμος είδε ένα καρτούν στο οποίο μόνο τα αυτοκίνητα έγιναν ήρωες.

Αυτοκίνητα στο καρτούν Τα αυτοκίνητα ("Αυτοκίνητα") ζουν συνηθισμένες ζωές - το ένα διατηρεί ένα μαγαζί με καουτσούκ, το άλλο ένα στούντιο συντονισμού και μερικά απλά ζουν για τη δική τους ευχαρίστηση, όπως ο χίπης Fillmore (Volkswagen T1) ή ο φίλος του - βετεράνος του Β' Παγκοσμίου Πολέμου Serge (Willy). Ο κύριος χαρακτήρας της εικόνας McQueen, με το παρατσούκλι "Lightning", ονειρεύεται μόνο αγώνες, νίκες και δόξα. Μόλις βρεθεί στο Radiator District στον διάσημο αυτοκινητόδρομο 66 των ΗΠΑ, ο «πράσινος» McQueen λέει αμέσως σε όλους πόσο γρήγορος και ψύχραιμος είναι. Ωστόσο, η πρώτη εκκίνηση στον αγώνα NASCAR διαλύει τις ψευδαισθήσεις του. Οι φίλοι βοηθούν τον ήρωα να επιβιώσει από την απώλεια - το παλιό ρυμουλκούμενο Meiter (GMC Pick-up), ο μέντορας Doc Hudson (Hudson Hornet) και ο μικρός Luigi (Fiat 600), που ονειρεύεται να δει μια πραγματική Ferrari.

Λοιπόν, πού χωρίς τη ρομαντική καλλονή Sally (Porsche με ένα γοητευτικό τατουάζ 911)! Σε μεγάλο βαθμό χάρη σε αυτούς, ο McQueen θα συνεχίσει να κερδίσει τον αγώνα, νικώντας τον κύριο αντίπαλο Chico (Plymouth Hemi Cuda). Το όνειρο του Λουίτζι θα γίνει επίσης πραγματικότητα - μια μέρα ένας «επιβήτορας από το Μαρανέλο» θα καλέσει στο μαγαζί του για να αλλάξει λάστιχα, κάτι που, παρεμπιπτόντως, εκφράστηκε από τον ίδιο τον «Κόκκινο βαρόνο» Μίκαελ Σουμάχερ.

Αξιοσημείωτο είναι ότι τόσο οι δημιουργοί της εικόνας όσο και αυτοί που την εξέφρασαν είναι άνθρωποι που ασχολούνται με αυτοκίνητα. Για παράδειγμα, ο σκηνοθέτης Joe Lasseter πέρασε το μεγαλύτερο μέρος της παιδικής του ηλικίας στο εργοστάσιο της Chevrolet, όπου ο πατέρας του ήταν ένας από τους επικεφαλής σχεδιαστές. Ο Τζέι Μέις, ο κορυφαίος σχεδιαστής της εταιρείας Ford, ενήργησε ως σύμβουλος. Εκτός από τον ήδη αναφερθέντα επτά φορές παγκόσμιο πρωταθλητή της Formula 1 Michael Schumacher, οι αστέρες του NASCAR Richard Petty και Paul Newman, καθώς και ο θρυλικός δρομέας Michael Andretti, συμμετείχαν στην έκφραση των ηρώων.

Χρησιμοποιήθηκε μόνο ο αρχικός θόρυβος του αυτοκινήτου - για παράδειγμα, ειδικά για αγωνιστικά επεισόδια, ο ήχος ηχογραφήθηκε για αρκετές εβδομάδες σε αμερικανικά οβάλ κατά τη διάρκεια διαγωνισμών NASCAR. Χρειάστηκαν περισσότερα από δύο χρόνια για να δημιουργηθεί η εικόνα, ο προϋπολογισμός της οποίας ήταν 70 εκατομμύρια δολάρια. Κατά τη διάρκεια αυτής της περιόδου, δημιουργήθηκαν 43 χιλιάδες διαφορετικά σκίτσα αυτοκινήτων και κάθε σχέδιο χρειάστηκε περισσότερες από 17 ώρες. Υπάρχουν συνολικά 120 χαρακτήρες αυτοκινήτου στην ταινία, από νέες Porsche και Ferrari μέχρι αντίκες Ford Ts.

Μπορείτε να κρατήσετε τα αγόρια απασχολημένα για πολλή ώρα αν τα προσκαλέσετε να παίξουν με αυτοκίνητα στο sandbox. Τι γίνεται όμως αν έξω κάνει κρύο, το παιδί βαριέται. Σε αυτήν την περίπτωση, μπορείτε να κατεβάσετε και να εκτυπώσετε τα ακόλουθα πρότυπα δρόμου αυτοκινήτων. Η διασκέδαση θα ξεκινήσει με το κόψιμο όλων των δακτυλίων, των στροφών και των ευθύγραμμων δρόμων. Από αυτά τα πρότυπα, ένα παιδί μπορεί να κατασκευάσει έναν δρόμο οποιουδήποτε σχήματος, απλώς βεβαιωθείτε ότι έχει εκτυπωθεί ο σωστός αριθμός των απαιτούμενων φύλλων Α4.

Κατεβάστε ευθύ δρόμο για αυτοκίνητα

Αυτά τα φύλλα θα χρειαστούν περισσότερο από όλα. Σε ένα φύλλο Α4 τοποθετήσαμε 3 δρόμους που πρέπει να εκτυπωθούν και να κοπούν. Δείξτε στο παιδί σας πώς να κόβει το δρόμο σε ορθή γωνία για να κάνει το τμήμα στο μήκος που χρειάζεται.

Δρόμος για αυτοκίνητα: δακτύλιος

Για να συνδέσετε τους δρόμους, θα χρειαστείτε ένα δαχτυλίδι, το πρότυπο του οποίου παρουσιάζεται παραπάνω, και ξεκινήστε να χτίζετε την υποδομή σας από αυτό.

Δρόμος αυτοκινήτου: Ευθεία στροφή

Οι στροφές που παρουσιάζονται θα επιτρέψουν στο αγόρι να στρίψει το δρόμο στις 90 μοίρες, προς την κατεύθυνση που χρειάζεται.

Όχι απότομη στροφή του δρόμου για αυτοκίνητα

Το παρακάτω πρότυπο Α4 θα σας βοηθήσει να στρίψετε το δρόμο σε οποιαδήποτε ακτίνα.

Βρίσκεστε στη σελίδα χρωματισμού δρόμου. Η σελίδα χρωματισμού που βλέπετε περιγράφεται από τους επισκέπτες μας ως εξής "" Εδώ θα βρείτε πολλές σελίδες χρωματισμού στο διαδίκτυο. Μπορείτε να κατεβάσετε σελίδες χρωματισμού δρόμων και επίσης να τις εκτυπώσετε δωρεάν. Όπως γνωρίζετε, οι δημιουργικές δραστηριότητες παίζουν τεράστιο ρόλο στην ανάπτυξη του παιδιού. Ενεργοποιούν τη νοητική δραστηριότητα, σχηματίζουν μια αισθητική γεύση και ενσταλάζουν την αγάπη για την τέχνη. Η διαδικασία χρωματισμού εικόνων με θέμα το δρόμο αναπτύσσει λεπτές κινητικές δεξιότητες, επιμονή και ακρίβεια, βοηθά να μάθετε περισσότερα για τον κόσμο γύρω μας, σας εισάγει σε όλη την ποικιλία χρωμάτων και αποχρώσεων. Κάθε μέρα προσθέτουμε νέες δωρεάν σελίδες χρωματισμού για αγόρια και κορίτσια στον ιστότοπό μας, τις οποίες μπορείτε να χρωματίσετε online ή να τις κατεβάσετε και να τις εκτυπώσετε. Ένας βολικός κατάλογος που καταρτίζεται ανά κατηγορίες θα διευκολύνει την εύρεση της σωστής εικόνας και μια μεγάλη ποικιλία σελίδων χρωματισμού θα σας επιτρέψει να βρίσκετε ένα νέο ενδιαφέρον θέμα για χρωματισμό κάθε μέρα.

Η γνώση ενός παιδιού για τους Κανόνες Οδοποιίας είναι μια από τις βασικές προϋποθέσεις για την ασφάλειά του στο δρόμο. Πολλοί πεζοί, συμπεριλαμβανομένων των ενηλίκων, είναι μάλλον επιπόλαιοι για την τήρηση αυτών των κανόνων, κάτι που συχνά γίνεται αιτία τροχαίων ατυχημάτων διαφορετικής σοβαρότητας. Τα παιδιά πρέπει να καταλάβουν ξεκάθαρα ότι όντας στο δρόμο στο χωριό, είναι πλήρως συμμετέχοντες στο δρόμο, επομένως η τήρηση των κανόνων κυκλοφορίας είναι δική τους ευθύνη.

Σελίδες ζωγραφικής Κανόνες δρόμου για παιδιά.

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

1. Σελίδα χρωματισμού φανάρι.

Το καλύτερο μέρος για να διασχίσετε το δρόμο με ασφάλεια είναι σε μια διάβαση πεζών εξοπλισμένη με φανάρια. Οι σελίδες χρωματισμού φωτεινών σηματοδοτών περιέχουν επίσης μικρές ρίμες για να βοηθήσουν τα παιδιά να θυμούνται τους κανόνες για τη χρήση τους πιο εύκολα.

• Να ξεκινάτε πάντα να οδηγείτε μόνο όταν το φανάρι είναι πράσινο.
• Ποτέ μην διασχίζετε το δρόμο με κόκκινα ή κίτρινα σήματα κυκλοφορίας, ακόμα κι αν δεν υπάρχουν οχήματα κοντά.
• Όταν ανάψετε το πράσινο φως, βεβαιωθείτε επιπλέον ότι είστε ασφαλείς - κοιτάξτε αριστερά και μετά δεξιά.

2. Χρωματισμός της διάβασης πεζών.

Μάθετε στο παιδί σας να διασχίζει το οδόστρωμα μόνο σε διάβαση πεζών. Οι χρωματιστικές σελίδες των διαδράσεων πεζών θα διδάξουν στα παιδιά να διασχίζουν σωστά το δρόμο. Μια διάβαση που δεν είναι εξοπλισμένη με φανάρι ονομάζεται άναρχη.

• Η διάβαση πεζών σημειώνεται στην επιφάνεια του δρόμου με ζέβρα.
• Πριν διασχίσετε το δρόμο, επιθεωρήστε τον προσεκτικά, βεβαιωθείτε ότι δεν υπάρχει κίνηση κοντά.
• Διασχίστε το δρόμο, μην τρέχετε απέναντι.
• Μην διασχίζετε το δρόμο.
• Δώστε ιδιαίτερη προσοχή στα όρθια οχήματα που εμποδίζουν τη θέα σας.
• Σταματήστε να μιλάτε στο τηλέφωνο ενώ περπατάτε σε μια διάβαση πεζών.
• Εάν υπάρχουν υπόγεια ή υπερυψωμένα περάσματα κοντά, φροντίστε να τα χρησιμοποιήσετε, σε τέτοια σημεία η κίνηση είναι ιδιαίτερα έντονη.

3. Πεζοδρόμια.

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

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

4. Σελίδες χρωματισμού με κανόνες συμπεριφοράς για παιδιά στις αστικές συγκοινωνίες και στις στάσεις λεωφορείων.

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

• Μια στάση δημόσιας συγκοινωνίας είναι ένα επικίνδυνο μέρος λόγω της πιθανής κακής ορατότητας του δρόμου και του μεγάλου πλήθους ανθρώπων που μπορεί κατά λάθος να σπρώξουν ένα παιδί από το πεζοδρόμιο στο οδόστρωμα. Εδώ πρέπει να είστε ιδιαίτερα προσεκτικοί.
• Πλησιάστε τις πόρτες της μεταφοράς μόνο αφού έχει σταματήσει τελείως.
• Αφού φύγετε από το όχημα, συνεχίστε να διασχίζετε το δρόμο μόνο αφού φύγει από τη στάση.

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

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

Τις προάλλες διάβασα για ένα ενδιαφέρον πρόβλημα από τη θεωρία γραφημάτων - την εικασία χρωματισμού του δρόμου. Αυτή η εικασία ήταν ανοιχτή εδώ και 37 χρόνια, αλλά πριν από τρία χρόνια την απέδειξε ο Ισραηλινός μαθηματικός Abraham Trachtman. Η απόδειξη αποδείχτηκε αρκετά στοιχειώδης και με κάποιες δυσκολίες (επειδή ο εγκέφαλός μου ατροφούσε) μπόρεσα να την διαβάσω και να την κατανοήσω, και μάλιστα θα προσπαθήσω να την εξηγήσω σε αυτό το λήμμα.

Το πρόβλημα μπορεί να εξηγηθεί με ένα παράδειγμα. Φανταστείτε έναν χάρτη της πόλης, όπου σε κάθε διασταύρωση μπορείτε να πάτε σε μία από τις τέσσερις κατευθύνσεις - βόρεια, νότια, ανατολικά και δυτικά. Εάν το αυτοκίνητο ξεκινά από κάποια διασταύρωση και ακολουθεί κάποια λίστα κατευθύνσεων - "βόρεια, βόρεια, ανατολή" κ.λπ. - τότε τελικά θα φτάσει σε κάποια άλλη διασταύρωση. Είναι δυνατόν να βρεθεί μια τέτοια λίστα με οδηγίες, ίσως μεγάλη, που θα οδηγήσει το αυτοκίνητο στο ίδιο σημείο, ανεξάρτητα από το πού ξεκίνησε; Εάν ο χάρτης μοιάζει με το Μανχάταν - ένα κανονικό πλέγμα - τότε όχι, αλλά ίσως υπάρχουν πολλά αδιέξοδα και απροσδόκητες στροφές;

Ή άλλο παράδειγμα. Ο φίλος σας έχει κολλήσει σε έναν λαβύρινθο στον οποίο πρέπει να βρείτε το κέντρο και σας κάλεσε ζητώντας βοήθεια. Ξέρεις πώς λειτουργεί ο λαβύρινθος, αλλά δεν ξέρεις πού είναι ο φίλος σου. Μπορεί να υπάρξει μια σειρά εντολών που σίγουρα θα οδηγήσει τον φίλο σας στο κέντρο, όπου κι αν βρίσκεται;

Σε αυτά τα δύο παραδείγματα, οι "κατευθύνσεις" σε κάθε σημείο είναι σταθερές και η λύση είτε υπάρχει είτε δεν υπάρχει. Αλλά σε μια πιο γενική περίπτωση, αυτό το πρόβλημα ρωτά: εάν μπορούμε να επιλέξουμε πού, για παράδειγμα, σημεία "δύση, βόρεια, ανατολή, νότος", σε κάθε διασταύρωση με τον δικό της τρόπο, μπορούμε τότε να διασφαλίσουμε την ύπαρξη μιας "συγχρονιστικής λέξης" " - μια ακολουθία εντολών, η οποία από οποιοδήποτε μέρος θα οδηγήσει σε μια σταθερή;

Στη γενική περίπτωση, ας υπάρχει ένα κατευθυνόμενο γράφημα G - με άκρες "βέλους" μεταξύ των κορυφών. Αφήστε αυτό το γράφημα να έχει ομοιόμορφο εξερχόμενο βαθμό d - αυτό σημαίνει ότι ακριβώς d άκρες βγαίνουν έξω από κάθε κορυφή. Ταυτόχρονα, ένας διαφορετικός αριθμός, όχι απαραίτητα d, μπορεί να εισέλθει σε κάθε επιμέρους κορυφή. Ας υποθέσουμε ότι έχουμε ένα σύνολο από d γράμματα κάποιου αλφαβήτου, τα οποία θα ονομάζουμε «λουλούδια». Στη συνέχεια δίνεται ο «χρωματισμός» του γραφήματος εκχωρώντας για κάθε κορυφή όλα τα d γράμματα για το d των εξερχόμενων άκρων του. Αν λοιπόν «βρισκόμαστε» σε κάποια κορυφή και θέλουμε να «πάμε» κάπου σύμφωνα με το χρώμα α, τότε ο χρωματισμός θα μας λέει πάντα ποια άκρη πρέπει να πάμε σε ποια νέα κορυφή. Μια "λέξη" είναι οποιαδήποτε αλληλουχία χρωμάτων γραμμάτων. Στη συνέχεια, εάν δίνεται ένας χρωματισμός στο γράφημα, και το x είναι κάποια κορυφή και το w είναι κάποια λέξη, τότε το xw δηλώνει την κορυφή στην οποία θα φτάσουμε, ξεκινώντας από το x και ακολουθώντας τη λέξη w.

Το βιβλίο ζωγραφικής ονομάζεται συγχρονισμός, εάν υπάρχει μια λέξη w που οδηγεί οποιαδήποτε κορυφή x σε μια σταθερή κορυφή x 0 . Στην περίπτωση αυτή καλείται το w συγχρονισμός λέξης. Το ερώτημα που τίθεται από το πρόβλημα χρωματισμού δρόμου είναι: υπάρχει πάντα ένας σύγχρονος χρωματισμός; Είναι πάντα δυνατό να χρωματίσουμε τις άκρες ενός γραφήματος με τέτοιο τρόπο ώστε όλες οι κορυφές να μπορούν να μειωθούν σε μία;

Αυτό το πρόβλημα έχει εφαρμογές σε πολλές διαφορετικές περιοχές, για τις οποίες μπορείτε να διαβάσετε, για παράδειγμα, στη Wikipedia. Για παράδειγμα, στην επιστήμη των υπολογιστών, στη θεωρία των αυτομάτων. Ένα γράφημα με χρωματισμό μπορεί να θεωρηθεί ως μια ντετερμινιστική μηχανή πεπερασμένης κατάστασης στην οποία οι κορυφές είναι οι καταστάσεις και οι ακμές υποδεικνύουν τον τρόπο πλοήγησης μεταξύ τους. Ας υποθέσουμε ότι ελέγχουμε αυτό το αυτόματο από απόσταση, στέλνοντας εντολές σε κάποιο κανάλι πληροφοριών και λόγω κάποιων βλαβών, αυτό το κανάλι ήταν μολυσμένο, το αυτόματο έλαβε κάποιες λανθασμένες οδηγίες και τώρα δεν ξέρουμε καθόλου σε ποια κατάσταση βρίσκεται. Στη συνέχεια, εάν υπάρχει μια λέξη συγχρονισμού, μπορούμε να τη φέρουμε σε μια γνωστή κατάσταση, ανεξάρτητα από το πού βρίσκεται τώρα.

Πότε λοιπόν υπάρχει ο χρωματισμός συγχρονισμού; Η εικασία χρωματισμού δρόμου επιβάλλει δύο ακόμη περιορισμούς στο γράφημα (πέρα από το γεγονός ότι κάθε κορυφή έχει ακριβώς d άκρες). Πρώτον, το γράφημα πρέπει να είναι ισχυρά συνδεδεμένο, πράγμα που σημαίνει ότι υπάρχει μια διαδρομή από οποιαδήποτε κορυφή σε οποιαδήποτε άλλη. Δεύτερον, το γράφημα δεν πρέπει να είναι περιοδικό. Φανταστείτε ότι όλες οι κορυφές του γραφήματος μπορούν να χωριστούν σε σύνολα V 1 , V 2 , ... V n , έτσι ώστε οποιαδήποτε άκρη του γραφήματος να συνδέει κορυφές από μερικά V i και V i+1 ή V n και V 0 . Δεν υπάρχουν ακμές μεταξύ των κορυφών σε κάθε V και δεν μπορούν να "πηδήξουν" μεταξύ οποιουδήποτε V, μόνο με τη σειρά. Ένα τέτοιο γράφημα ονομάζεται περιοδικό. Είναι σαφές ότι ένα τέτοιο γράφημα δεν μπορεί να έχει συγχρονιστικό χρωματισμό, γιατί ανεξάρτητα από το πώς χρωματίζετε και ποιες λέξεις πηγαίνετε, δύο κορυφές σε διαφορετικό V i δεν θα ενωθούν ποτέ - θα κάνουν τον κύκλο.

Το θεώρημα του χρωματισμού του δρόμου λέει ότι αυτές οι συνθήκες είναι επαρκείς: οποιοδήποτε μη περιοδικό ισχυρά συνδεδεμένο κατευθυνόμενο γράφημα με d άκρες από κάθε κορυφή έχει συγχρονιζόμενο χρωματισμό. Διατυπώθηκε για πρώτη φορά ως εικασία το 1970 και από τότε έχουν υπάρξει πολλά επιμέρους αποτελέσματα που αποδεικνύουν ειδικές περιπτώσεις, αλλά μια πλήρης απόδειξη εμφανίστηκε μόλις το 2007. Αυτό που ακολουθεί είναι η επανάληψη σχεδόν ολόκληρης της απόδειξης (εκτός από ένα τεχνικό λήμμα).

Περιοδικότης

Πρώτα απ 'όλα, ας αντικαταστήσουμε τη συνθήκη μη περιοδικότητας με μια άλλη ισοδύναμη με αυτήν. Ένα γράφημα είναι περιοδικό αν και μόνο αν υπάρχει αριθμός N>1 που διαιρεί τη διάρκεια οποιουδήποτε κύκλου στο γράφημα. Εκείνοι. η απαίτησή μας για μη περιοδικότητα είναι ισοδύναμη με το να πούμε ότι δεν υπάρχει τέτοιο Ν, ή με άλλα λόγια, ο μεγαλύτερος κοινός διαιρέτης των μηκών όλων των κύκλων στο γράφημα είναι 1. Θα αποδείξουμε ότι κάθε γράφημα που ικανοποιεί αυτήν την συνθήκη έχει συγχρονισμός χρωματισμού.

Το να αποδειχθεί ότι η περιοδικότητα είναι ισοδύναμη με τη συνθήκη "υπάρχει N>1 με την οποία διαιρείται το μήκος οποιουδήποτε κύκλου" είναι ασήμαντο προς τη μία κατεύθυνση και εύκολο στην άλλη. Εάν είστε διατεθειμένοι να το πάρετε με πίστη, μπορείτε εύκολα να παραλείψετε το υπόλοιπο αυτής της παραγράφου· δεν έχει σημασία για την υπόλοιπη απόδειξη. Αν το γράφημα είναι περιοδικό, π.χ. Εφόσον είναι δυνατό να διαιρεθούν οι κορυφές σε σύνολα V 1 , V 2 , ... V n , έτσι ώστε οι ακμές να πηγαίνουν ανάμεσά τους σε έναν κύκλο, τότε είναι προφανές ότι το μήκος οποιουδήποτε κύκλου πρέπει να διαιρείται με το n, δηλ. πληρούται η νέα προϋπόθεση. Αυτή είναι μια τετριμμένη κατεύθυνση, αλλά για την αντικατάστασή μας χρειαζόμαστε μόνο τη δεύτερη κατεύθυνση. Ας υποθέσουμε ότι υπάρχει τέτοιο N>1, που διαιρεί τη διάρκεια οποιουδήποτε κύκλου. Ας δημιουργήσουμε στο γράφημά μας κάποιο κατευθυνόμενο δέντρο που εκτείνεται (spanning tree) με ρίζα στην κορυφή r. Υπάρχει μια διαδρομή προς οποιαδήποτε κορυφή x σε αυτό το δέντρο που ξεκινά από τη ρίζα μήκους l(x). Τώρα ισχυριζόμαστε ότι για οποιαδήποτε ακμή p-->q στο γράφημα, l(q) = l(p) + 1 (mod N). Εάν αυτή η δήλωση είναι αληθής, τότε αμέσως προκύπτει από αυτήν ότι μπορούμε να χωρίσουμε όλες τις κορυφές σε σύνολα V i σύμφωνα με το l(x) mod N και το γράφημα θα είναι περιοδικό. Γιατί είναι αλήθεια αυτή η δήλωση; Εάν το p-->q είναι μέρος ενός εκτεινόμενου δέντρου, τότε αυτό είναι προφανές, γιατί τότε μόνο l(q) = l(p) + 1. Εάν αυτό δεν συμβαίνει, τότε γράφουμε τις διαδρομές από τη ρίζα r έως οι κορυφές p,q ως R p και R q . Έστω επίσης R r η διαδρομή από το q πίσω στο r στο γράφημα (το γράφημα είναι συνδεδεμένο, άρα υπάρχει). Τότε μπορούμε να γράψουμε δύο κύκλους: R p p-->q R r , και R q R r . Σύμφωνα με τη συνθήκη, τα μήκη αυτών των κύκλων διαιρούνται με το N, αφαιρώντας και ακυρώνοντας τις συνολικές τιμές, προκύπτει ότι l(p)+1 = l(q) mod N, το οποίο έπρεπε να αποδειχθεί.

Σταθερή φιλία και επαγωγή

Ας δοθεί λίγος χρωματισμός του γραφήματος G. Δύο κορυφές ονομάζουμε φίλους p,q αν κάποια λέξη w τις φέρει στην ίδια κορυφή: pw = qw. Ας ονομάσουμε p,q εχθρούς αν «ποτέ δεν συναντηθούν». Ας ονομάσουμε p,q σταθερούς φίλους αν μετά την εκτέλεση οποιασδήποτε λέξης w παραμείνουν φίλοι: το pw μπορεί να μην έρθει στην ίδια κορυφή με το qw, αλλά μετά από λίγο w" μπορεί. Οι σταθεροί φίλοι δεν γίνονται ποτέ εχθροί.

Η σχέση σταθερότητας μεταξύ των κορυφών είναι, πρώτον, μια ισοδυναμία (είναι αντανακλαστική, συμμετρική και μεταβατική), και δεύτερον, διατηρείται από τη δομή του γραφήματος: αν τα p,q είναι σταθεροί φίλοι, το p συνδέεται με μια ακμή με το p" , q με q", και αυτές οι άκρες έχουν το ίδιο χρώμα, μετά το p" και το q" είναι επίσης σταθεροί φίλοι. Αυτό σημαίνει ότι η σταθερή φιλία είναι μαθηματική αναλογίακαι μπορεί να χωριστεί σε: δημιουργήστε ένα νέο γράφημα G", του οποίου οι κορυφές θα είναι σταθερές τάξεις ισοδυναμίας φιλίας στο G. Εάν υπάρχει τουλάχιστον ένα σταθερό ζεύγος στο G, τότε το G" θα είναι μικρότερο από το G σε μέγεθος. Επιπλέον, εάν στο αρχικό γράφημα G από κάθε κορυφή έχει d άκρες, τότε στο G" θα είναι το ίδιο. Για παράδειγμα, αν το P είναι κορυφή ενός νέου γραφήματος, που είναι η κλάση ισοδυναμίας των αρχικών κορυφών p1, p2... , και α είναι οποιοδήποτε χρώμα, τότε οι άκρες p1--α--> q1, p2---α-->q2, κλπ. όλες οδηγούν στις κορυφές q1, q2..., οι οποίες βρίσκονται σε σταθερή φιλία με κάθε άλλο, και επομένως βρίσκονται σε μια νέα κορυφή Q, έτσι ώστε όλες αυτές οι ακμές να γίνουν μια νέα ακμή P --α-->Q Και ούτω καθεξής για καθένα από τα χρώματα d.

Επιπλέον, εάν το G ήταν μη περιοδικό, τότε το G" είναι. Επειδή - χρησιμοποιώντας τον εναλλακτικό μας ορισμό της περιοδικότητας - οποιοσδήποτε κύκλος στο G μετατρέπεται σε κύκλο στο G", οπότε αν όλα τα μήκη κύκλου στο G" διαιρούνται με n > 1, τότε το ίδιο ισχύει για όλους τους κύκλους στο G. Άρα η περιοδικότητα του G» συνεπάγεται την περιοδικότητα του G.

Ας υποθέσουμε ότι στο G" καταφέραμε να βρούμε έναν συγχρονιζόμενο χρωματισμό. Τώρα μπορεί να χρησιμοποιηθεί στο G αντί για τον χρωματισμό με τον οποίο ξεκινήσαμε: οποιαδήποτε άκρη p-->q θα λάβει ένα νέο χρώμα σύμφωνα με το νέο χρώμα της άκρης P-->Q. Λίγο πιο συγκεκριμένα, θα πρέπει να το πούμε: σε κάθε κορυφή P του γραφήματος G" δίνεται ένας νέος χρωματισμός από κάποια μετάθεση όλων των χρωμάτων π P: η άκρη που βάφτηκε με το χρώμα α παίρνει ένα νέο χρώμα π P (α). Στη συνέχεια, στο αρχικό γράφημα G, σε κάθε κορυφή p από την τάξη σταθερότητας P, εφαρμόζουμε την ίδια μετάθεση π P για να ξαναχρωματίσουμε τις άκρες της. Ο νέος χρωματισμός του γραφήματος G ορίζει γενικά κάποιες νέες έννοιες «φιλίας», «εχθρότητας» και «σταθερότητας» που δεν είναι πανομοιότυπες με τις αρχικές. Ωστόσο, αν δύο κορυφές p, q ήταν σταθεροί φίλοι στον παλιό χρωματισμό - ανήκαν στην ίδια τάξη P - τότε θα παραμείνουν σταθεροί φίλοι στη νέα. Αυτό συμβαίνει επειδή οποιαδήποτε ακολουθία w που φέρνει το p,q σε μία κορυφή μπορεί να «μεταφερθεί» από τον παλιό χρωματισμό στη νέα, ή αντίστροφα, χρησιμοποιώντας τη μετάθεση π P σε κάθε κορυφή του p κατά μήκος του δρόμου. Εφόσον τα p,q είναι σταθερά στον παλιό χρωματισμό και παραμένουν έτσι "σε όλη τη διαδρομή", κάθε ενδιάμεσο ζεύγος κορυφών p n , q n στο δρόμο από το p,q προς την κοινή κορυφή θα είναι σταθερό, δηλ. βρίσκονται μέσα στην ίδια κορυφή P n και επομένως λαμβάνουν την ίδια μετάθεση π P n .

Ο νέος χρωματισμός συγχρονίζεται για το G", δηλαδή κάποια ακολουθία w φέρνει όλες τις κορυφές σε μία κορυφή P. Εάν τώρα εφαρμόσουμε το w στον νέο χρωματισμό στο G, τότε όλες οι κορυφές συγκλίνουν κάπου "μέσα στο P". Όπως αναφέρθηκε παραπάνω, όλες οι κορυφές εντός της κλάσης P παραμένουν σταθερές στον νέο χρωματισμό, πράγμα που σημαίνει ότι μπορούμε τώρα να συνεχίσουμε το w, συγκεντρώνοντας τα υπόλοιπα ζεύγη κορυφών που είναι ακόμα ξεχωριστά, ξανά και ξανά, μέχρις ότου όλα συγκλίνουν σε μια κορυφή G. Έτσι, το νέο Ο χρωματισμός συγχρονίζεται για το G.

Από όλα αυτά προκύπτει ότι για να αποδειχθεί το θεώρημα, αρκεί να αποδειχθεί ότι σε οποιοδήποτε γράφημα που πληροί τις προϋποθέσεις, υπάρχει ένας χρωματισμός στον οποίο υπάρχει ένα ζευγάρι σταθερών φίλων. Επειδή τότε είναι δυνατό να πάμε από το γράφημα G στο γράφημα G" μικρότερο σε μέγεθος, και επίσης πληροί όλες τις προϋποθέσεις. Χρησιμοποιώντας το επαγωγικό όρισμα, μπορούμε να υποθέσουμε ότι για γραφήματα μικρότερου μεγέθους το πρόβλημα έχει ήδη λυθεί και τότε ο χρωματισμός συγχρονισμού για το G" θα συγχρονίζεται επίσης για το G .

Κλίκες και μάξιμαλ σετ

Για οποιοδήποτε υποσύνολο Α των κορυφών του γραφήματος και της λέξης w, το Aw δηλώνει το σύνολο των κορυφών στο οποίο θα φτάσουμε, ξεκινώντας από όλες τις κορυφές του Α και ακολουθώντας τη λέξη w. Αν ξεκινήσουμε από όλες τις κορυφές του γραφήματος γενικά, τότε το συμβολίζουμε με Gw. Σε αυτόν τον συμβολισμό, ο συγχρονισμός χρωματισμού σημαίνει ότι υπάρχει ένα w έτσι ώστε το Gw να είναι ένα σύνολο ενός στοιχείου.

Εάν το σύνολο κορυφής A έχει τη μορφή Gw για κάποιο w, και επιπλέον οποιεσδήποτε δύο κορυφές στο A είναι εχθροί, δηλ. ποτέ να μην συγκλίνουμε, ας καλέσουμε τον Α κλίκα. Οι κλίκες υπάρχουν επειδή μπορούμε πάντα να ξεκινήσουμε με έναν ακέραιο αριθμό G, να πάρουμε ένα ζευγάρι κορυφών φίλων, να διασχίσουμε το w που τις συνδέει και να μειώσουμε τον αριθμό των κορυφών κατά μία. συνεχίστε έτσι μέχρι να μείνουν μόνο εχθροί ή να μείνει μόνο μία κορυφή - επίσης σε αυτήν την περίπτωση μια κλίκα, απλώς ασήμαντη.

Αν το Α είναι κλίκα, τότε για οποιαδήποτε λέξη το w Aw είναι επίσης κλίκα. αυτό είναι ξεκάθαρο γιατί οι εχθροί παραμένουν εχθροί. Αν x είναι οποιαδήποτε κορυφή του γραφήματος, τότε υπάρχει μια κλίκα που περιέχει x. Αυτό προκύπτει από το γεγονός ότι υπάρχει κάποια κλίκα Α (βλ. την προηγούμενη παράγραφο). αν το p είναι κορυφή σε αυτό, τότε υπάρχει μια λέξη w που οδηγεί από το p στο x, επειδή συνδεδεμένο γράφημα? τότε το Aw είναι μια κλίκα που περιλαμβάνει το x.

Τα κλικ θα μας βοηθήσουν να αποδείξουμε ότι υπάρχει χρωματισμός με σταθερούς φίλους - σύμφωνα με την προηγούμενη ενότητα, αυτό αρκεί για να αποδείξουμε το θεώρημα. Σε όλη αυτή την ενότητα, θα αποδείξουμε ότι αν υπάρχουν δύο κλίκες Α και Β, έτσι ώστε όλες οι κορυφές σε αυτές να είναι κοινές, εκτός από μία στο Α και μία στο Β, τότε αυτές οι δύο κορυφές είναι σταθεροί φίλοι. Έτσι, το πρόβλημα περιορίζεται στην εύρεση ενός χρωματισμού που περιέχει τέτοιες κλίκες Α και Β.

Για να κατανοήσετε καλύτερα πώς λειτουργούν οι κλίκες, είναι χρήσιμο να αντιστοιχίσετε βάρη σε κορυφές σε ένα γράφημα. Ας δείξουμε ότι έχουμε έναν τρόπο να ορίσουμε ένα θετικό βάρος w(x) σε κάθε κορυφή x, έτσι ώστε αν για οποιαδήποτε κορυφή x αθροίστε τα βάρη όλων των κορυφών που έχουν ακμές σε x, τότε παίρνουμε d*w(x), όπου d είναι ο αριθμός των ακμών από κάθε κορυφή. Αυτό προκύπτει από τη γραμμική άλγεβρα, και αν δεν ξέρετε τι είναι η ιδιοτιμή, παραλείψτε το υπόλοιπο αυτής της παραγράφου και λάβετε υπόψη την ύπαρξη αυτού του w(x) στην πίστη. Αν M είναι ο πίνακας του γραφήματος G (το κελί (i,j) είναι 1 αν υπάρχει ακμή i-->j, και 0 αν δεν υπάρχει τέτοια ακμή), τότε το w(x), όπως τα περιέγραψα, είναι στοιχεία του ιδιοδιανύσματος αριστεράαυτός ο πίνακας για την ιδιοτιμή d. Γνωρίζουμε ότι ένα τέτοιο διάνυσμα υπάρχει επειδή το d είναι μια ιδιοτιμή: έχει ένα τετριμμένο ιδιοδιάνυσμα στα δεξιά(1,1,....1) - αυτό προκύπτει αμέσως από το γεγονός ότι ακριβώς d άκρες βγαίνουν από κάθε κορυφή.

Εάν το A είναι οποιοδήποτε σύνολο κορυφών, τότε το w(A) υποδηλώνει το άθροισμα των βαρών όλων των κορυφών στο A. και w(G) είναι το άθροισμα των βαρών όλων των κορυφών του γραφήματος. Επιπλέον, αν το s είναι οποιαδήποτε λέξη, τότε ας As -1 υποδηλώνει το σύνολο των κορυφών στις οποίες έρχεστε από το A εάν πηγαίνετε "στην αντίθετη κατεύθυνση" κατά μήκος του s, σε κάθε βήμα αντικαθιστώντας κάθε κορυφή με αυτές τις κορυφές (αν υπάρχουν) που του πηγαίνουν στο κατάλληλο χρώμα.

Ας εξετάσουμε τώρα όλα τα σύνολα κορυφών που μπορούν να συγκεντρωθούν σε ένα σημείο, δηλ. Ένα τέτοιο που, για μερικά w, το Aw περιέχει μόνο μία κορυφή. Τα σύνολα Α που μεταξύ όλων αυτών έχουν το μέγιστο βάρος w(A) ονομάζονται μέγιστα σύνολα. Εάν ο χρωματισμός συγχρονίζεται, τότε ολόκληρο το γράφημα G είναι ένα μέγιστο σύνολο (μοναδικό), αλλά διαφορετικά δεν είναι.

Εάν το A είναι οποιοδήποτε σύνολο κορυφών, τότε το άθροισμα όλων των w(Aα -1), όπου το α διατρέχει όλα τα d χρώματα, είναι ίσο με d*w(A) - αυτή είναι απλώς μια γενίκευση της κύριας ιδιότητας βάρους από ένα κορυφή στο σύνολο των κορυφών A. Εάν, επιπλέον, επιπλέον, το A είναι το μέγιστο σύνολο, τότε καθένα από τα w(Aα -1) δεν μπορεί να είναι μεγαλύτερο από το w(A), επειδή και αυτά τα σύνολα συγκλίνουν σε μία κορυφή. Και επειδή το άθροισμα d αυτών των βαρών είναι ίσο με d*w(A), αποδεικνύεται ότι καθένα από αυτά είναι ίσο με w(A), και όλα αυτά τα σύνολα είναι επίσης μέγιστα. Αυτό σημαίνει αμέσως ότι αν το A είναι μέγιστο, τότε το Aw -1 είναι επίσης μέγιστο για οποιαδήποτε λέξη w.

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

Ας έχουμε ένα σύνολο μέγιστων συνόλων A 1 ...A n που δεν τέμνονται σε ζεύγη και ανάγονται σε μονές κορυφές a 1 ...a n με την ίδια λέξη w (στην αρχική περίπτωση θα υπάρχουν n=1 και μόνο ένα σετ, οπότε είναι εύκολο να ξεκινήσει). Είναι σαφές ότι όλα τα a 1 ...a n διαφέρουν μεταξύ τους, γιατί διαφορετικά θα ήταν δυνατό να επεκταθεί το μέγιστο σύνολο ακόμη περισσότερο από στοιχεία ενός άλλου με την ίδια τελική κορυφή. Ας υποθέσουμε ότι όλα τα A i μαζί δεν έχουν εξαντλήσει ακόμη όλες τις κορυφές του G και έστω x μια κορυφή έξω από όλα τα A i . Εφόσον το γράφημα είναι συνδεδεμένο, υπάρχει κάποια διαδρομή h από το 1 στο x. Τότε n μέγιστα σύνολα A i h -1 w -1 πηγαίνουν με τη λέξη whw στις τελικές κορυφές a 1 ...a n , και το μέγιστο σύνολο A 1 πηγαίνει σε κάποια κορυφή Awhw = (Aw)hw = (a 1 h)w = xw. Αυτή η κορυφή xw πρέπει επίσης να είναι διαφορετική από όλα τα a 1 ...a n, γιατί διαφορετικά το μέγιστο σύνολο A i θα μπορούσε να συμπληρωθεί με το στοιχείο x. Και δεδομένου ότι όλα αυτά τα n + 1 σύνολα - όλα τα A i h -1 w -1 συν A 1 - πηγαίνουν κατά μήκος whw σε διαφορετικές κορυφές, είναι όλα χωριστά κατά ζεύγη. Θα συνεχίσουμε αυτή την επέκταση μέχρι να μην υπάρχουν κορυφές εκτός του συνόλου.

Έτσι μπορούμε να καλύψουμε ολόκληρο το γράφημα G με ασύνδετα μέγιστα σύνολα. Εφόσον είναι μέγιστα, έχουν όλα το ίδιο συνολικό w max , και επομένως ο αριθμός τους στην κάλυψη είναι N max = w(G)/w max .

Τώρα εξετάστε οποιοδήποτε σύνολο Α που αποτελείται από ζεύγη εχθρούς. Για παράδειγμα, μια κλίκα είναι ένα παράδειγμα ενός τέτοιου συνόλου (και έχει επίσης τη μορφή Gw). Δεν μπορεί να υπάρχει ένα ζευγάρι εχθρών μέσα στο μέγιστο σετ, γιατί τότε δεν θα μπορούσε να συγκλίνει. Ως εκ τούτου, σε μια κάλυψη από N max μέγιστα σύνολα, το καθένα περιέχει το πολύ ένα μέλος του A, άρα το μέγεθος του A είναι το πολύ N max . Συγκεκριμένα, αυτό είναι ένα ανώτατο όριο στο μέγεθος οποιασδήποτε κλίκας.

Έστω A μια κλίκα της μορφής Gw, όπου w είναι κάποια λέξη. Τότε G = Aw -1 , και κατά συνέπεια το w(G) είναι ίσο με το άθροισμα w(aw -1), όπου το a διατρέχει όλες τις κορυφές του A. Ο αριθμός των όρων, σύμφωνα με την προηγούμενη παράγραφο, είναι το πολύ N max , και κάθε σύνολο aw -1 μπορεί να μειωθεί σε ένα σημείο (στο σημείο a με τη λέξη w), επομένως το βάρος του δεν είναι μεγαλύτερο από το μέγιστο w max . Εφόσον ολόκληρο το άθροισμα είναι w(G) = N max *w max , συμπεραίνουμε ότι ο αριθμός των όρων είναι ακριβώς N max , και κάθε όρος είναι ακριβώς w max . Έχουμε αποδείξει ότι όλα τα κλικ έχουν το ίδιο μέγεθος: ακριβώς N μέγ. στοιχεία.

Έστω δύο κλίκες Α και Β, έτσι ώστε μέσα στο Α όλα τα στοιχεία να είναι κοινά με το Β, εκτός από ένα: |A| - |A∩B| = 1.

Εφόσον το Α και το Β έχουν το ίδιο μέγεθος, έχουμε και |Β| - |A∩B| = 1, δηλ. Τα A και B έχουν όλα τα κοινά στοιχεία εκτός από μια κορυφή p στο A και μια κορυφή q στο B. Θα θέλαμε να αποδείξουμε ότι αυτές οι κορυφές p,q είναι σταθεροί φίλοι. Αν δεν είναι έτσι, τότε κάποια λέξη w τους κάνει εχθρούς, δηλ. Το pw και το qw είναι εχθροί. Όπως φαίνεται παραπάνω, το Aw και το Bw είναι επίσης κλίκες, και είναι προφανές ότι και πάλι έχουν όλα τα κοινά στοιχεία, εκτός από τους εχθρούς pw και qw. Τότε το σύνολο Aw ∪ Bw είναι το σύνολο των ζευγών εχθρών. Πράγματι, σε αυτό όλα τα στοιχεία του Aw είναι εχθροί κατά ζεύγη, επειδή είναι μια κλίκα. Το ίδιο ισχύει και για τα στοιχεία Bw. και έμειναν μόνο δυο pw, qw - επίσης εχθροί. Αλλά αυτό το σύνολο έχει N max +1 στοιχεία, και παραπάνω δείξαμε ότι οποιοδήποτε σύνολο εχθρών κατά ζεύγη δεν μπορεί να έχει περισσότερα από N max στοιχεία. Αυτό είναι μια αντίφαση, και επομένως το pw και το qw δεν μπορούν να είναι εχθροί για κανένα w. Με άλλα λόγια, το p και το q είναι σταθεροί φίλοι.

Εκτεινόμενα γραφήματα και κλίκες

Ας πάρουμε όλες τις κορυφές από ένα δεδομένο γράφημα G και ας επιλέξουμε μόνο μία εξερχόμενη ακμή από κάθε κορυφή. Μια τέτοια επιλογή ορίζει ένα υπογράφημα, το οποίο ονομάζουμε εκτεινόμενο γράφημα(εκτεινόμενο γράφημα). Μπορεί να υπάρχουν πολλά διαφορετικά εκτεινόμενα γραφήματα, αλλά ας σκεφτούμε λίγο πώς φαίνονται. Ας υπάρχει κάποιο εκτεινόμενο γράφημα R. Αν πάρουμε οποιαδήποτε κορυφή x σε αυτό και αρχίσουμε να ακολουθούμε τις άκρες της, τότε κάθε φορά θα έχουμε τη μόνη επιλογή, γιατί στο R μόνο μία ακμή βγαίνει από κάθε κορυφή και αργά ή γρήγορα θα κλείσιμο του κύκλου. Ίσως αυτός ο κύκλος να μην κλείσει στο x, αλλά να κλείσει κάπου "παραπέρα" - για παράδειγμα, x-->y-->z-->s-->y. Τότε από το x θα οδηγήσει την «ουρά» σε αυτόν τον κύκλο. Αν ξεκινήσουμε από κάποια άλλη κορυφή, σίγουρα θα φτάσουμε επίσης σε έναν κύκλο - αυτόν ή κάποιο άλλο. Αποδεικνύεται ότι οποιαδήποτε κορυφή του R είτε βρίσκεται σε έναν κύκλο (από τον οποίο μπορεί να υπάρχουν αρκετοί), είτε είναι μέρος της «ουράς» που οδηγεί στον κύκλο. Αυτό σημαίνει ότι το R μοιάζει με αυτό: ένας ορισμένος αριθμός κύκλων και ένας ορισμένος αριθμός «ανεστραμμένων» δέντρων είναι χτισμένοι πάνω τους: κάθε δέντρο δεν ξεκινά, αλλά τελειώνει σε μια «ρίζα» που βρίσκεται σε έναν από τους κύκλους.

Σε κάθε κορυφή του γραφήματος μπορούμε να αντιστοιχίσουμε επίπεδο, που αντιστοιχεί στην απόστασή του από τον κύκλο στο δεδομένο εκτεινόμενο γράφημα R. Οι κορυφές που βρίσκονται στον κύκλο έχουν επίπεδο 0 και οι κορυφές που βρίσκονται στο δέντρο που συνδέεται με τον κύκλο λαμβάνουν επίπεδο ίσο με την απόσταση του δέντρου τους από τη "ρίζα «ξαπλωμένος στον κύκλο. Μερικές κορυφές του γραφήματος μας έχουν μέγιστο επίπεδο L. Ίσως είναι γενικά ίσο με 0 - δηλ. δεν υπάρχουν δέντρα, μόνο κύκλοι. Ίσως είναι μεγαλύτερο από το μηδέν, και οι κορυφές αυτού του μέγιστου επιπέδου βρίσκονται σε όλα τα είδη των διαφορετικών δέντρων που συνδέονται με διαφορετικούς κύκλους ή με έναν.

Θέλουμε να επιλέξουμε ένα εκτεινόμενο γράφημα R με τέτοιο τρόπο ώστε όλες οι κορυφές του μέγιστου επιπέδου βρίσκονται στο ίδιο δέντρο. Διαισθητικά, μπορεί κανείς να πιστέψει ότι αυτό μπορεί να γίνει, γιατί αν δεν συμβαίνει αυτό - για παράδειγμα, είναι διάσπαρτα σε διαφορετικά δέντρα - τότε μπορεί κανείς να επιλέξει μία από αυτές τις μέγιστες κορυφές x και να αυξήσει το επίπεδό της προσαρτώντας στο R κάποια άκρη που πηγαίνει έως x. Τότε θα πρέπει να πεταχτεί κάποια άλλη άκρη, και δεν είναι σίγουρο ότι δεν θα βλάψει κάτι άλλο... αλλά αυτό είναι τεχνικό θέμα, για περισσότερα αργότερα. Απλώς προσπαθώ να πω ότι διαισθητικά δεν φαίνεται πολύ περίπλοκο.

Προς το παρόν, ας υποθέσουμε ότι μπορούμε να επιλέξουμε το R έτσι ώστε όλες οι κορυφές του μέγιστου επιπέδου να βρίσκονται στο ίδιο δέντρο. Αυτό το δέντρο θεωρείται ότι είναι μη τετριμμένο, δηλ. μέγιστο επίπεδο L > 0. Με βάση αυτή την υπόθεση, θα κατασκευάσουμε έναν χρωματισμό με τις κλίκες Α και Β, ικανοποιώντας τη συνθήκη της προηγούμενης ενότητας, και αυτό θα αποδείξει ότι αυτός ο χρωματισμός έχει ένα σταθερό ζευγάρι φίλων.

Ο χρωματισμός θα είναι ο εξής: επιλέγουμε κάποιο χρώμα α και χρωματίζουμε όλες τις άκρες στο γράφημα R με αυτό το χρώμα και όλες τις άλλες άκρες στο γράφημα G - σε κάποια άλλα χρώματα με οποιονδήποτε τρόπο (αν υπάρχει μόνο ένα χρώμα, τότε το R συμπίπτει με το G οπότε δεν υπάρχει πρόβλημα). Έτσι, οι λέξεις που αποτελούνται από το χρώμα α «προωθούν» τις κορυφές του R κατά μήκος των δέντρων τους προς τους κύκλους και μετά τις οδηγούν κατά μήκος των κύκλων. Τέτοια λόγια χρειαζόμαστε μόνο.

Έστω x οποιαδήποτε κορυφή του μέγιστου επιπέδου L στο R και έστω K κάθε κλίκα που περιλαμβάνει x. ξέρουμε ότι υπάρχει μια τέτοια κλίκα. Μπορεί το K να περιλαμβάνει κάποια άλλη κορυφή μέγιστου επιπέδου L; Σύμφωνα με την υπόθεσή μας, όλες αυτές οι κορυφές βρίσκονται στο ίδιο δέντρο με το x, πράγμα που σημαίνει ότι η λέξη α L τις οδηγεί στην ίδια θέση με το x - δηλαδή, στη ρίζα αυτού του δέντρου που βρίσκεται στον κύκλο. Επομένως, όλες αυτές οι κορυφές είναι φίλοι του x και επομένως δεν μπορούν να βρίσκονται στην ίδια κλίκα με αυτό. Επομένως, εκτός από το x, το K μπορεί να περιλαμβάνει μόνο κορυφές χαμηλότερου επιπέδου.

Ας δούμε το σύνολο A = Kα L-1 . Αυτή είναι επίσης μια κλίκα, και σε αυτήν όλες οι κορυφές, εκτός από το x, έχουν φτάσει σε κάποιους από τους κύκλους τους στο R, επειδή όλες οι κορυφές του A, εκτός από το x, έχουν επίπεδο μικρότερο από το L. Μόνο το x είναι ακόμα εκτός του κύκλου, σε απόσταση ακριβώς 1 από τη ρίζα του στον κύκλο. Τώρα ας πάρουμε έναν αριθμό m που είναι πολλαπλάσιο όλων των μηκών κύκλου στο R - για παράδειγμα, το γινόμενο όλων των μηκών κύκλου. Το m έχει τέτοιο χαρακτηριστικό ώστε αν μια κορυφή y βρίσκεται σε έναν κύκλο στο R, τότε η λέξη α m την επιστρέφει στη θέση της: yα m = y. Ας δούμε την κλίκα B = Aα m . Όλες οι κορυφές του Α, εκτός από το x, βρίσκονται σε κύκλους και επομένως παρέμειναν εκεί στο Β. και μόνο το x μπήκε τελικά στον κύκλο του και εγκαταστάθηκε κάπου εκεί. Αυτό σημαίνει ότι η τομή των Α και Β περιέχει όλες τις κορυφές του Α, εκτός από μία: |A| - |A∩B| = 1. Αλλά αυτό σημαίνει απλώς, σύμφωνα με την προηγούμενη ενότητα, ότι ο χρωματισμός μας έχει ένα σταθερό ζεύγος, το οποίο έπρεπε να αποδειχτεί.

Χτίζοντας το μέγιστο επίπεδο.

Μένει να αποδείξουμε ότι είναι πάντα δυνατό να επιλέξουμε ένα εκτεινόμενο γράφημα R με τέτοιο τρόπο ώστε να έχει ένα μη τετριμμένο μέγιστο επίπεδο L > 0, και όλες οι κορυφές αυτού του επιπέδου να βρίσκονται στο ίδιο δέντρο.

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

Θα χρειαστούμε δύο περιορισμούς που μπορούμε να επιβάλουμε στο γράφημα G. Πρώτον, λέμε ότι δεν υπάρχουν βρόχοι στο G, δηλ. ακμές από μια κορυφή στην ίδια κορυφή. Το θέμα είναι ότι αν υπάρχει βρόχος στο γράφημα, τότε είναι πολύ εύκολο να βρεις τον χρωματισμό συγχρονισμού με άλλο τρόπο. Ας χρωματίσουμε αυτόν τον βρόχο σε κάποιο χρώμα α, και μετά, πηγαίνοντας από αυτήν την κορυφή προς την αντίθετη κατεύθυνση "κόντρα στα βέλη", θα χρωματίσουμε τις άκρες έτσι ώστε το χρώμα α να οδηγεί πάντα σε αυτήν την κορυφή. Επειδή το γράφημα είναι συνδεδεμένο, αυτό είναι εύκολο να τακτοποιηθεί και, στη συνέχεια, ο βρόχος διασφαλίζει ότι κάποια ισχύς του α θα φέρει ολόκληρο το γράφημα σε αυτήν την κορυφή.

Στη συνέχεια, ας υποθέσουμε για ένα δευτερόλεπτο ότι από κάποια κορυφή p, όλες οι άκρες d οδηγούν στην ίδια κορυφή q. Αυτό επιτρέπεται από τις συνθήκες, αλλά σε αυτήν την περίπτωση θα ονομάσουμε αυτό το σύνολο ακμών δέσμη. Ο δεύτερος περιορισμός μας είναι αυτός: δεν υπάρχει κορυφή r στην οποία οδηγούν δύο σύνδεσμοι από διαφορετικές κορυφές p και q. Γιατί μπορούμε να το επιβάλλουμε; Διότι αν υπάρχουν σύνδεσμοι από το p και το q στο r, τότε για οποιονδήποτε χρωματισμό το p,q θα συγκλίνει στην κορυφή r μετά το πρώτο χρώμα, και επομένως είναι σταθεροί φίλοι. Έτσι, σε αυτήν την περίπτωση, δεν χρειαζόμαστε όλη την κατασκευή εκτεταμένων γραφημάτων και κλίκων, αποκτάμε αμέσως σταθερούς φίλους. Επομένως, μπορούμε να υποθέσουμε ότι αυτό δεν ισχύει.

Τέλος, ας αποδείξουμε ότι υπάρχει πάντα ένα εκτεινόμενο γράφημα R στο οποίο δεν βρίσκονται όλες οι κορυφές σε κύκλους, αλλά υπάρχουν μερικά μη τετριμμένα δέντρα. Επιλέγουμε λίγο R και υποθέτουμε ότι όλες οι κορυφές σε αυτό βρίσκονται σε κύκλους. Εάν στο γράφημα G όλες οι άκρες βρίσκονται σε δέσμες - δηλ. πάντα όλες οι d άκρες που εξερχόντουσαν από μια κορυφή οδηγούσαν στην ίδια κορυφή - τότε η επιλογή R θα περιλάμβανε απλώς την επιλογή μιας ακμής από κάθε δέσμη. Σε αυτήν την περίπτωση, θα μπορούσε να υπάρχει μόνο ένας κύκλος στο R (εξάλλου, πολλοί κύκλοι στο R δεν μπορούσαν να συνδεθούν μεταξύ τους σε ένα συνδεδεμένο γράφημα G - όλες οι ακμές του G συνδέουν μόνο τις ίδιες κορυφές με τις άκρες του R, επειδή αυτές οι είναι σύνδεσμοι - και αφού το G είναι συνδεδεμένο, αυτό είναι αδύνατο), και οποιοσδήποτε κύκλος στο G απλώς επιλέγει άλλες άκρες από τους συνδέσμους αυτού του κύκλου, αλλά στην πραγματικότητα είναι ο ίδιος κύκλος, το ίδιο μήκος. Αλλά αυτό σημαίνει ότι τα μήκη όλων των κύκλων στο G διαιρούνται με αυτό το μήκος, το οποίο απλώς έρχεται σε αντίθεση με τη μη περιοδικότητα του G. Επομένως, δεν μπορεί να είναι ότι στο G όλες οι ακμές βρίσκονται σε δεσμούς, πράγμα που σημαίνει ότι υπάρχουν περίπου δύο άκρες p -- >q στο R, και p-->s έξω από το R (χρειαζόμασταν ένα μεγάλο επιχείρημα σχετικά με τις συνδέσεις για να αποδείξουμε ότι κάποια ακμή από το p όχι μόνο δεν βρίσκεται στο εκτεινόμενο γράφημα, αλλά οδηγεί επίσης σε μια άλλη κορυφή s). Στη συνέχεια αντικαθιστούμε το p-->q με το p-->s, και αυτό θα «σπάσει» τον κύκλο, δημιουργώντας κάποια μη τετριμμένη ουρά σε αυτόν. Αυτή η ουρά θα μας δώσει ένα μη τετριμμένο δέντρο στο νέο γράφημα.

Τώρα, από όλα τα εκτεινόμενα γραφήματα R που έχουν μη τετριμμένα δέντρα, μπορούμε να επιλέξουμε κάποιο R που έχει τον μέγιστο αριθμό κορυφών στους κύκλους. Τ.ε. έχει κορυφές όχι σε κύκλους, αλλά εκτός από αυτόν τον περιορισμό, ο αριθμός των κορυφών στους κύκλους μεγιστοποιείται. Αυτό το γράφημα έχει μερικές κορυφές μέγιστου επιπέδου L και μπορούμε να υποθέσουμε ότι βρίσκονται σε δέντρα που οδηγούν σε διαφορετικές ρίζες, διαφορετικά έχουμε ήδη πετύχει αυτό που χρειαζόμαστε. Επιλέγουμε μια τέτοια κορυφή x. Θέλουμε να αλλάξουμε το γράφημα έτσι ώστε αυτή η κορυφή να γίνει μέρος μιας μεγαλύτερης διαδρομής στο δέντρο, μεγαλύτερη από το L, και τα υπόλοιπα δέντρα να μην αλλάξουν, και τότε το μέγιστο επίπεδο θα είναι μόνο σε ένα δέντρο, το οποίο είναι θέλω. Μπορείτε να αλλάξετε το γράφημα με τρεις τρόπους:

α) Πάρτε κάποια ακμή y-->x, και προσθέστε την στο R, και απορρίψτε την ακμή y-->z που υπάρχει εκεί.
β) πάρτε την ακμή b-->r, η οποία είναι μόλις η τελευταία στη διαδρομή από το x στον κύκλο της (r στον κύκλο), και απορρίψτε την και προσθέστε κάποια άλλη b-->z.
γ) πάρτε την άκρη c-->r, που είναι μέρος του κύκλου, και απορρίψτε την και προσθέστε κάποια άλλη c-->z.

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

Ενημέρωση, μια εβδομάδα αργότερα:Ωστόσο, αποφάσισα να κάνω αυτό το λήμμα εντελώς αυτάρκης και επίσης να επαναλάβω την απόδειξη του λήμματος στο οποίο αναφέρθηκα στην προηγούμενη παράγραφο. Θα ήταν καλύτερο να το κάνουμε αυτό με ένα διάγραμμα, αλλά δεν θέλω να το σχεδιάσω ή να το αποκόψω από το άρθρο, οπότε θα προσπαθήσω με λόγια. Λοιπόν, ας φανταστούμε ότι έχουμε ένα εκτεινόμενο γράφημα R, το οποίο έχει μη τετριμμένα δέντρα, και από όλα αυτά τα γραφήματα σε αυτό, ο μέγιστος αριθμός κορυφών βρίσκεται σε κύκλους. Στόχος μας είναι να μετατρέψουμε το R σε ένα εκτεινόμενο γράφημα στο οποίο όλες οι κορυφές του μέγιστου επιπέδου βρίσκονται στο ίδιο δέντρο. μόλις πάρουμε ένα τέτοιο γράφημα στη διαδικασία της προσπάθειας, τελειώνουμε αμέσως (και δεν μας νοιάζει που μπορεί να χαθεί το μέγιστο γράφημα ως προς τον αριθμό των κορυφών στους κύκλους, δεν είναι σημαντικό για εμάς από μόνο του, το χρησιμοποιούμε μόνο στη διαδικασία). Έστω x η κορυφή του μέγιστου επιπέδου L, T το δέντρο στο οποίο βρίσκεται, r η κορυφή στον κύκλο C όπου τελειώνει το T, b-->r το τελευταίο άκρο πριν από το r στη διαδρομή από το x στον κύκλο C. Μπορούμε να υποθέσουμε ότι υπάρχουν ακόμα μερικά δέντρα που εντάσσονται σε αυτόν τον κύκλο ή άλλα που έχουν κορυφές επιπέδου L - διαφορετικά όλα έχουν ήδη γίνει. Από αυτό προκύπτει ότι αν καταφέρουμε να πάρουμε ένα δέντρο από το T με στοιχείο μεγαλύτερου βαθμού από το L και να μην επιμηκύνουμε αυτά τα άλλα δέντρα, τότε τελειώσαμε.

Αρχικά, ας προσπαθήσουμε να εκτελέσουμε τη λειτουργία α) παραπάνω: πάρτε κάποια ακμή y-->x στο G - υπάρχει, επειδή το γράφημα είναι συνδεδεμένο και χωρίς βρόχους και δεν βρίσκεται στο R, γιατί x μέγιστο επίπεδο. Ας το προσθέσουμε στο R και ας πετάξουμε λίγο y-->z που ήταν εκεί πριν. Εάν το y βρίσκεται στο δέντρο T, τότε το y-->x κλείνει έναν νέο κύκλο και στο νέο γράφημα, περισσότερες κορυφές βρίσκονται σε κύκλους και υπάρχουν ακόμα μη τετριμμένα δέντρα (τουλάχιστον εκείνα τα άλλα που ήταν στο R), το οποίο έρχεται σε αντίθεση με τη μέγιστη τιμή του R. Εάν το y δεν βρίσκεται στο T και το y-->z δεν είναι μέρος του κύκλου C, τότε η διαγραφή του y-->z δεν σπάει αυτόν τον κύκλο και η προσθήκη του y-->x επιμηκύνεται το μέγιστο επίπεδο του δέντρου T κατά τουλάχιστον ένα, και τα άλλα δέντρα δεν επιμηκύνονται, οπότε τελειώσαμε. Η επιλογή που απομένει είναι όταν το y-->z βρίσκεται στον κύκλο C, ο οποίος τώρα έχει σπάσει, και έχει σχηματιστεί ένας νέος κύκλος: από r στο y, μετά y-->x, μετά από x στο r κατά μήκος του προηγούμενου δέντρου. Το μήκος αυτού του κύκλου είναι l(ry)+1+L, ενώ το μήκος του παλιού κύκλου C ήταν l(ry)+1+l(zr). Ο νέος κύκλος δεν μπορεί να είναι μεγαλύτερος από τον παλιό, αυτό έρχεται σε αντίθεση με τη μέγιστη τιμή του R, οπότε βλέπουμε ότι L ≤ l(zr), δηλ. το μήκος της διαδρομής από το z στο r στον παλιό βρόχο. Από την άλλη πλευρά, στο νέο γράφημα, η κορυφή z έχει τώρα ένα επίπεδο τουλάχιστον l(zr), και αν αυτό είναι μεγαλύτερο από το L, τότε τελειώσαμε. Άρα μπορούμε να υποθέσουμε ότι l(zr)=L. Για να συνοψίσουμε: υποθέτουμε ότι το a) δεν λειτουργεί και τότε γνωρίζουμε ότι το y-->z βρίσκεται στον κύκλο C, l(zr) = L.

Τώρα ας δοκιμάσουμε τη λειτουργία b): αντικαταστήστε την άκρη b-->r με κάποια άλλη άκρη b-->d. Ας δούμε πού βρίσκεται η νέα κορυφή d. Αν στο δέντρο T, τότε δημιουργήσαμε έναν νέο κύκλο χωρίς να σπάσουμε τον προηγούμενο, και αντικρούσαμε τη μεγιστοποίηση του R. Εάν σε άλλο δέντρο, τότε οι μέγιστες κορυφές του T, συμπεριλαμβανομένου του x, θα έχουν τώρα ένα επίπεδο μεγαλύτερο από το L, ενώ άλλα δέντρα δεν θα το κάνουν, και τελειώσαμε. Εάν σε έναν άλλο κύκλο, όχι στο C, τότε θα κάνουμε τώρα το a) μαζί με το β) επίσης το a): αφού γνωρίζουμε ότι το y-->z βρίσκεται στο C, τότε αυτή η πράξη θα σπάσει το C, αλλά όχι τον νέο κύκλο στον οποίο τώρα είναι συνδεδεμένο το δέντρο Τ, και αυτό το δέντρο θα έχει τώρα κορυφές επιπέδου μεγαλύτερου από το L, και τελειώσαμε ξανά.

Η επιλογή που απομένει είναι όταν το b-->d είναι επίσης συνδεδεμένο με τον κύκλο C, σε κάποιο άλλο μέρος εκτός από το r, ή στο ίδιο σημείο και μετά d=r. Αφού αντικαταστήσαμε το b-->r με το b-->d, έχουμε την ίδια κατάσταση όπως αρχικά - δέντρο T, κόμβος x του επιπέδου L κ.λπ. - μόνο το δέντρο συνδέεται πλέον με τον κύκλο μέσω της κορυφής d. Θεωρώντας τώρα τη λειτουργία a), συμπεραίνουμε (υποθέτοντας ότι δεν λειτουργεί) ότι l(zd) = L, όπως καταλήξαμε νωρίτερα ότι l(zr) = L. Αν όμως l(zd)=l( zr), δηλ. η απόσταση κατά μήκος του κύκλου από το z είναι η ίδια στο d και το r, τότε αυτή είναι η ίδια κορυφή: d=r. Έτσι, εάν το b) δεν λειτουργεί, τότε οποιαδήποτε ακμή από το b πρέπει να οδηγεί στο r, δηλ. οι άκρες από το β σχηματίζουν μια δέσμη.

Τέλος, θεωρήστε την ακμή c-->r που βρίσκεται στον κύκλο C. Εφόσον μπορούμε να υποθέσουμε ότι όλες οι ακμές από το b βρίσκονται στον σύνδεσμο που οδηγεί στο r, μπορούμε επίσης να επιβάλουμε τον περιορισμό που αναφέρθηκε παραπάνω ότι δεν μπορούν να υπάρχουν δύο σύνδεσμοι, που να οδηγούν σε μία κορυφή, δεν οδηγούν όλες οι ακμές από το c στο r, αλλά υπάρχει κάποια ακμή c-->e. Ας αντικαταστήσουμε το c-->r με το c-->e. Πού μπορεί να βρίσκεται η κορυφή e; Όχι στο δέντρο T, γιατί αυτό θα «επέκτεινε» τον κύκλο C, έρχεται σε αντίθεση με τη μεγιστοποίηση του R. Άρα το e βρίσκεται σε διαφορετικό δέντρο, ή σε διαφορετικό κύκλο, ή ακόμα και στον ίδιο κύκλο C, αλλά όχι στην κορυφή r . Στη συνέχεια, το δέντρο T, προτού συνδεθεί με τον κύκλο, επεκτείνεται τώρα κατά τουλάχιστον ένα άκρο που εξέρχεται από το r, και ίσως περισσότερο (μόνο ένα εάν το e βρίσκεται αμέσως μετά το r και το c--> e κλείνει ξανά τον κύκλο C, που προκύπτει μόνο r από αυτό). Αυτό σημαίνει ότι το επίπεδο της κορυφής x και των άλλων μέγιστων κορυφών T είναι τώρα τουλάχιστον L + 1, και τα άλλα δέντρα δεν έχουν επιμηκυνθεί, και πάλι έχουμε αυτό που χρειαζόμαστε.