🌳 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 αναλυτικά παραδείγματα
✅ Classic competition problems
✅ Competition framework

🤔 Γιατί Graph Theory;
Οι γράφοι μοντελοποιούν σχέσεις: φιλίες, δρόμους, συνδέσεις, εξαρτήσεις. Κάθε φορά που έχετε "αντικείμενα και σχέσεις μεταξύ τους", έχετε έναν γράφο! Αυτό τους κάνει απίστευτα 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\)

🎨 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

🔗 Βασικοί Όροι

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:

\[ \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: Όλες οι κορυφές διαφορετικές (εκτός ίσως πρώτης=τελευταίας)

📌 Cycles (Κύκλοι)

Ένας 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.

🌳 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\) κορυφές:

\[ |E| = n - 1 \]

Απόδειξη (Induction):

Base case: \(n = 1\)
• 1 κορυφή, 0 ακμές ✓

Inductive step:
Υποθέτουμε ισχύει για trees με \(n\) κορυφές.

Έστω \(T'\) tree με \(n+1\) κορυφές.
• \(T'\) είναι connected → υπάρχει path μεταξύ όλων
• \(T'\) δεν έχει cycles

Παίρνουμε ένα leaf (κορυφή βαθμού 1, υπάρχει πάντα — βλ. Παράδειγμα 3 παρακάτω) και το αφαιρούμε με την ακμή του.
Το υπόλοιπο \(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|\) πρέπει να είναι άρτιος!

Απάντηση: ❌ Αδύνατο! Το άθροισμα των βαθμών είναι περιττό!

🔹 Παράδειγμα 2: Tree Recognition Πρόβλημα: Ένας connected graph με 10 κορυφές και 9 ακμές. Είναι tree;

Λύση:

Tree με \(n = 10\) κορυφές έχει ακριβώς \(n - 1 = 9\) ακμές.

Αφού ο γράφος είναι:
• 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! ✓

🏆 4. Classic Competition Problems

🏅 Παράδειγμα 4: The Language Problem (1978 USAMO, Πρόβλημα 5) Πρόβλημα: Εννέα μαθηματικοί συναντιούνται σε ένα διεθνές συνέδριο και ανακαλύπτουν ότι, ανάμεσα σε οποιουσδήποτε τρεις από αυτούς, τουλάχιστον δύο μιλούν κοινή γλώσσα. Αν κάθε μαθηματικός μιλάει το πολύ 3 γλώσσες, αποδείξτε ότι υπάρχουν τουλάχιστον τρεις μαθηματικοί που μιλούν την ίδια γλώσσα.

Λύση:

Βήμα 1: Γράφος "μη-κοινής γλώσσας"

Κατασκευάζουμε γράφο \(\bar G\): 9 κορυφές (οι μαθηματικοί), ακμή \(\{u,v\}\) αν οι \(u,v\) δεν μιλούν καμία κοινή γλώσσα.

Η υπόθεση "ανάμεσα σε 3, τουλάχιστον 2 μοιράζονται γλώσσα" σημαίνει ακριβώς ότι το \(\bar G\) δεν έχει τρίγωνο (triangle-free) — τρεις αμοιβαία "ξένοι" θα ήταν τρίγωνο στο \(\bar G\).

Βήμα 2: Υποθέτουμε το αντίθετο

Ας υποθέσουμε ότι καμία γλώσσα δεν μιλιέται από ≥3 άτομα (δηλ. κάθε γλώσσα από ≤2).

Σταθεροποιούμε έναν μαθηματικό \(A\). Μιλάει το πολύ 3 γλώσσες, και κάθε μία μιλιέται από το πολύ 1 άλλο άτομο (αφού συνολικά ≤2 ανά γλώσσα). Άρα ο \(A\) μοιράζεται γλώσσα με το πολύ 3 άλλα άτομα.

Άρα ο \(A\) ΔΕΝ μοιράζεται γλώσσα με τουλάχιστον \(9-1-3=5\) άτομα — δηλαδή \(\deg_{\bar G}(A) \geq 5\).

Βήμα 3: Μέτρημα ακμών + Θεώρημα Mantel

Αφού κάθε κορυφή έχει βαθμό \(\geq 5\) στο \(\bar G\):
\[ |E(\bar G)| \geq \frac{9 \times 5}{2} = 22.5 \;\Rightarrow\; |E(\bar G)| \geq 23 \]

Όμως από το Θεώρημα του Mantel, ένας triangle-free γράφος με 9 κορυφές έχει το πολύ \(\lfloor 9^2/4 \rfloor = 20\) ακμές.

\(23 > 20\) — άτοπο!

Άρα η αρχική μας υπόθεση ήταν λάθος: υπάρχει γλώσσα που μιλιέται από τουλάχιστον 3 άτομα. \(\blacksquare\)

⚠️ Σημείωση διόρθωσης: Η αρχική εκδοχή ανέφερε "BMO 1987" με 1985 άτομα, ≤5 γλώσσες, και συμπέρασμα ότι όλοι μιλούν κοινή γλώσσα — αυτή η πηγή δεν επιβεβαιώθηκε (ελέγξαμε την πραγματική λίστα προβλημάτων IMO 1985, δεν ταιριάζει), και το συμπέρασμα ήταν ύποπτα ισχυρό χωρίς πραγματική απόδειξη. Αντικαταστάθηκε με το γνήσιο, επαληθευμένο 1978 USAMO Πρόβλημα 5, με πλήρη αυστηρή απόδειξη.

🏅 Παράδειγμα 5: Pentagon Triangulation Πρόβλημα: Μπορείτε να τριγωνοποιήσετε ένα κυρτό πεντάγωνο (χρησιμοποιώντας μόνο διαγώνιους, χωρίς εσωτερικά σημεία) έτσι ώστε όλες οι κορυφές να έχουν άρτιο βαθμό;

Λύση:

Setup:

Κάθε τριγωνοποίηση κυρτού πενταγώνου (χωρίς εσωτερικά σημεία) χρησιμοποιεί ακριβώς \(5-3=2\) διαγώνιους.

Ο βαθμός κάθε κορυφής = 2 (από τις δύο πλευρές του πενταγώνου) + (αριθμός διαγωνίων που την αγγίζουν).

Βασική Παρατήρηση:

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

Άρα η κατανομή "αριθμός διαγωνίων ανά κορυφή" είναι πάντα \(\{2,1,1,0,0\}\): μία κορυφή αγγίζεται από 2 διαγωνίους, δύο κορυφές από 1 η καθεμία, και δύο κορυφές από καμία.

Συμπέρασμα:

Οι δύο κορυφές με ακριβώς 1 διαγώνιο έχουν συνολικό βαθμό \(2+1=3\) — περιττό, ανεξάρτητα από το ποιες 2 μη τεμνόμενες διαγώνιοι επιλεγούν!

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

💡 Παράδειγμα επαλήθευσης: Με διαγώνιους \(1\text{-}3\) και \(1\text{-}4\) (fan από την κορυφή 1): βαθμοί = \(v_1{=}4, v_2{=}2, v_3{=}3, v_4{=}3, v_5{=}2\) — ακριβώς 2 περιττοί (\(v_3,v_4\)), όπως προβλέπει η ανάλυση.

📊 5. Επιπλέον Παραδείγματα

🔹 Παράδειγμα 6: Complete Graph \(K_n\) Ορισμός: \(K_n\) = complete graph με \(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} \]

🔹 Παράδειγμα 7: Bipartite Graphs Ορισμός: Ένας γράφος είναι bipartite αν οι κορυφές του μπορούν να χωριστούν σε δύο sets \(A\) και \(B\) έτσι ώστε κάθε edge να συνδέει μία κορυφή από \(A\) με μία από \(B\).

Θεώρημα: Ένας γράφος είναι bipartite αν και μόνο αν δεν έχει odd-length cycles.

Sketch Proof:

⇒: Αν bipartite, κάθε cycle εναλλάσσει μεταξύ \(A\) και \(B\) → even length.

⇐: Αν 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

🚨 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

🏆 CHALLENGE PROBLEM - Part 1

🎯 THE CHALLENGE

Πρόβλημα: Σε ένα 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)

📊 Σύνοψη & Επόμενα Βήματα

🎓 Τι Μάθαμε:

✅ 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 classic competition problems
✅ Framework: Model → Identify → Apply → Prove

🎊 Συγχαρητήρια!

Ολοκληρώσατε το Part 1 του Graph Theory Marathon!

Τι κατακτήσατε:
✅ Graph fundamentals
✅ Tree theory mastery
✅ Handshaking Lemma
✅ Connectivity concepts
✅ 7 αναλυτικά examples
✅ Classic problems solved
✅ Problem-solving framework

📅 Επόμενο Part:
Part 2: Eulerian & Hamiltonian Paths
Traversals & Graph Tours! 🧡

Μείνετε συντονισμένοι...
Το ταξίδι στη Graph Theory μόλις ξεκίνησε! 🚀🌳

📘

Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώ

PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify

📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα

Δες τα βιβλία →