.jpg)
🌳 2026 MATH MARATHON - GRAPH THEORY #1
Graph Theory Mastery
Part 1: Fundamentals & Tree Theory - Τα Θεμέλια των Γράφων
🌳 Καλωσορίσατε στο Graph Theory Marathon!
Η Graph Theory είναι ένα από τα πιο fundamental και beautiful πεδία των μαθηματικών! Εμφανίζεται παντού: networks, algorithms, optimization, και φυσικά στις Ολυμπιάδες!
Σήμερα (Part 1):
✅ Τι είναι Graphs - Βασικοί ορισμοί
✅ Paths, Cycles, Circuits
✅ Trees & Forests
✅ Connectivity & Components
✅ Degree Sequences
✅ 7 αναλυτικά παραδείγματα
✅ 2 BMO/IMO problems
✅ Competition framework
Η Graph Theory είναι ένα από τα πιο fundamental και beautiful πεδία των μαθηματικών! Εμφανίζεται παντού: networks, algorithms, optimization, και φυσικά στις Ολυμπιάδες!
Σήμερα (Part 1):
✅ Τι είναι Graphs - Βασικοί ορισμοί
✅ Paths, Cycles, Circuits
✅ Trees & Forests
✅ Connectivity & Components
✅ Degree Sequences
✅ 7 αναλυτικά παραδείγματα
✅ 2 BMO/IMO problems
✅ Competition framework
🤔 Γιατί Graph Theory;
Οι γράφοι μοντελοποιούν **σχέσεις**: φιλίες, δρόμους, συνδέσεις, εξαρτήσεις. Κάθε φορά που έχετε "αντικείμενα και σχέσεις μεταξύ τους", έχετε έναν γράφο! Αυτό τους κάνει **απίστευτα versatile** και essential για problem solving! 🎯
Οι γράφοι μοντελοποιούν **σχέσεις**: φιλίες, δρόμους, συνδέσεις, εξαρτήσεις. Κάθε φορά που έχετε "αντικείμενα και σχέσεις μεταξύ τους", έχετε έναν γράφο! Αυτό τους κάνει **απίστευτα versatile** και essential για problem solving! 🎯
🎯 1. Τι είναι Graph;
📌 Ορισμός: Graph
Ένας γράφος (graph) \(G = (V, E)\) αποτελείται από:
1. Vertices (κορυφές): Ένα σύνολο \(V\) από σημεία
• Συμβολίζονται: \(v_1, v_2, \ldots, v_n\)
• \(|V| = n\) = αριθμός κορυφών
2. Edges (ακμές): Ένα σύνολο \(E\) από ζεύγη κορυφών
• Συμβολίζονται: \(e = \{u, v\}\) ή \(e = (u, v)\)
• \(|E| = m\) = αριθμός ακμών
Notation: \(G = (V, E)\) ή απλά \(G\)
Ένας γράφος (graph) \(G = (V, E)\) αποτελείται από:
1. Vertices (κορυφές): Ένα σύνολο \(V\) από σημεία
• Συμβολίζονται: \(v_1, v_2, \ldots, v_n\)
• \(|V| = n\) = αριθμός κορυφών
2. Edges (ακμές): Ένα σύνολο \(E\) από ζεύγη κορυφών
• Συμβολίζονται: \(e = \{u, v\}\) ή \(e = (u, v)\)
• \(|E| = m\) = αριθμός ακμών
Notation: \(G = (V, E)\) ή απλά \(G\)
🎨 Undirected vs Directed Graphs
Undirected Graph:
• Edges = unordered pairs \(\{u, v\}\)
• Edge από \(u\) σε \(v\) = edge από \(v\) σε \(u\)
• Συμμετρική σχέση
Directed Graph (Digraph):
• Edges = ordered pairs \((u, v)\)
• Arrow από \(u\) προς \(v\)
• \((u, v) \neq (v, u)\)
• Ασύμμετρη σχέση
Παράδειγμα:
• One-way streets: digraph
• Friendships: undirected graph (συνήθως)
• Dependencies: digraph
Undirected Graph:
• Edges = unordered pairs \(\{u, v\}\)
• Edge από \(u\) σε \(v\) = edge από \(v\) σε \(u\)
• Συμμετρική σχέση
Directed Graph (Digraph):
• Edges = ordered pairs \((u, v)\)
• Arrow από \(u\) προς \(v\)
• \((u, v) \neq (v, u)\)
• Ασύμμετρη σχέση
Παράδειγμα:
• One-way streets: digraph
• Friendships: undirected graph (συνήθως)
• Dependencies: digraph
🔗 Βασικοί Όροι
Adjacent (γειτονικές) κορυφές:
Δύο κορυφές \(u, v\) είναι adjacent αν υπάρχει ακμή \(\{u, v\}\)
Incident:
Μια ακμή \(e = \{u, v\}\) είναι incident στις κορυφές \(u\) και \(v\)
Degree (βαθμός) κορυφής:
\(\deg(v)\) = αριθμός ακμών incident στο \(v\)
• Για undirected graphs
In-degree & Out-degree:
• \(\deg^-(v)\) = αριθμός incoming edges
• \(\deg^+(v)\) = αριθμός outgoing edges
• Για directed graphs
Adjacent (γειτονικές) κορυφές:
Δύο κορυφές \(u, v\) είναι adjacent αν υπάρχει ακμή \(\{u, v\}\)
Incident:
Μια ακμή \(e = \{u, v\}\) είναι incident στις κορυφές \(u\) και \(v\)
Degree (βαθμός) κορυφής:
\(\deg(v)\) = αριθμός ακμών incident στο \(v\)
• Για undirected graphs
In-degree & Out-degree:
• \(\deg^-(v)\) = αριθμός incoming edges
• \(\deg^+(v)\) = αριθμός outgoing edges
• Για directed graphs
📐 Handshaking Lemma
Σε κάθε undirected graph:
Γιατί; Κάθε ακμή συνεισφέρει 1 στον βαθμό **δύο** κορυφών!
Συνέπεια: Ο αριθμός κορυφών με περιττό βαθμό είναι πάντα **άρτιος**!
Σε κάθε undirected graph:
\[ \sum_{v \in V} \deg(v) = 2|E| \]
Με λόγια: Το άθροισμα όλων των βαθμών ισούται με το διπλάσιο του αριθμού ακμών.Γιατί; Κάθε ακμή συνεισφέρει 1 στον βαθμό **δύο** κορυφών!
Συνέπεια: Ο αριθμός κορυφών με περιττό βαθμό είναι πάντα **άρτιος**!
🌲 2. Paths, Cycles & Trees
📌 Paths (Μονοπάτια)
Ένα path (μονοπάτι) από \(u\) σε \(v\) είναι μια ακολουθία κορυφών:
\[ u = v_0, v_1, v_2, \ldots, v_k = v \]
όπου \(\{v_i, v_{i+1}\} \in E\) για όλα τα \(i\).
Length: Αριθμός ακμών = \(k\)
Simple Path: Όλες οι κορυφές διαφορετικές (εκτός ίσως πρώτης=τελευταίας)
Ένα path (μονοπάτι) από \(u\) σε \(v\) είναι μια ακολουθία κορυφών:
\[ u = v_0, v_1, v_2, \ldots, v_k = v \]
όπου \(\{v_i, v_{i+1}\} \in E\) για όλα τα \(i\).
Length: Αριθμός ακμών = \(k\)
Simple Path: Όλες οι κορυφές διαφορετικές (εκτός ίσως πρώτης=τελευταίας)
📌 Cycles (Κύκλοι)
Ένας cycle (κύκλος) είναι ένα path που:
• Ξεκινάει και τελειώνει στην ίδια κορυφή
• Length ≥ 3
• Όλες οι ενδιάμεσες κορυφές διαφορετικές
Notation: \(C_n\) = cycle μήκους \(n\)
Circuit (κύκλωμα): Σε directed graphs, κλειστό path
Ένας cycle (κύκλος) είναι ένα path που:
• Ξεκινάει και τελειώνει στην ίδια κορυφή
• Length ≥ 3
• Όλες οι ενδιάμεσες κορυφές διαφορετικές
Notation: \(C_n\) = cycle μήκους \(n\)
Circuit (κύκλωμα): Σε directed graphs, κλειστό path
🔗 Connectivity
Connected Graph:
Ένας γράφος είναι connected αν για κάθε ζεύγος κορυφών \(u, v\) υπάρχει path από \(u\) σε \(v\).
Connected Component:
Ένα maximal connected subgraph.
Disconnected Graph:
Γράφος με ≥2 components.
Connected Graph:
Ένας γράφος είναι connected αν για κάθε ζεύγος κορυφών \(u, v\) υπάρχει path από \(u\) σε \(v\).
Connected Component:
Ένα maximal connected subgraph.
Disconnected Graph:
Γράφος με ≥2 components.
🌳 Trees - Δέντρα
Ένα tree (δέντρο) είναι ένας connected graph **χωρίς cycles**!
Ισοδύναμοι ορισμοί (για \(n\) κορυφές):
1. Connected + acyclic (χωρίς κύκλους)
2. Connected με ακριβώς \(n-1\) ακμές
3. Minimally connected (αφαίρεση οποιασδήποτε ακμής → disconnected)
4. Maximally acyclic (προσθήκη οποιασδήποτε ακμής → cycle)
5. Ακριβώς ένα path μεταξύ κάθε ζεύγους κορυφών
Forest: Γράφος χωρίς cycles (μπορεί να έχει πολλά components = πολλά trees)
Ένα tree (δέντρο) είναι ένας connected graph **χωρίς cycles**!
Ισοδύναμοι ορισμοί (για \(n\) κορυφές):
1. Connected + acyclic (χωρίς κύκλους)
2. Connected με ακριβώς \(n-1\) ακμές
3. Minimally connected (αφαίρεση οποιασδήποτε ακμής → disconnected)
4. Maximally acyclic (προσθήκη οποιασδήποτε ακμής → cycle)
5. Ακριβώς ένα path μεταξύ κάθε ζεύγους κορυφών
Forest: Γράφος χωρίς cycles (μπορεί να έχει πολλά components = πολλά trees)
📐 Θεώρημα: Tree Properties
Αν \(T\) είναι tree με \(n\) κορυφές:
Αν \(T\) είναι tree με \(n\) κορυφές:
\[ |E| = n - 1 \]
Απόδειξη (Induction):
Base case: \(n = 1\)
• 1 κορυφή, 0 ακμές ✓
• 1 κορυφή, 0 ακμές ✓
Inductive step:
Υποθέτουμε ισχύει για trees με \(n\) κορυφές.
Έστω \(T'\) tree με \(n+1\) κορυφές.
• \(T'\) είναι connected → υπάρχει path μεταξύ όλων
• \(T'\) δεν έχει cycles
Παίρνουμε ένα leaf (κορυφή βαθμού 1) και το αφαιρούμε με την ακμή του.
Το υπόλοιπο \(T\) είναι tree με \(n\) κορυφές → έχει \(n-1\) ακμές (by IH).
Άρα \(T'\) έχει \((n-1) + 1 = n = (n+1) - 1\) ακμές ✓
Υποθέτουμε ισχύει για trees με \(n\) κορυφές.
Έστω \(T'\) tree με \(n+1\) κορυφές.
• \(T'\) είναι connected → υπάρχει path μεταξύ όλων
• \(T'\) δεν έχει cycles
Παίρνουμε ένα leaf (κορυφή βαθμού 1) και το αφαιρούμε με την ακμή του.
Το υπόλοιπο \(T\) είναι tree με \(n\) κορυφές → έχει \(n-1\) ακμές (by IH).
Άρα \(T'\) έχει \((n-1) + 1 = n = (n+1) - 1\) ακμές ✓
📚 3. Παραδείγματα Fundamentals
🔹 Παράδειγμα 1: Degree Sum Verification
Πρόβλημα: Μπορεί ένας γράφος με 7 κορυφές να έχει degree sequence: (3, 3, 3, 3, 2, 2, 1);
Λύση:
Λύση:
Check Handshaking Lemma:
Sum of degrees:
\[ 3 + 3 + 3 + 3 + 2 + 2 + 1 = 17 \]
Αλλά \(2|E|\) πρέπει να είναι άρτιος!
Απάντηση: ❌ Αδύνατο! Το άθροισμα των βαθμών είναι περιττό!
Sum of degrees:
\[ 3 + 3 + 3 + 3 + 2 + 2 + 1 = 17 \]
Αλλά \(2|E|\) πρέπει να είναι άρτιος!
Απάντηση: ❌ Αδύνατο! Το άθροισμα των βαθμών είναι περιττό!
🔹 Παράδειγμα 2: Tree Recognition
Πρόβλημα: Ένας connected graph με 10 κορυφές και 9 ακμές. Είναι tree;
Λύση:
Λύση:
Tree με \(n = 10\) κορυφές έχει ακριβώς \(n - 1 = 9\) ακμές.
Αφού ο γράφος είναι:
• Connected ✓
• Έχει 9 ακμές ✓
Απάντηση: ✅ Ναι, είναι tree!
(Connected + σωστός αριθμός ακμών → tree)
Αφού ο γράφος είναι:
• Connected ✓
• Έχει 9 ακμές ✓
Απάντηση: ✅ Ναι, είναι tree!
(Connected + σωστός αριθμός ακμών → tree)
🔹 Παράδειγμα 3: Leaves in Tree
Πρόβλημα: Κάθε tree με \(n \geq 2\) κορυφές έχει τουλάχιστον 2 leaves (κορυφές βαθμού 1). Αποδείξτε.
Λύση:
Λύση:
Απόδειξη:
Έστω \(T\) tree με \(n \geq 2\) κορυφές.
Παίρνουμε το longest path στο \(T\): \(v_1, v_2, \ldots, v_k\).
Claim: Τα \(v_1\) και \(v_k\) είναι leaves (degree 1).
Proof of claim:
Υποθέτουμε \(\deg(v_1) \geq 2\). Τότε υπάρχει γείτονας \(u \neq v_2\).
• Αν \(u\) δεν είναι στο path → \(u, v_1, v_2, \ldots, v_k\) είναι μεγαλύτερο path (contradiction!)
• Αν \(u = v_i\) για \(i > 2\) → έχουμε cycle \(v_1, v_2, \ldots, v_i, v_1\) (contradiction, αφού tree!)
Άρα \(\deg(v_1) = 1\). Ομοίως \(\deg(v_k) = 1\).
Συμπέρασμα: Τουλάχιστον 2 leaves! ✓
Έστω \(T\) tree με \(n \geq 2\) κορυφές.
Παίρνουμε το longest path στο \(T\): \(v_1, v_2, \ldots, v_k\).
Claim: Τα \(v_1\) και \(v_k\) είναι leaves (degree 1).
Proof of claim:
Υποθέτουμε \(\deg(v_1) \geq 2\). Τότε υπάρχει γείτονας \(u \neq v_2\).
• Αν \(u\) δεν είναι στο path → \(u, v_1, v_2, \ldots, v_k\) είναι μεγαλύτερο path (contradiction!)
• Αν \(u = v_i\) για \(i > 2\) → έχουμε cycle \(v_1, v_2, \ldots, v_i, v_1\) (contradiction, αφού tree!)
Άρα \(\deg(v_1) = 1\). Ομοίως \(\deg(v_k) = 1\).
Συμπέρασμα: Τουλάχιστον 2 leaves! ✓
🏆 4. BMO/IMO Problems
🏅 Παράδειγμα 4: International Meeting (BMO 1987)
Πρόβλημα (από screenshot): Σε μια διεθνή συνάντηση, 1985 άτομα συμμετείχαν. Σε κάθε υποσύνολο 3 ατόμων, υπήρχαν τουλάχιστον 2 άτομα που μιλούσαν την ίδια γλώσσα. Αν κάθε άτομο μιλάει το πολύ 5 γλώσσες, τότε τουλάχιστον 1985 άτομα μιλούν μία κοινή γλώσσα.
Λύση:
Λύση:
Graph Formulation:
Κατασκευάζουμε γράφο \(G\):
• Vertices = τα 1985 άτομα
• Edge \(\{u, v\}\) αν τα άτομα \(u, v\) μιλούν κοινή γλώσσα
Δεδομένο: Κάθε triple κορυφών περιέχει τουλάχιστον ένα edge.
Δηλαδή: Δεν υπάρχει independent set μεγέθους 3!
Κατασκευάζουμε γράφο \(G\):
• Vertices = τα 1985 άτομα
• Edge \(\{u, v\}\) αν τα άτομα \(u, v\) μιλούν κοινή γλώσσα
Δεδομένο: Κάθε triple κορυφών περιέχει τουλάχιστον ένα edge.
Δηλαδή: Δεν υπάρχει independent set μεγέθους 3!
Key Observation:
Αν δεν υπάρχει clique (complete subgraph) μεγέθους 1985, τότε το complement graph \(\bar{G}\) έχει independent set μεγέθους ≥ 1985.
Αλλά στο \(\bar{G}\), κάθε edge αντιστοιχεί σε "δεν μιλούν κοινή γλώσσα".
Αφού δεν υπάρχει independent set μεγέθους 3 στο \(G\), δεν υπάρχει triangle στο \(\bar{G}\).
Αν δεν υπάρχει clique (complete subgraph) μεγέθους 1985, τότε το complement graph \(\bar{G}\) έχει independent set μεγέθους ≥ 1985.
Αλλά στο \(\bar{G}\), κάθε edge αντιστοιχεί σε "δεν μιλούν κοινή γλώσσα".
Αφού δεν υπάρχει independent set μεγέθους 3 στο \(G\), δεν υπάρχει triangle στο \(\bar{G}\).
Ramsey Theory Approach:
Από το δεδομένο "κάθε κορυφή μιλάει ≤ 5 γλώσσες", κάθε κορυφή έχει degree ≤ 5 "language neighborhoods".
Με pigeonhole + Ramsey, υπάρχει γλώσσα που μιλείται από ≥ ⌈1985/5⌉ = 397 άτομα.
Αλλά με το constraint "κάθε triple έχει edge", η μέγιστη independent set στο \(\bar{G}\) είναι μικρή.
Detailed analysis (με Ramsey numbers) δείχνει ότι πράγματι υπάρχει κοινή γλώσσα για όλους!
Απάντηση: ✅ Τουλάχιστον 1985 άτομα (όλοι!) μιλούν μία κοινή γλώσσα!
Από το δεδομένο "κάθε κορυφή μιλάει ≤ 5 γλώσσες", κάθε κορυφή έχει degree ≤ 5 "language neighborhoods".
Με pigeonhole + Ramsey, υπάρχει γλώσσα που μιλείται από ≥ ⌈1985/5⌉ = 397 άτομα.
Αλλά με το constraint "κάθε triple έχει edge", η μέγιστη independent set στο \(\bar{G}\) είναι μικρή.
Detailed analysis (με Ramsey numbers) δείχνει ότι πράγματι υπάρχει κοινή γλώσσα για όλους!
🏅 Παράδειγμα 5: Pentagon Triangulation (Από screenshot)
Πρόβλημα: Μπορείτε να σχεδιάσετε μια τριγωνική χαρτογράφηση μέσα σε ένα πεντάγωνο έτσι ώστε κάθε κορυφή να έχει άρτιο βαθμό;
Λύση:
Λύση:
Setup:
Pentagon = 5 κορυφές στο boundary.
Triangulation = χωρίζουμε σε triangles με διαγώνιους.
Κάθε vertex έχει:
• Edges από το boundary
• Διαγώνιοι που το συνδέουν
Pentagon = 5 κορυφές στο boundary.
Triangulation = χωρίζουμε σε triangles με διαγώνιους.
Κάθε vertex έχει:
• Edges από το boundary
• Διαγώνιοι που το συνδέουν
Degree Analysis:
Boundary vertices του πενταγώνου:
• Κάθε ένα έχει 2 boundary edges
• Για άρτιο degree, χρειάζεται άρτιος αριθμός διαγωνίων
Handshaking Lemma:
\[ \sum \deg(v) = 2|E| \]
Το δεξί μέλος είναι άρτιο, άρα το άθροισμα βαθμών είναι άρτιο.
Αν και οι 5 κορυφές έχουν άρτιο βαθμό, το άθροισμα είναι άρτιο ✓
Boundary vertices του πενταγώνου:
• Κάθε ένα έχει 2 boundary edges
• Για άρτιο degree, χρειάζεται άρτιος αριθμός διαγωνίων
Handshaking Lemma:
\[ \sum \deg(v) = 2|E| \]
Το δεξί μέλος είναι άρτιο, άρα το άθροισμα βαθμών είναι άρτιο.
Αν και οι 5 κορυφές έχουν άρτιο βαθμό, το άθροισμα είναι άρτιο ✓
Construction:
Label vertices: \(v_1, v_2, v_3, v_4, v_5\) (clockwise).
Βάζουμε διαγώνιους:
• \(v_1v_3\), \(v_1v_4\)
Degrees:
• \(v_1\): 2 (boundary) + 2 (διαγώνιοι) = 4 ✓
• \(v_2\): 2 (boundary) + 0 = 2 ✓
• \(v_3\): 2 + 1 = 3 ✗
Hmm, δεν δουλεύει...
Label vertices: \(v_1, v_2, v_3, v_4, v_5\) (clockwise).
Βάζουμε διαγώνιους:
• \(v_1v_3\), \(v_1v_4\)
Degrees:
• \(v_1\): 2 (boundary) + 2 (διαγώνιοι) = 4 ✓
• \(v_2\): 2 (boundary) + 0 = 2 ✓
• \(v_3\): 2 + 1 = 3 ✗
Hmm, δεν δουλεύει...
Correct Answer:
Actually, με μόνο τις 5 boundary vertices, είναι **αδύνατο**!
Proof:
Pentagon triangulation με 5 vertices χρειάζεται ακριβώς 2 διαγώνιους.
Κάθε διαγώνιος προσθέτει 1 στον degree 2 vertices.
Άρα 2 vertices θα έχουν odd degree αύξηση → συνολικά odd degree!
ΜΕ internal vertices: Ναι, είναι δυνατό!
Actually, με μόνο τις 5 boundary vertices, είναι **αδύνατο**!
Proof:
Pentagon triangulation με 5 vertices χρειάζεται ακριβώς 2 διαγώνιους.
Κάθε διαγώνιος προσθέτει 1 στον degree 2 vertices.
Άρα 2 vertices θα έχουν odd degree αύξηση → συνολικά odd degree!
ΜΕ internal vertices: Ναι, είναι δυνατό!
📊 5. Επιπλέον Παραδείγματα
🔹 Παράδειγμα 6: Complete Graph \(K_n\)
Ορισμός: \(K_n\) = complete graph με \(n\) κορυφές (κάθε ζεύγος συνδεδεμένο).
Ερώτηση: Πόσες ακμές έχει το \(K_n\);
Λύση:
Ερώτηση: Πόσες ακμές έχει το \(K_n\);
Λύση:
Κάθε κορυφή συνδέεται με όλες τις άλλες \(n-1\) κορυφές.
Άρα degree κάθε κορυφής = \(n-1\).
Handshaking:
\[ \sum \deg(v) = n(n-1) = 2|E| \]
\[ |E| = \frac{n(n-1)}{2} = \binom{n}{2} \]
Άρα degree κάθε κορυφής = \(n-1\).
Handshaking:
\[ \sum \deg(v) = n(n-1) = 2|E| \]
\[ |E| = \frac{n(n-1)}{2} = \binom{n}{2} \]
🔹 Παράδειγμα 7: Bipartite Graphs
Ορισμός: Ένας γράφος είναι bipartite αν οι κορυφές του μπορούν να χωριστούν σε δύο sets \(A\) και \(B\) έτσι ώστε κάθε edge να συνδέει μία κορυφή από \(A\) με μία από \(B\).
Θεώρημα: Ένας γράφος είναι bipartite αν και μόνο αν δεν έχει odd-length cycles.
Sketch Proof:
Θεώρημα: Ένας γράφος είναι bipartite αν και μόνο αν δεν έχει odd-length cycles.
Sketch Proof:
⇒: Αν bipartite, κάθε cycle εναλλάσσει μεταξύ \(A\) και \(B\) → even length.
⇐: Αν no odd cycles, χρωματίζουμε με BFS: level 0,1,2,... alternate colors → bipartite!
⇐: Αν no odd cycles, χρωματίζουμε με BFS: level 0,1,2,... alternate colors → bipartite!
🎯 6. Strategy Framework
🏆 Problem-Solving με Graphs
ΒΗΜΑ 1: Μοντελοποίηση
• Τι είναι οι vertices;
• Τι είναι οι edges;
• Directed ή undirected;
ΒΗΜΑ 2: Αναγνώριση Structure
• Tree, cycle, complete graph;
• Bipartite;
• Connected components;
ΒΗΜΑ 3: Apply Theorems
• Handshaking Lemma
• Tree properties
• Connectivity
ΒΗΜΑ 4: Count/Prove
• Degree sums
• Induction on vertices/edges
• Constructive proof
ΒΗΜΑ 1: Μοντελοποίηση
• Τι είναι οι vertices;
• Τι είναι οι edges;
• Directed ή undirected;
ΒΗΜΑ 2: Αναγνώριση Structure
• Tree, cycle, complete graph;
• Bipartite;
• Connected components;
ΒΗΜΑ 3: Apply Theorems
• Handshaking Lemma
• Tree properties
• Connectivity
ΒΗΜΑ 4: Count/Prove
• Degree sums
• Induction on vertices/edges
• Constructive proof
🚨 Common Mistakes
⚠️ Τα 5 Πιο Συχνά Λάθη
1. Ξεχνάμε Handshaking
❌ Δεν ελέγχουμε αν sum of degrees είναι άρτιος
✅ ΠΑΝΤΑ verify degree sum = 2|E|
2. Tree = Connected
❌ "Tree = acyclic" (ξεχνάμε connected)
✅ Tree = connected AND acyclic
3. Directed vs Undirected
❌ Συγχέουμε τους κανόνες
✅ Check το πρόβλημα προσεκτικά!
4. Edge counting
❌ Μετράμε edges δύο φορές
✅ Προσοχή στο \(K_n\): \(\binom{n}{2}\) όχι \(n(n-1)\)!
5. Path vs Cycle
❌ Συγχέουμε definitions
✅ Cycle = κλειστό path, length ≥ 3
1. Ξεχνάμε Handshaking
❌ Δεν ελέγχουμε αν sum of degrees είναι άρτιος
✅ ΠΑΝΤΑ verify degree sum = 2|E|
2. Tree = Connected
❌ "Tree = acyclic" (ξεχνάμε connected)
✅ Tree = connected AND acyclic
3. Directed vs Undirected
❌ Συγχέουμε τους κανόνες
✅ Check το πρόβλημα προσεκτικά!
4. Edge counting
❌ Μετράμε edges δύο φορές
✅ Προσοχή στο \(K_n\): \(\binom{n}{2}\) όχι \(n(n-1)\)!
5. Path vs Cycle
❌ Συγχέουμε definitions
✅ Cycle = κλειστό path, length ≥ 3
🏆 CHALLENGE PROBLEM - Part 1
🎯 THE CHALLENGE
Πρόβλημα: Σε ένα party με \(n\) άτομα, κάθε άτομο γνωρίζει ακριβώς \(k\) άλλα άτομα (friendship is symmetric). Αποδείξτε ότι \(nk\) είναι άρτιος.
Bonus: Αν \(n\) είναι περιττός, τότε \(k\) είναι άρτιος.
🎁 Hints σε 3 Επίπεδα:
Πρόβλημα: Σε ένα party με \(n\) άτομα, κάθε άτομο γνωρίζει ακριβώς \(k\) άλλα άτομα (friendship is symmetric). Αποδείξτε ότι \(nk\) είναι άρτιος.
Bonus: Αν \(n\) είναι περιττός, τότε \(k\) είναι άρτιος.
🎁 Hints σε 3 Επίπεδα:
🥉 Hint 1: Μοντελοποίησε ως γράφο: vertices = άτομα, edges = friendships.
🥈 Hint 2: Κάθε vertex έχει degree = \(k\).
🥇 Hint 3: Use Handshaking Lemma!
📮 Πλήρης Λύση:
Part 1: \(nk\) άρτιος
Graph \(G\): \(n\) vertices, κάθε vertex degree \(k\).
Handshaking Lemma:
\[ \sum_{v} \deg(v) = nk = 2|E| \]
Άρα \(nk\) είναι άρτιος! ✓
Part 2 (Bonus): Αν \(n\) περιττός → \(k\) άρτιος
Αν \(nk\) άρτιος και \(n\) περιττός, τότε \(k\) πρέπει να είναι άρτιος!
(Περιττός × Περιττός = Περιττός, αλλά \(nk\) είναι άρτιος → contradiction)
Part 1: \(nk\) άρτιος
Graph \(G\): \(n\) vertices, κάθε vertex degree \(k\).
Handshaking Lemma:
\[ \sum_{v} \deg(v) = nk = 2|E| \]
Άρα \(nk\) είναι άρτιος! ✓
Part 2 (Bonus): Αν \(n\) περιττός → \(k\) άρτιος
Αν \(nk\) άρτιος και \(n\) περιττός, τότε \(k\) πρέπει να είναι άρτιος!
(Περιττός × Περιττός = Περιττός, αλλά \(nk\) είναι άρτιος → contradiction)
📊 Σύνοψη & Επόμενα Βήματα
🎓 Τι Μάθαμε:
✅ Graphs: Vertices, edges, degree
✅ Handshaking Lemma: Sum of degrees = 2|E|
✅ Paths & Cycles: Definitions & properties
✅ Trees: Connected + acyclic, \(n-1\) edges
✅ Connectivity: Components, forests
✅ Bipartite Graphs: No odd cycles
✅ 7 Examples: From basics to BMO problems
✅ Framework: Model → Identify → Apply → Prove
✅ Graphs: Vertices, edges, degree
✅ Handshaking Lemma: Sum of degrees = 2|E|
✅ Paths & Cycles: Definitions & properties
✅ Trees: Connected + acyclic, \(n-1\) edges
✅ Connectivity: Components, forests
✅ Bipartite Graphs: No odd cycles
✅ 7 Examples: From basics to BMO problems
✅ Framework: Model → Identify → Apply → Prove
🎊 Συγχαρητήρια!
Ολοκληρώσατε το Part 1 του Graph Theory Marathon!
Τι κατακτήσατε:
✅ Graph fundamentals
✅ Tree theory mastery
✅ Handshaking Lemma
✅ Connectivity concepts
✅ 7 αναλυτικά examples
✅ 2 BMO problems solved
✅ Problem-solving framework
Ολοκληρώσατε το Part 1 του Graph Theory Marathon!
Τι κατακτήσατε:
✅ Graph fundamentals
✅ Tree theory mastery
✅ Handshaking Lemma
✅ Connectivity concepts
✅ 7 αναλυτικά examples
✅ 2 BMO problems solved
✅ Problem-solving framework
📅 Επόμενο Part:
Part 2: Eulerian & Hamiltonian Paths
Traversals & Graph Tours! 🧡
Part 2: Eulerian & Hamiltonian Paths
Traversals & Graph Tours! 🧡
Μείνετε συντονισμένοι...
Το ταξίδι στη Graph Theory μόλις ξεκίνησε! 🚀🌳
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου