Πόλεις και δρόμοι

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ · #1

Μία χώρα έχει

πόλεις. Κάθε δύο πόλεις ενώνονται μεταξύ τους με το πολύ έναν δρόμο.
Να βρεθεί το ελάχιστο πλήθος δρόμων(συναρτήσει του

) έτσι ώστε οποιαδήποτε και να είναι η θέση αυτών των δρόμων κάθε δύο πόλεις μπορούν να επικοινωνήσουν μεταξύ τους παρεμβάλλοντας το πολύ μία άλλη πόλη.

#2

Αν έχουμε $\binom{n-2}{2} + (n-1)$ δρόμους τότε σίγουρα θα ικανοποιείται η συνθήκη. Πράγματι, έστω δυο πόλεις A,B

. Οι υπόλοιπες n-2

πόλεις συνδέονται μεταξύ τους με το πολύ $\binom{n-2}{2}$ δρόμους. Οπότε υπάρχουν τουλάχιστον n-1

δρόμοι όπου τουλάχιστον το ένα άκρο τους είναι μια από τις πόλεις A,B

. Αν υπάρχει δρόμος μεταξύ των A,B

είμαιστε εντάξει. Αλλιώς κάθε ένας από αυτούς τους τουλάχιστον n-1

δρόμους έχει στο ένα άκρο μια από τις A,B

και στο άλλο άκρο κάποια άλλη πόλη εκτός των A,B

. Επειδή υπάρχουν τουλάχιστον n-1

δρόμοι και ακριβώς n-2

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

και μία με την

. Οπότε πάλι είμαστε εντάξει.

Τώρα θα δείξουμε ότι αν έχουμε λιγότερους από $\binom{n-2}{2} + (n-1)$ δρόμους τότε δεν ικανοποιείται απαραίτητα η συνθήκη. Πράγματι επειδή $\binom{n-2}{2} + (n-2) = \frac{(n-2)(n-3)}{2} + (n-2) = \frac{(n-2)(n-1)}{2} = \binom{n-1}{2}$ , ένα παράδειγμα που δεν ικανοποιείται η συνθήκη είναι να έχουμε μια πόλη ασύνδετη με όλες τις άλλες και τις υπόλοιπες n-1

πόλεις συνδεδεμένες ανά δύο μεταξύ τους.

MAnTH05 · #3

Μία παρατήρηση:
Θεωρώ πως θα μπορούσαμε να καταλήξουμε στο ίδιο αποτέλεσμα μεταφράζοντας το πρόβλημα σε όρους θεωρίας γραφημάτων.
Το ζητούμενο είναι ισοδύναμο με το εξής:
Ένα γράφημα (G)

έχει

κορυφές

. Κάθε δύο κορυφές συνδέονται μεταξύ τους με το πολύ μία ακμή (e)

.
Να βρεθεί το ελάχιστο πλήθος ακμών έτσι ώστε κάθε δύο κορυφές να συνδέονται μεταξύ τους παρεμβάλλοντας το πολύ μία άλλη κορυφή.

: γράφημα.png (112.09 KiB) Προβλήθηκε 2822 φορές

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ · #4

MAnTH05 έγραψε: ↑
Τρί Μαρ 09, 2021 9:23 pm
Μία παρατήρηση:
Θεωρώ πως θα μπορούσαμε να καταλήξουμε στο ίδιο αποτέλεσμα μεταφράζοντας το πρόβλημα σε όρους θεωρίας γραφημάτων.
Το ζητούμενο είναι ισοδύναμο με το εξής:
Ένα γράφημα έχει κορυφές . Κάθε δύο κορυφές συνδέονται μεταξύ τους με το πολύ μία ακμή .
Να βρεθεί το ελάχιστο πλήθος ακμών έτσι ώστε κάθε δύο κορυφές να συνδέονται μεταξύ τους παρεμβάλλοντας το πολύ μία άλλη κορυφή.

γράφημα.png

Πράγματι, γράφω μία λύση με όρους θεωρίας γραφημάτων:

Θεωρούμε το γράφημα G=(V,E)

με κορυφές τις πόλεις, έστω $V=\left \{u_1,..,u_n \right \}$
Δύο ακμές συνδέονται με ακμή αν υπάρχει δρόμος που τις ενώνει.
Αν είχαμε $\leq \dbinom {n-1}{2}$ δρόμους τότε κάνουμε την κατασκευή του κ. Δημήτρη.
Τώρα έστω ότι έχουμε $\dbinom {n-1}{2}+1(=|E|)$ δρόμους και ότι δεν έχουμε το ζητούμενο,
θα υπάρχουν τότε $u,w\in V$ ώστε $e(u_i,w) \not \in E, \forall u_i\in N(u)$ δηλαδή κάθε γειτονική κορυφή της

δεν συνδέεται με την

.
Τότε από το γράφημα λείπουν όλες οι ακμές $e(u_i,w), u_i\in N(u)$ καθώς και οι $e(u,u_j),u_ j\in V / N(u)$ οι οποίες συνολικά σε πλήθος είναι deg(u)+(n-1-deg(u))=n-1

δηλαδή $|E|\leq \dbinom{n}{2}-(n-1)=\dbinom {n-1}{2}$ άτοπο.

Πόλεις και δρόμοι

Πόλεις και δρόμοι

Re: Πόλεις και δρόμοι

Re: Πόλεις και δρόμοι

Re: Πόλεις και δρόμοι

Μέλη σε σύνδεση