Πόλεις και δρόμοι
Συντονιστές: Demetres, socrates, silouan
- ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ
- Δημοσιεύσεις: 921
- Εγγραφή: Πέμ Νοέμ 22, 2018 9:43 pm
Πόλεις και δρόμοι
Μία χώρα έχει πόλεις. Κάθε δύο πόλεις ενώνονται μεταξύ τους με το πολύ έναν δρόμο.
Να βρεθεί το ελάχιστο πλήθος δρόμων(συναρτήσει του ) έτσι ώστε οποιαδήποτε και να είναι η θέση αυτών των δρόμων κάθε δύο πόλεις μπορούν να επικοινωνήσουν μεταξύ τους παρεμβάλλοντας το πολύ μία άλλη πόλη.
Να βρεθεί το ελάχιστο πλήθος δρόμων(συναρτήσει του ) έτσι ώστε οποιαδήποτε και να είναι η θέση αυτών των δρόμων κάθε δύο πόλεις μπορούν να επικοινωνήσουν μεταξύ τους παρεμβάλλοντας το πολύ μία άλλη πόλη.
Λέξεις Κλειδιά:
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: Πόλεις και δρόμοι
Αν έχουμε δρόμους τότε σίγουρα θα ικανοποιείται η συνθήκη. Πράγματι, έστω δυο πόλεις . Οι υπόλοιπες πόλεις συνδέονται μεταξύ τους με το πολύ δρόμους. Οπότε υπάρχουν τουλάχιστον δρόμοι όπου τουλάχιστον το ένα άκρο τους είναι μια από τις πόλεις . Αν υπάρχει δρόμος μεταξύ των είμαιστε εντάξει. Αλλιώς κάθε ένας από αυτούς τους τουλάχιστον δρόμους έχει στο ένα άκρο μια από τις και στο άλλο άκρο κάποια άλλη πόλη εκτός των . Επειδή υπάρχουν τουλάχιστον δρόμοι και ακριβώς άλλες πόλεις, τουλάχιστον μια από τις πόλεις θα εμφανίζεται τουλάχιστον δύο φορές ως άκρο αυτών των δρόμων. Τότε όμως θα εμφανίζεται ακριβώς δύο φορές. Μία συνδεδεμένη με την και μία με την . Οπότε πάλι είμαστε εντάξει.
Τώρα θα δείξουμε ότι αν έχουμε λιγότερους από δρόμους τότε δεν ικανοποιείται απαραίτητα η συνθήκη. Πράγματι επειδή , ένα παράδειγμα που δεν ικανοποιείται η συνθήκη είναι να έχουμε μια πόλη ασύνδετη με όλες τις άλλες και τις υπόλοιπες πόλεις συνδεδεμένες ανά δύο μεταξύ τους.
Τώρα θα δείξουμε ότι αν έχουμε λιγότερους από δρόμους τότε δεν ικανοποιείται απαραίτητα η συνθήκη. Πράγματι επειδή , ένα παράδειγμα που δεν ικανοποιείται η συνθήκη είναι να έχουμε μια πόλη ασύνδετη με όλες τις άλλες και τις υπόλοιπες πόλεις συνδεδεμένες ανά δύο μεταξύ τους.
Re: Πόλεις και δρόμοι
Μία παρατήρηση:
Θεωρώ πως θα μπορούσαμε να καταλήξουμε στο ίδιο αποτέλεσμα μεταφράζοντας το πρόβλημα σε όρους θεωρίας γραφημάτων.
Το ζητούμενο είναι ισοδύναμο με το εξής:
Ένα γράφημα έχει κορυφές . Κάθε δύο κορυφές συνδέονται μεταξύ τους με το πολύ μία ακμή .
Να βρεθεί το ελάχιστο πλήθος ακμών έτσι ώστε κάθε δύο κορυφές να συνδέονται μεταξύ τους παρεμβάλλοντας το πολύ μία άλλη κορυφή.
Θεωρώ πως θα μπορούσαμε να καταλήξουμε στο ίδιο αποτέλεσμα μεταφράζοντας το πρόβλημα σε όρους θεωρίας γραφημάτων.
Το ζητούμενο είναι ισοδύναμο με το εξής:
Ένα γράφημα έχει κορυφές . Κάθε δύο κορυφές συνδέονται μεταξύ τους με το πολύ μία ακμή .
Να βρεθεί το ελάχιστο πλήθος ακμών έτσι ώστε κάθε δύο κορυφές να συνδέονται μεταξύ τους παρεμβάλλοντας το πολύ μία άλλη κορυφή.
Ματθαίος Κουκλέρης
- ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ
- Δημοσιεύσεις: 921
- Εγγραφή: Πέμ Νοέμ 22, 2018 9:43 pm
Re: Πόλεις και δρόμοι
Πράγματι, γράφω μία λύση με όρους θεωρίας γραφημάτων:MAnTH05 έγραψε: ↑Τρί Μαρ 09, 2021 9:23 pmΜία παρατήρηση:
Θεωρώ πως θα μπορούσαμε να καταλήξουμε στο ίδιο αποτέλεσμα μεταφράζοντας το πρόβλημα σε όρους θεωρίας γραφημάτων.
Το ζητούμενο είναι ισοδύναμο με το εξής:
Ένα γράφημα έχει κορυφές . Κάθε δύο κορυφές συνδέονται μεταξύ τους με το πολύ μία ακμή .
Να βρεθεί το ελάχιστο πλήθος ακμών έτσι ώστε κάθε δύο κορυφές να συνδέονται μεταξύ τους παρεμβάλλοντας το πολύ μία άλλη κορυφή.
γράφημα.png
Θεωρούμε το γράφημα με κορυφές τις πόλεις, έστω
Δύο ακμές συνδέονται με ακμή αν υπάρχει δρόμος που τις ενώνει.
Αν είχαμε δρόμους τότε κάνουμε την κατασκευή του κ. Δημήτρη.
Τώρα έστω ότι έχουμε δρόμους και ότι δεν έχουμε το ζητούμενο,
θα υπάρχουν τότε ώστε δηλαδή κάθε γειτονική κορυφή της δεν συνδέεται με την .
Τότε από το γράφημα λείπουν όλες οι ακμές καθώς και οι οι οποίες συνολικά σε πλήθος είναι δηλαδή άτοπο.
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 5 επισκέπτες