Αεροπορικές Γραμμές στο Aerostan – Ένα Πρόβλημα Θεωρίας Γράφων

📌 Το Πρόβλημα

Η χώρα Aerostan διαθέτει 15 πόλεις και τρεις αεροπορικές εταιρείες. Κάθε εταιρεία εκτελεί πτήσεις μεταξύ ορισμένων ζευγών πόλεων.

Ποιος είναι ο ελάχιστος δυνατός συνολικός αριθμός αεροπορικών γραμμών, ώστε ακόμη και αν χρεοκοπήσει οποιαδήποτε από τις τρεις εταιρείες, το υπόλοιπο δίκτυο να παραμένει συνδεδεμένο;

🔎 Μαθηματική Μοντελοποίηση

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

Ένα συνεκτικό γράφημα με n κορυφές απαιτεί τουλάχιστον n − 1 ακμές. Για 15 πόλεις:

15 − 1 = 14

Άρα, μετά την αφαίρεση οποιασδήποτε εταιρείας, οι υπόλοιπες δύο μαζί πρέπει να διαθέτουν τουλάχιστον 14 ακμές ώστε να διατηρείται η συνδεσιμότητα.

🧠 Η Κρίσιμη Ιδέα

Αν κάθε εταιρεία διαθέτει x γραμμές, τότε μετά τη χρεοκοπία μιας εταιρείας απομένουν 2x γραμμές.

Για να παραμένει το δίκτυο συνδεδεμένο απαιτείται:

2x ≥ 14

Άρα:

x ≥ 7

Κάθε εταιρεία πρέπει επομένως να διαθέτει τουλάχιστον 7 γραμμές.

✅ Τελικός Υπολογισμός

Αφού υπάρχουν 3 εταιρείες, ο ελάχιστος συνολικός αριθμός γραμμών είναι:

3 × 7 = 21

Απάντηση: 21 αεροπορικές γραμμές.

✨ Μαθηματική Σημασία

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

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