🎨 2026 MATH MARATHON - GRAPH THEORY #3
Graph Theory Mastery
Part 3: Graph Coloring & Planarity - Η Τέχνη των Χρωμάτων
🔗 Η Διαδρομή μας:
Part 1 (❤️): Fundamentals, Trees, Handshaking Lemma
Part 2 (🔴): Eulerian & Hamiltonian Paths
Part 3 (🧡 TODAY): Graph Coloring & Planarity!
Σήμερα κατακτούμε:
✅ Vertex Coloring & Chromatic Number
✅ Four Color Theorem (THE famous one!)
✅ Edge Coloring & Chromatic Index
✅ Planar Graphs & Euler's Formula
✅ Kuratowski's Theorem
✅ 7 αναλυτικά παραδείγματα
✅ Classic competition problems
✅ Competition mastery
Part 1 (❤️): Fundamentals, Trees, Handshaking Lemma
Part 2 (🔴): Eulerian & Hamiltonian Paths
Part 3 (🧡 TODAY): Graph Coloring & Planarity!
Σήμερα κατακτούμε:
✅ Vertex Coloring & Chromatic Number
✅ Four Color Theorem (THE famous one!)
✅ Edge Coloring & Chromatic Index
✅ Planar Graphs & Euler's Formula
✅ Kuratowski's Theorem
✅ 7 αναλυτικά παραδείγματα
✅ Classic competition problems
✅ Competition mastery
🎨 Γιατί Graph Coloring;
Το graph coloring είναι ένα από τα πιο όμορφα και πρακτικά προβλήματα! Από χρωματισμό χαρτών μέχρι scheduling algorithms, από register allocation σε compilers μέχρι frequency assignment σε κινητά δίκτυα - το coloring είναι παντού! 🌈
Το graph coloring είναι ένα από τα πιο όμορφα και πρακτικά προβλήματα! Από χρωματισμό χαρτών μέχρι scheduling algorithms, από register allocation σε compilers μέχρι frequency assignment σε κινητά δίκτυα - το coloring είναι παντού! 🌈
🎯 1. Vertex Coloring - Βασικοί Ορισμοί
📌 Ορισμός: Vertex Coloring
Ένας vertex coloring (χρωματισμός κορυφών) ενός γράφου \(G = (V, E)\) είναι μια απεικόνιση:
\[ c: V \to \{1, 2, 3, \ldots, k\} \]
τέτοια ώστε αν \(\{u, v\} \in E\) (δηλαδή οι \(u, v\) είναι adjacent), τότε \(c(u) \neq c(v)\).
Με λόγια: Χρωματίζουμε κάθε κορυφή με ένα χρώμα, έτσι ώστε καμία ακμή να μη συνδέει δύο κορυφές του ίδιου χρώματος!
Proper Coloring: Coloring που ικανοποιεί το constraint παραπάνω.
Ένας vertex coloring (χρωματισμός κορυφών) ενός γράφου \(G = (V, E)\) είναι μια απεικόνιση:
\[ c: V \to \{1, 2, 3, \ldots, k\} \]
τέτοια ώστε αν \(\{u, v\} \in E\) (δηλαδή οι \(u, v\) είναι adjacent), τότε \(c(u) \neq c(v)\).
Με λόγια: Χρωματίζουμε κάθε κορυφή με ένα χρώμα, έτσι ώστε καμία ακμή να μη συνδέει δύο κορυφές του ίδιου χρώματος!
Proper Coloring: Coloring που ικανοποιεί το constraint παραπάνω.
🔢 Chromatic Number
Ο chromatic number \(\chi(G)\) ενός γράφου είναι ο ελάχιστος αριθμός χρωμάτων που χρειάζονται για proper vertex coloring.
Παραδείγματα:
• \(\chi(K_n) = n\) (complete graph χρειάζεται \(n\) χρώματα)
• \(\chi(C_n) = 2\) αν \(n\) άρτιος, \(3\) αν \(n\) περιττός (cycle)
• \(\chi(K_{m,n}) = 2\) (bipartite graph)
• \(\chi(\text{Tree}) = 2\) (δέντρα είναι bipartite)
Ο chromatic number \(\chi(G)\) ενός γράφου είναι ο ελάχιστος αριθμός χρωμάτων που χρειάζονται για proper vertex coloring.
Παραδείγματα:
• \(\chi(K_n) = n\) (complete graph χρειάζεται \(n\) χρώματα)
• \(\chi(C_n) = 2\) αν \(n\) άρτιος, \(3\) αν \(n\) περιττός (cycle)
• \(\chi(K_{m,n}) = 2\) (bipartite graph)
• \(\chi(\text{Tree}) = 2\) (δέντρα είναι bipartite)
📐 Θεώρημα: Brooks' Theorem
Για κάθε connected graph \(G\) που ΔΕΝ είναι complete graph ή odd cycle:
Εξαιρέσεις:
• \(K_n\): \(\chi = n\) αλλά \(\Delta = n-1\)
• \(C_{2k+1}\): \(\chi = 3\) αλλά \(\Delta = 2\)
💡 Θα το χρησιμοποιήσουμε αργότερα σε αυτό το ποστ — κρατήστε το στο μυαλό σας!
Για κάθε connected graph \(G\) που ΔΕΝ είναι complete graph ή odd cycle:
\[ \chi(G) \leq \Delta(G) \]
όπου \(\Delta(G)\) = maximum degree του γράφου.Εξαιρέσεις:
• \(K_n\): \(\chi = n\) αλλά \(\Delta = n-1\)
• \(C_{2k+1}\): \(\chi = 3\) αλλά \(\Delta = 2\)
💡 Θα το χρησιμοποιήσουμε αργότερα σε αυτό το ποστ — κρατήστε το στο μυαλό σας!
🗺️ 2. The Four Color Theorem
👑 The Four Color Theorem (1976)
Κάθε planar graph (επίπεδος γράφος) μπορεί να χρωματιστεί με το πολύ 4 χρώματα!
• 1852: Francis Guthrie - εικασία
• 1879: Kempe - λανθασμένη απόδειξη
• 1976: Appel & Haken - πρώτη major computer-assisted proof!
• 1997: Robertson, Sanders, Seymour, Thomas - απλούστερη απόδειξη
Σημείωση: Αυτό είναι ένα από τα πιο διάσημα θεωρήματα - πήρε 124 χρόνια να αποδειχθεί!
Κάθε planar graph (επίπεδος γράφος) μπορεί να χρωματιστεί με το πολύ 4 χρώματα!
\[ G \text{ planar} \Rightarrow \chi(G) \leq 4 \]
Ιστορία:• 1852: Francis Guthrie - εικασία
• 1879: Kempe - λανθασμένη απόδειξη
• 1976: Appel & Haken - πρώτη major computer-assisted proof!
• 1997: Robertson, Sanders, Seymour, Thomas - απλούστερη απόδειξη
Σημείωση: Αυτό είναι ένα από τα πιο διάσημα θεωρήματα - πήρε 124 χρόνια να αποδειχθεί!
📌 Planar Graphs (Επίπεδοι Γράφοι)
Ένας γράφος είναι planar αν μπορεί να σχεδιαστεί στο επίπεδο (2D plane) χωρίς edge crossings (διασταυρώσεις ακμών).
Παραδείγματα Planar:
• Trees (πάντα planar)
• Cycles
• \(K_4\) (complete graph με 4 κορυφές)
• Wheels, Grids
Παραδείγματα Non-Planar:
• \(K_5\) (complete με 5 κορυφές)
• \(K_{3,3}\) (complete bipartite)
Ένας γράφος είναι planar αν μπορεί να σχεδιαστεί στο επίπεδο (2D plane) χωρίς edge crossings (διασταυρώσεις ακμών).
Παραδείγματα Planar:
• Trees (πάντα planar)
• Cycles
• \(K_4\) (complete graph με 4 κορυφές)
• Wheels, Grids
Παραδείγματα Non-Planar:
• \(K_5\) (complete με 5 κορυφές)
• \(K_{3,3}\) (complete bipartite)
🔷 Euler's Formula για Planar Graphs
Για κάθε connected planar graph με \(V\) vertices, \(E\) edges, και \(F\) faces (περιοχές):
Παράδειγμα: Κύβος
• \(V = 8\) (γωνίες)
• \(E = 12\) (ακμές)
• \(F = 6\) (όψεις)
• Check: \(8 - 12 + 6 = 2\) ✓
Για κάθε connected planar graph με \(V\) vertices, \(E\) edges, και \(F\) faces (περιοχές):
\[ V - E + F = 2 \]
Faces: Οι περιοχές που δημιουργούνται (συμπεριλαμβανομένης της εξωτερικής!).Παράδειγμα: Κύβος
• \(V = 8\) (γωνίες)
• \(E = 12\) (ακμές)
• \(F = 6\) (όψεις)
• Check: \(8 - 12 + 6 = 2\) ✓
📐 Kuratowski's Theorem (1930)
Ένας γράφος είναι planar αν και μόνο αν ΔΕΝ περιέχει subdivision του \(K_5\) ή \(K_{3,3}\) ως subgraph.
Subdivision: Προσθήκη vertices σε edges (splitting edges).
Δηλαδή: Τα \(K_5\) και \(K_{3,3}\) είναι τα "forbidden subdivisions" για planarity (μια στενά συγγενική εκδοχή με "minors" ισχύει από το θεώρημα του Wagner, 1937).
Ένας γράφος είναι planar αν και μόνο αν ΔΕΝ περιέχει subdivision του \(K_5\) ή \(K_{3,3}\) ως subgraph.
Subdivision: Προσθήκη vertices σε edges (splitting edges).
Δηλαδή: Τα \(K_5\) και \(K_{3,3}\) είναι τα "forbidden subdivisions" για planarity (μια στενά συγγενική εκδοχή με "minors" ισχύει από το θεώρημα του Wagner, 1937).
📚 3. Vertex Coloring Examples
🔹 Παράδειγμα 1: Greedy Coloring Algorithm
Πρόβλημα: Χρωματίστε τον γράφο \(C_5\) (cycle με 5 κορυφές) με greedy algorithm.
Λύση:
Λύση:
Greedy Algorithm:
1. Βάλε τις κορυφές σε σειρά: \(v_1, v_2, v_3, v_4, v_5\)
2. Για κάθε κορυφή, χρησιμοποίησε το μικρότερο χρώμα που δεν χρησιμοποιείται από ήδη χρωματισμένους γείτονες
Execution:
• \(v_1\): Color 1 (πρώτη, κανένας γείτονας χρωματισμένος)
• \(v_2\): γείτονας \(v_1\)(=1) → Color 2
• \(v_3\): μόνο ο \(v_2\)(=2) είναι ήδη χρωματισμένος γείτονας (ο \(v_4\) όχι ακόμα) → μικρότερο διαθέσιμο = Color 1
• \(v_4\): μόνο ο \(v_3\)(=1) είναι ήδη χρωματισμένος γείτονας → μικρότερο διαθέσιμο = Color 2
• \(v_5\): γείτονες \(v_4\)(=2) ΚΑΙ \(v_1\)(=1) ήδη χρωματισμένοι → χρειάζεται Color 3
Greedy χρησιμοποίησε 3 χρώματα (1,2,1,2,3)!
Αλλά \(\chi(C_5) = 3\) (odd cycle), άρα optimal! ✓
1. Βάλε τις κορυφές σε σειρά: \(v_1, v_2, v_3, v_4, v_5\)
2. Για κάθε κορυφή, χρησιμοποίησε το μικρότερο χρώμα που δεν χρησιμοποιείται από ήδη χρωματισμένους γείτονες
Execution:
• \(v_1\): Color 1 (πρώτη, κανένας γείτονας χρωματισμένος)
• \(v_2\): γείτονας \(v_1\)(=1) → Color 2
• \(v_3\): μόνο ο \(v_2\)(=2) είναι ήδη χρωματισμένος γείτονας (ο \(v_4\) όχι ακόμα) → μικρότερο διαθέσιμο = Color 1
• \(v_4\): μόνο ο \(v_3\)(=1) είναι ήδη χρωματισμένος γείτονας → μικρότερο διαθέσιμο = Color 2
• \(v_5\): γείτονες \(v_4\)(=2) ΚΑΙ \(v_1\)(=1) ήδη χρωματισμένοι → χρειάζεται Color 3
Greedy χρησιμοποίησε 3 χρώματα (1,2,1,2,3)!
Αλλά \(\chi(C_5) = 3\) (odd cycle), άρα optimal! ✓
🔹 Παράδειγμα 2: Map Coloring
Πρόβλημα: Έχετε χάρτη με 6 χώρες σε κύκλο. Πόσα χρώματα χρειάζονται;
Λύση:
Λύση:
Dual graph: \(C_6\) (cycle με 6 κορυφές).
Αφού 6 άρτιος: \(\chi(C_6) = 2\)
Coloring:
• Alternating colors: 1, 2, 1, 2, 1, 2
Μόνο 2 χρώματα χρειάζονται! 🎨
Αφού 6 άρτιος: \(\chi(C_6) = 2\)
Coloring:
• Alternating colors: 1, 2, 1, 2, 1, 2
Μόνο 2 χρώματα χρειάζονται! 🎨
🎨 4. Edge Coloring
📌 Edge Coloring
Ένας edge coloring είναι χρωματισμός των ακμών έτσι ώστε δύο ακμές που μοιράζονται κορυφή να έχουν διαφορετικά χρώματα.
Chromatic Index \(\chi'(G)\): Ελάχιστος αριθμός χρωμάτων για edge coloring.
Ένας edge coloring είναι χρωματισμός των ακμών έτσι ώστε δύο ακμές που μοιράζονται κορυφή να έχουν διαφορετικά χρώματα.
Chromatic Index \(\chi'(G)\): Ελάχιστος αριθμός χρωμάτων για edge coloring.
📐 Vizing's Theorem (1964)
Για κάθε simple graph:
Class 1 graphs: \(\chi' = \Delta\)
Class 2 graphs: \(\chi' = \Delta + 1\)
Παράδειγμα: Bipartite graphs είναι πάντα Class 1!
Για κάθε simple graph:
\[ \Delta(G) \leq \chi'(G) \leq \Delta(G) + 1 \]
όπου \(\Delta(G)\) = maximum degree.Class 1 graphs: \(\chi' = \Delta\)
Class 2 graphs: \(\chi' = \Delta + 1\)
Παράδειγμα: Bipartite graphs είναι πάντα Class 1!
🏆 5. Classic Competition Problems
🏅 Παράδειγμα 3: Triangulating Convex n-gon
Πρόβλημα: Με πόσους τρόπους μπορείτε να τριγωνοποιήσετε ένα κυρτό \(n\)-γωνο με \((n-3)\) μη-τεμνόμενες διαγώνιες;
Λύση:
Λύση:
Catalan Numbers!
Ο αριθμός τρόπων να τριγωνοποιήσεις ένα κυρτό \((n+2)\)-γωνο είναι ο \(n\)-οστός Catalan number:
Παραδείγματα:
• Pentagon (5-γωνο): \(C_3 = 5\) τρόποι
• Hexagon (6-γωνο): \(C_4 = 14\) τρόποι
• Heptagon (7-γωνο): \(C_5 = 42\) τρόποι
Ο αριθμός τρόπων να τριγωνοποιήσεις ένα κυρτό \((n+2)\)-γωνο είναι ο \(n\)-οστός Catalan number:
\[ C_n = \frac{1}{n+1}\binom{2n}{n} \]
Για \(n\)-γωνο: \(C_{n-2}\) τρόποι.Παραδείγματα:
• Pentagon (5-γωνο): \(C_3 = 5\) τρόποι
• Hexagon (6-γωνο): \(C_4 = 14\) τρόποι
• Heptagon (7-γωνο): \(C_5 = 42\) τρόποι
Recursive Formula:
\(T(n)\) = αριθμός triangulations του \(n\)-γωνου.
Fix μία ακμή και θεώρησε το triangle που το περιέχει:
\[ T(n) = \sum_{k=2}^{n-1} T(k) \cdot T(n-k+1) \]
με \(T(2) = 1\) (εκφυλισμένη περίπτωση/μονή ακμή) και \(T(3) = 1\) (τρίγωνο ήδη τριγωνοποιημένο).
\(T(n)\) = αριθμός triangulations του \(n\)-γωνου.
Fix μία ακμή και θεώρησε το triangle που το περιέχει:
\[ T(n) = \sum_{k=2}^{n-1} T(k) \cdot T(n-k+1) \]
με \(T(2) = 1\) (εκφυλισμένη περίπτωση/μονή ακμή) και \(T(3) = 1\) (τρίγωνο ήδη τριγωνοποιημένο).
🏅 Παράδειγμα 4: The Petersen Graph Revisited
Πρόβλημα: Στο Part 2 είδαμε τον Petersen graph: 10 κορυφές, κάθε μία βαθμού 3, χωρίς τρίγωνα και χωρίς 4-κύκλους (girth 5). Αποδείξτε ότι κάθε δύο μη-γειτονικές κορυφές έχουν ακριβώς έναν κοινό γείτονα.
Λύση:
Λύση:
Βήμα 1: Μέτρημα "cherries" (μονοπάτια μήκους 2)
Κάθε κορυφή έχει βαθμό 3, άρα δίνει \(\binom{3}{2}=3\) "cherries" (ζεύγη γειτόνων της). Σύνολο:
\[ 10 \times 3 = 30 \text{ cherries} \]
Κάθε cherry με κέντρο \(x\) και άκρα \(y,z\) πιστοποιεί ότι το \(x\) είναι κοινός γείτονας των \(y,z\).
Κάθε κορυφή έχει βαθμό 3, άρα δίνει \(\binom{3}{2}=3\) "cherries" (ζεύγη γειτόνων της). Σύνολο:
\[ 10 \times 3 = 30 \text{ cherries} \]
Κάθε cherry με κέντρο \(x\) και άκρα \(y,z\) πιστοποιεί ότι το \(x\) είναι κοινός γείτονας των \(y,z\).
Βήμα 2: Πού "προσγειώνονται" τα cherries;
• Αφού δεν υπάρχουν τρίγωνα (girth ≥5), καμία γειτονική (adjacent) ζεύγος κορυφών δεν έχει κοινό γείτονα — αλλιώς θα σχηματιζόταν τρίγωνο!
• Αφού δεν υπάρχουν 4-κύκλοι, κανένα ζεύγος δεν έχει 2 ή περισσότερους κοινούς γείτονες — αλλιώς θα σχηματιζόταν 4-κύκλος!
Άρα όλα τα 30 cherries προσγειώνονται σε μη-γειτονικά ζεύγη, το πολύ 1 ανά ζεύγος.
• Αφού δεν υπάρχουν τρίγωνα (girth ≥5), καμία γειτονική (adjacent) ζεύγος κορυφών δεν έχει κοινό γείτονα — αλλιώς θα σχηματιζόταν τρίγωνο!
• Αφού δεν υπάρχουν 4-κύκλοι, κανένα ζεύγος δεν έχει 2 ή περισσότερους κοινούς γείτονες — αλλιώς θα σχηματιζόταν 4-κύκλος!
Άρα όλα τα 30 cherries προσγειώνονται σε μη-γειτονικά ζεύγη, το πολύ 1 ανά ζεύγος.
Βήμα 3: Μέτρημα μη-γειτονικών ζευγών
Σύνολο ζευγών: \(\binom{10}{2}=45\). Ακμές: \(10\times3/2=15\). Μη-γειτονικά ζεύγη: \(45-15=30\).
Έχουμε ακριβώς 30 cherries να μοιραστούν σε ακριβώς 30 μη-γειτονικά ζεύγη, το πολύ 1 ανά ζεύγος — άρα κάθε μη-γειτονικό ζεύγος παίρνει ακριβώς 1! \(\blacksquare\)
Σύνολο ζευγών: \(\binom{10}{2}=45\). Ακμές: \(10\times3/2=15\). Μη-γειτονικά ζεύγη: \(45-15=30\).
Έχουμε ακριβώς 30 cherries να μοιραστούν σε ακριβώς 30 μη-γειτονικά ζεύγη, το πολύ 1 ανά ζεύγος — άρα κάθε μη-γειτονικό ζεύγος παίρνει ακριβώς 1! \(\blacksquare\)
⚠️ Σημείωση διόρθωσης: Η αρχική εκδοχή ("AUO 1992") έθετε το ίδιο ερώτημα για τυχαίο 4-κανονικό γράφο με 17 κορυφές — κάτι που είναι στην πραγματικότητα μαθηματικά λάθος: από το όριο του Moore, ένας 4-κανονικός γράφος με διάμετρο 2 έχει το πολύ \(1+4+4\cdot3=17\) κορυφές, με ισότητα ΜΟΝΟ αν είναι γνήσιος γράφος Moore — και δεν υπάρχει γράφος Moore βαθμού 4 (μόνο για βαθμό 2, 3, 7). Άρα κάθε 4-κανονικός γράφος με 17 κορυφές έχει διάμετρο >2, δηλαδή πάντα υπάρχει ζεύγος χωρίς κοινό γείτονα — ακριβώς το αντίθετο συμπέρασμα! Το αντικαταστήσαμε με τη σωστή, επαληθευμένη εκδοχή για τον (μοναδικό) γράφο Petersen, που είναι πράγματι γράφος Moore βαθμού 3.
🏅 Παράδειγμα 5: Monochromatic Triangles (IMO 1992, Πρόβλημα 3)
Πρόβλημα: Θεωρήστε 9 σημεία στο χώρο, όχι 4 από τα οποία είναι συνεπίπεδα. Κάθε ζεύγος συνδέεται με ακμή, και κάθε ακμή είτε χρωματίζεται μπλε είτε κόκκινη είτε παραμένει άβαφη. Βρείτε την ελάχιστη τιμή του \(n\) τέτοια ώστε, όποτε ακριβώς \(n\) ακμές είναι χρωματισμένες, υπάρχει πάντα μονοχρωματικό τρίγωνο.
Λύση (σκαρίφημα):
Λύση (σκαρίφημα):
Complete graph \(K_9\) έχει \(\binom{9}{2}=36\) ακμές συνολικά.
Το \(n=32\) δεν αρκεί: Υπάρχει έγκυρος χρωματισμός 32 ακμών χωρίς μονοχρωματικό τρίγωνο — π.χ. πάρτε δύο "τετράγωνα" \(R_1R_2R_3R_4\) και \(B_1B_2B_3B_4\) (8 σημεία), χρωμάτισε όλες τις εντός-τετραγώνου ακμές (12) με το αντίστοιχο χρώμα, και τις ανά ζεύγη ακμές μεταξύ των δύο τετραγώνων ανάλογα με το αν οι δείκτες έχουν ίδια ή διαφορετική αρτιότητα — αποφεύγει επιτυχώς κάθε μονοχρωματικό τρίγωνο.
Το \(n=33\) αρκεί πάντα: Με 33 χρωματισμένες (άρα μόνο 3 άβαφες) ακμές, ένα pigeonhole + Ramsey \(R(3,3)=6\) επιχείρημα δείχνει ότι πάντα υπάρχει μονοχρωματικό τρίγωνο.
Απάντηση: \(n = 33\)
Το \(n=32\) δεν αρκεί: Υπάρχει έγκυρος χρωματισμός 32 ακμών χωρίς μονοχρωματικό τρίγωνο — π.χ. πάρτε δύο "τετράγωνα" \(R_1R_2R_3R_4\) και \(B_1B_2B_3B_4\) (8 σημεία), χρωμάτισε όλες τις εντός-τετραγώνου ακμές (12) με το αντίστοιχο χρώμα, και τις ανά ζεύγη ακμές μεταξύ των δύο τετραγώνων ανάλογα με το αν οι δείκτες έχουν ίδια ή διαφορετική αρτιότητα — αποφεύγει επιτυχώς κάθε μονοχρωματικό τρίγωνο.
Το \(n=33\) αρκεί πάντα: Με 33 χρωματισμένες (άρα μόνο 3 άβαφες) ακμές, ένα pigeonhole + Ramsey \(R(3,3)=6\) επιχείρημα δείχνει ότι πάντα υπάρχει μονοχρωματικό τρίγωνο.
⚠️ Σημείωση διόρθωσης: Το αρχικό κείμενο ανέφερε λάθος αρίθμηση ("Πρόβλημα 5" αντί για το σωστό Πρόβλημα 3) και λάθος απάντηση (\(s=30\)) — η επίσημη, επιβεβαιωμένη απάντηση είναι \(n=33\).
📊 6. Επιπλέον Παραδείγματα
🔹 Παράδειγμα 6: Scheduling Problem
Πρόβλημα: Έχετε 7 μαθήματα. Κάποια ζεύγη δεν μπορούν να είναι την ίδια ώρα (conflicts). Ελάχιστος αριθμός time slots;
Conflicts: (1,2), (1,3), (2,4), (3,4), (4,5), (5,6), (6,7), (7,5)
Λύση:
Conflicts: (1,2), (1,3), (2,4), (3,4), (4,5), (5,6), (6,7), (7,5)
Λύση:
Graph Coloring!
Vertices = μαθήματα
Edges = conflicts
Chromatic number = ελάχιστος αριθμός time slots!
Analyzing the graph structure και greedy coloring → \(\chi = 3\)
Schedule:
• Slot 1: {1, 4, 7}
• Slot 2: {2, 5}
• Slot 3: {3, 6}
Vertices = μαθήματα
Edges = conflicts
Chromatic number = ελάχιστος αριθμός time slots!
Analyzing the graph structure και greedy coloring → \(\chi = 3\)
Schedule:
• Slot 1: {1, 4, 7}
• Slot 2: {2, 5}
• Slot 3: {3, 6}
🔹 Παράδειγμα 7: Planar Graph Verification
Πρόβλημα: Είναι το \(K_{3,3}\) planar;
Λύση:
Λύση:
Method 1: Euler's Formula
\(K_{3,3}\) έχει \(V = 6\), \(E = 9\).
Αν ήταν planar με \(F\) faces:
\[ V - E + F = 2 \Rightarrow 6 - 9 + F = 2 \Rightarrow F = 5 \]
Κάθε face σε bipartite graph έχει τουλάχιστον 4 ακμές (no triangles!).
Άρα \(2E \geq 4F\) (κάθε edge borders 2 faces).
\[ 2(9) \geq 4(5) \Rightarrow 18 \geq 20 \]
Contradiction! Άρα \(K_{3,3}\) ΔΕΝ είναι planar! ✓
\(K_{3,3}\) έχει \(V = 6\), \(E = 9\).
Αν ήταν planar με \(F\) faces:
\[ V - E + F = 2 \Rightarrow 6 - 9 + F = 2 \Rightarrow F = 5 \]
Κάθε face σε bipartite graph έχει τουλάχιστον 4 ακμές (no triangles!).
Άρα \(2E \geq 4F\) (κάθε edge borders 2 faces).
\[ 2(9) \geq 4(5) \Rightarrow 18 \geq 20 \]
Contradiction! Άρα \(K_{3,3}\) ΔΕΝ είναι planar! ✓
🎯 7. Strategy Framework
🏆 Problem-Solving με Coloring
ΒΗΜΑ 1: Αναγνώριση
• Coloring problem;
• Vertex ή edge coloring;
• Planar graph;
ΒΗΜΑ 2: Bounds
• Lower bound: clique size, odd cycle length
• Upper bound: Brooks, greedy
ΒΗΜΑ 3: Technique Selection
• Greedy algorithm
• Induction
• Euler's formula (planar)
ΒΗΜΑ 4: Verification
• Construct explicit coloring
• Verify constraints
ΒΗΜΑ 1: Αναγνώριση
• Coloring problem;
• Vertex ή edge coloring;
• Planar graph;
ΒΗΜΑ 2: Bounds
• Lower bound: clique size, odd cycle length
• Upper bound: Brooks, greedy
ΒΗΜΑ 3: Technique Selection
• Greedy algorithm
• Induction
• Euler's formula (planar)
ΒΗΜΑ 4: Verification
• Construct explicit coloring
• Verify constraints
🚨 Common Mistakes
⚠️ Τα 5 Πιο Συχνά Λάθη
1. Greedy = Optimal
❌ "Greedy πάντα δίνει χ(G)"
✅ Greedy δίνει upper bound, ΟΧΙ πάντα optimal (και εξαρτάται από τη σειρά!)
2. Planar = Few Colors
❌ "Planar → χ = 4 πάντα"
✅ χ ≤ 4, μπορεί να είναι 2 ή 3!
3. Euler Formula Misuse
❌ Ξεχνάμε V - E + F = 2 μόνο για connected planar
✅ Check connectivity!
4. K₅ Drawing
❌ "Μπορώ να σχεδιάσω K₅ planar"
✅ Αδύνατο! Kuratowski says NO!
5. Ξεχνώντας εξαιρέσεις
❌ "Κάθε γράφος με Δ≤3 είναι 3-χρωματίσιμος"
✅ Το \(K_4\) είναι αντιπαράδειγμα (Δ=3 αλλά χ=4)! Πάντα ελέγχετε τις εξαιρέσεις του Brooks' theorem.
1. Greedy = Optimal
❌ "Greedy πάντα δίνει χ(G)"
✅ Greedy δίνει upper bound, ΟΧΙ πάντα optimal (και εξαρτάται από τη σειρά!)
2. Planar = Few Colors
❌ "Planar → χ = 4 πάντα"
✅ χ ≤ 4, μπορεί να είναι 2 ή 3!
3. Euler Formula Misuse
❌ Ξεχνάμε V - E + F = 2 μόνο για connected planar
✅ Check connectivity!
4. K₅ Drawing
❌ "Μπορώ να σχεδιάσω K₅ planar"
✅ Αδύνατο! Kuratowski says NO!
5. Ξεχνώντας εξαιρέσεις
❌ "Κάθε γράφος με Δ≤3 είναι 3-χρωματίσιμος"
✅ Το \(K_4\) είναι αντιπαράδειγμα (Δ=3 αλλά χ=4)! Πάντα ελέγχετε τις εξαιρέσεις του Brooks' theorem.
🏆 CHALLENGE PROBLEM - Part 3
🎯 THE CHALLENGE
Πρόβλημα: Αποδείξτε ότι κάθε connected graph με maximum degree Δ ≤ 3, εκτός από το \(K_4\), μπορεί να χρωματιστεί με 3 χρώματα.
Πρόβλημα: Αποδείξτε ότι κάθε connected graph με maximum degree Δ ≤ 3, εκτός από το \(K_4\), μπορεί να χρωματιστεί με 3 χρώματα.
⚠️ Σημείωση διόρθωσης: Η αρχική εκφώνηση ("κάθε planar graph με Δ≤3...") ήταν μαθηματικά λάθος — το \(K_4\) είναι άμεσο αντιπαράδειγμα: είναι planar, έχει \(\Delta=3\), αλλά \(\chi(K_4)=4\) (χρειάζεται 4 χρώματα αφού είναι πλήρης γράφος). Ούτε χρειάζεται καν η υπόθεση planarity — το σωστό εργαλείο είναι το Brooks' Theorem που είδαμε στην αρχή του ποστ!
🎁 Hints σε 2 Επίπεδα:
🥉 Hint 1: Θυμήσου το Brooks' Theorem από την ενότητα 1!
🥈 Hint 2: Ποιες είναι ακριβώς οι εξαιρέσεις του Brooks' Theorem όταν \(\Delta=3\);
📮 Πλήρης Λύση:
Από το Brooks' Theorem (ενότητα 1): για κάθε connected γράφο \(G\) που ΔΕΝ είναι complete graph ή odd cycle, ισχύει \(\chi(G) \leq \Delta(G)\).
Εδώ \(\Delta(G) \leq 3\).
Έλεγχος εξαιρέσεων:
• Complete graphs με \(\Delta \leq 3\): μόνο τα \(K_1, K_2, K_3, K_4\) (αφού \(K_n\) έχει \(\Delta=n-1\)). Από αυτά, μόνο το \(K_4\) έχει \(\chi > 3\) (\(\chi(K_4)=4\)); τα \(K_1,K_2,K_3\) έχουν \(\chi\leq3\) ήδη.
• Odd cycles \(C_{2k+1}\): έχουν \(\Delta=2\), και \(\chi(C_{2k+1})=3\leq3\) ήδη — δεν χρειάζονται καν το Brooks' theorem για να είναι 3-χρωματίσιμα!
Άρα, αποκλείοντας ρητά το \(K_4\), το Brooks' theorem δίνει άμεσα:
\[ \chi(G) \leq \Delta(G) \leq 3 \]
για κάθε άλλο connected γράφο με \(\Delta\leq3\). \(\blacksquare\)
💡 Παρατήρηση: Η planarity δεν χρειάστηκε καθόλου! Το αποτέλεσμα ισχύει για ΚΑΘΕ γράφο (όχι μόνο planar) με \(\Delta\leq3\), εκτός \(K_4\) — π.χ. ο κύβος (planar, 3-κανονικός) είναι μάλιστα bipartite άρα \(\chi=2\).
Από το Brooks' Theorem (ενότητα 1): για κάθε connected γράφο \(G\) που ΔΕΝ είναι complete graph ή odd cycle, ισχύει \(\chi(G) \leq \Delta(G)\).
Εδώ \(\Delta(G) \leq 3\).
Έλεγχος εξαιρέσεων:
• Complete graphs με \(\Delta \leq 3\): μόνο τα \(K_1, K_2, K_3, K_4\) (αφού \(K_n\) έχει \(\Delta=n-1\)). Από αυτά, μόνο το \(K_4\) έχει \(\chi > 3\) (\(\chi(K_4)=4\)); τα \(K_1,K_2,K_3\) έχουν \(\chi\leq3\) ήδη.
• Odd cycles \(C_{2k+1}\): έχουν \(\Delta=2\), και \(\chi(C_{2k+1})=3\leq3\) ήδη — δεν χρειάζονται καν το Brooks' theorem για να είναι 3-χρωματίσιμα!
Άρα, αποκλείοντας ρητά το \(K_4\), το Brooks' theorem δίνει άμεσα:
\[ \chi(G) \leq \Delta(G) \leq 3 \]
για κάθε άλλο connected γράφο με \(\Delta\leq3\). \(\blacksquare\)
💡 Παρατήρηση: Η planarity δεν χρειάστηκε καθόλου! Το αποτέλεσμα ισχύει για ΚΑΘΕ γράφο (όχι μόνο planar) με \(\Delta\leq3\), εκτός \(K_4\) — π.χ. ο κύβος (planar, 3-κανονικός) είναι μάλιστα bipartite άρα \(\chi=2\).
📊 Σύνοψη & Επόμενα Βήματα
🎓 Τι Μάθαμε:
✅ Vertex Coloring: Chromatic number χ(G)
✅ Four Color Theorem: Planar → χ ≤ 4
✅ Edge Coloring: Chromatic index χ'(G)
✅ Planar Graphs: Euler's formula V - E + F = 2
✅ Kuratowski: K₅, K₃,₃ forbidden
✅ Brooks' Theorem: χ ≤ Δ (με εξαιρέσεις — και τις χρησιμοποιήσαμε στο τέλος!)
✅ 7 Examples: Από greedy → κλασικά προβλήματα
✅ Classic Problems: Triangulation, Petersen graph, IMO 1992
✅ Vertex Coloring: Chromatic number χ(G)
✅ Four Color Theorem: Planar → χ ≤ 4
✅ Edge Coloring: Chromatic index χ'(G)
✅ Planar Graphs: Euler's formula V - E + F = 2
✅ Kuratowski: K₅, K₃,₃ forbidden
✅ Brooks' Theorem: χ ≤ Δ (με εξαιρέσεις — και τις χρησιμοποιήσαμε στο τέλος!)
✅ 7 Examples: Από greedy → κλασικά προβλήματα
✅ Classic Problems: Triangulation, Petersen graph, IMO 1992
🎊 Συγχαρητήρια!
Ολοκληρώσατε το Part 3 του Graph Theory Marathon!
Τι κατακτήσατε:
✅ Graph coloring mastery
✅ Four Color Theorem understanding
✅ Planar graphs complete theory
✅ Euler's formula applications
✅ Kuratowski's theorem
✅ 7 αναλυτικά examples
✅ Verified classic problems
✅ Competition-ready skills
Ολοκληρώσατε το Part 3 του Graph Theory Marathon!
Τι κατακτήσατε:
✅ Graph coloring mastery
✅ Four Color Theorem understanding
✅ Planar graphs complete theory
✅ Euler's formula applications
✅ Kuratowski's theorem
✅ 7 αναλυτικά examples
✅ Verified classic problems
✅ Competition-ready skills
📅 Επόμενο Part - FINALE:
Part 4: IMO Problems & Graph Theory Mastery
The ultimate collection! 💜👑
Part 4: IMO Problems & Graph Theory Mastery
The ultimate collection! 💜👑
🔗 Αν σου διέφυγε: Part 2 - Eulerian & Hamiltonian Paths
Ένα Part ακόμα...
Η κορυφή σας περιμένει! 🏔️🎨
Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώ
PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify
📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα
Δες τα βιβλία →
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου