Θεωρία Γραφημάτων και Εφαρμογές — Ιανουάριος 2019¶
Μεταγραφή από το αρχείο του eClass «Εξεταση Ιανουαριου 2019 - Απαντησεις.pdf».
Εξεταση Ιανουαριου 2019 - Απαντησεις.pdf¶
Θεωρία Γραφημάτων και Εφαρμογές - Διακριτά Μαθηματικά ΙΙ - Ιανουάριος 2019
ΕΓΘΑ : Σ. Κοσμαδάκης, «Εισαγωγή στα Γραφήματα, Θεωρία-Ασκήσεις».
Στα ερωτήματα 1 ώς και 6, το Γ είναι οποιοδήποτε μη-κατευθυνόμενο συνεκτικό γράφημα.
1α Έστω ότι \(c_1, c_2, c_3\) είναι κύκλοι του Γ, και \(c_3 = c_1 \oplus c_2\). Αποδείξτε ότι: \(c_1 \oplus (c_2 \oplus c_3) = \emptyset\) (κενό γράφημα).
1β Υποθέτουμε ότι το Γ έχει \(n\) κορυφές και \(n+1\) ακμές, και ότι έχει τρείς κύκλους, \(c_1, c_2, c_3\), διαφορετικούς μεταξύ τους. Αποδείξτε ότι: \(c_1 \oplus (c_2 \oplus c_3) = \emptyset\). Μπορείτε να χρησιμοποιήσετε το (α).
2α Υποθέτουμε ότι οι βαθμοί των κορυφών του Γ είναι όλοι μεγαλύτεροι από 2. Αποδείξτε ότι: στο Γ θα υπάρχουν τουλάχιστον δύο (διαφορετικοί) κύκλοι.
2β Βρείτε άν ισχύει πάντα ότι: Άν οι βαθμοί των κορυφών του Γ είναι όλοι μεγαλύτεροι από 2, κάθε ακμή του Γ θα περιέχεται σε κύκλο.
Στο παρακάτω γράφημα κάθε κορυφή έχει βαθμό 3, και η ακμή \(\{A, B\}\) δεν περιέχεται σε κύκλο.
[Σχήμα: γράφημα με κορυφές βαθμού 3, που αποτελείται από δύο όμοια τμήματα (αριστερά και δεξιά). Τα τμήματα συνδέονται με την οριζόντια ακμή {Α, Β}: η Α ανήκει στο αριστερό τμήμα και η Β στο δεξιό. Η ακριβής σύνδεση των υπολοίπων κορυφών των τμημάτων δεν αποδίδεται πλήρως.]
3 Αποδείξτε ότι: Υπάρχει κλειστή διαδρομή του Γ, όπου κάθε ακμή του εμφανίζεται ακριβώς δύο φορές. Χρησιμοποιείστε την επαγωγή για τα συνεκτικά γραφήματα.
4 Υποθέτουμε ότι το Γ είναι δέντρο, και ότι ο βαθμός κάθε κορυφής του είναι \(\geq 1\) και \(\leq 3\). Αποδείξτε ότι: (ο αριθμός των κορυφών βαθμού 1) − (ο αριθμός των κορυφών βαθμού 3) = 2. Χρησιμοποιείστε την επαγωγή για τα δέντρα.
5 Έστω Δ ένα άκυκλο υπογράφημα του Γ. Αποδείξτε ότι: Υπάρχει υπογράφημα Τ του Γ που είναι δέντρο, και που περιέχει το Δ.
6 Έστω Η μία δισυνεκτική συνιστώσα του Γ ως προς ακμές, Θ μία δισυνεκτική συνιστώσα του Γ ως προς κορυφές.
α Αποδείξτε ότι: άν το Η περιέχεται στο Θ, θα είναι Η = Θ.
β Βρείτε άν ισχύει πάντα ότι: άν το Θ περιέχεται στο Η, θα είναι Η = Θ.
Στα ερωτήματα 7 και 8, υποθέτουμε ότι το Γ είναι οποιοδήποτε κατευθυνόμενο ισχυρά συνεκτικό γράφημα.
7 Βρείτε άν ισχύει πάντα ότι: Κάθε ακμή του Γ θα περιέχεται σε κύκλο.
8 Βρείτε άν ισχύει πάντα ότι: Υπάρχει μία κλειστή διαδρομή του Γ, που περιέχει όλες τις κορυφές του.
Λύσεις (🟢 official)
Κατάσταση: 🟢 official Πηγή: eClass μαθήματος, αρχείο «Θέματα Εξετάσεων και Απαντήσεις» (Εξεταση Ιανουαριου 2019 - Απαντησεις.pdf)
Λύσεις — Θεωρία Γραφημάτων και Εφαρμογές — Ιανουάριος 2019¶
Οι λύσεις μεταφέρονται από το αρχείο του eClass όπως είναι, χωρίς αλλαγές.
Εξεταση Ιανουαριου 2019 - Απαντησεις.pdf¶
Θεωρία Γραφημάτων και Εφαρμογές - Διακριτά Μαθηματικά ΙΙ Ιανουάριος 2019¶
ΕΓΘΑ : Σ. Κοσμαδάκης, «Εισαγωγή στα Γραφήματα, Θεωρία-Ασκήσεις».
Στα ερωτήματα 1 ώς και 6, το Γ είναι οποιοδήποτε μη-κατευθυνόμενο συνεκτικό γράφημα
1α Έστω ότι c1, c2, c3 είναι κύκλοι του Γ, και c3 = c1c2. Αποδείξτε ότι: c1(c2c3) = (κενό γράφημα).
Έστω Εi το σύνολο των ακμών που διατρέχει ο κύκλος ci , i = 1,2,3. Από τον ορισμό του αθροίσματος κύκλων – βλέπε ΕΓΘΑ 3.3 – και χρησιμοποιώντας την υπόθεση παίρνουμε Ε3 = Ε1 Ε2 . Για να δείξουμε ότι c1 (c2 c3) = (κενό γράφημα), αρκεί να δείξουμε ότι Ε1 (Ε2 Ε3) = (κενό σύνολο).
Α Τρόπος Αντικαθιστούμε το Ε3 με το Ε1 Ε2 , και χρησιμοποιούμε την προσεταιριστικότητα της συμμετρικής διαφοράς συνόλων – βλέπε ΕΓΘΑ 1.1 Ερώτημα 2 : Ε1 (Ε2 Ε3) = Ε1 (Ε2 (Ε1 Ε2)) = (Ε1 Ε2) (Ε1 Ε2) . Έχουμε ότι Α A = (Α A)U(A Α) = U = για οποιοδήποτε σύνολο Α , επομένως (Ε1 Ε2) (Ε1 Ε2) = .
Β Τρόπος Αντικαθιστούμε το Ε3 με το Ε1 Ε2 , και χρησιμοποιούμε την Άσκηση 9 ΕΓΘΑ 3.4 : το σύνολο Ε1 (Ε2 Ε3) = Ε1 (Ε2 (Ε1 Ε2)) θα αποτελείται από τις ακμές που ανήκουν σε περιττό αριθμό όρων της παράστασης Ε1 (Ε2 (Ε1 Ε2)) .
Kάθε ακμή που είναι κοινή στους c1 , c2 θα ανήκει και στους τέσσερις όρους της παράστασης, κάθε ακμή που ανήκει μόνο στον c1 θα ανήκει σε ακριβώς δύο όρους (τον πρώτο και τον τρίτο), και κάθε ακμή που ανήκει μόνο στον c2 θα ανήκει επίσης σε ακριβώς δύο όρους (τον δεύτερο και τον τέταρτο). Επομένως δεν υπάρχει ακμή που να ανήκει σε περιττό αριθμό όρων της παράστασης Ε1 (Ε2 (Ε1 Ε2)) , που σημαίνει ότι η τιμή της είναι .
1β Υποθέτουμε ότι το Γ έχει n κορυφές και n+1 ακμές, και ότι έχει τρείς κύκλους, c1, c2, c3, διαφορετικούς μεταξύ τους. Αποδείξτε ότι: c1(c2c3) = . Μπορείτε να χρησιμοποιήσετε το (α) .
To Γ θα έχει ακριβώς (n+1) n 1= 2 χορδές ως προς κάποιο (τυχαίο) δέντρο επικάλυψης Τ – βλέπε ΕΓΘΑ 3.3. Επομένως υπάρχουν ακριβώς δύο στοιχειώδεις κύκλοι ως προς το Τ .
Επειδή η τιμή της παράστασης c1 (c2 c3) δεν θα αλλάξει άν αλλάξουμε τη σειρά των ορισμάτων – βλέπε Άσκηση 9 ΕΓΘΑ 3.4 – μπορούμε να θεωρήσουμε, χωρίς βλάβη της γενικότητας, ότι οι στοιχειώδεις κύκλοι του Γ ως προς το Τ είναι οι c1, c2 . Από την Πρόταση 3.3.1 ΕΓΘΑ 3.3 έχουμε ότι: κάθε κύκλος του Γ που δεν είναι στοιχειώδης θα είναι άθροισμα στοιχειωδών, άρα c3 = c1 c2 . Όπως στο (α) , καταλήγουμε ότι c1 (c2 c3) = .
2α Υποθέτουμε ότι οι βαθμοί των κορυφών του Γ είναι όλοι μεγαλύτεροι από 2. Αποδείξτε ότι: στο Γ θα υπάρχουν τουλάχιστον δύο (διαφορετικοί) κύκλοι.
Α Τρόπος Από την Πρόταση 2.4.1 ΕΓΘΑ 2.4, υπάρχει μία τουλάχιστον κορυφή u του Γ που δεν είναι κομβικό σημείο. Aπό την υπόθεση υπάρχουν 3 διαφορετικές ακμές του Γ, έστω e1, e2, e3, που προσπίπτουν στην κορυφή u.
Από την Πρόταση 2.3.2 ΕΓΘΑ 2.3, αν επιλέξουμε οποιεσδήποτε δύο (τυχαίες) ακμές που προσπίπτουν στην u, θα περιέχονται στον ίδιο κύκλο. Άρα υπάρχει ένας κύκλος που περιέχει τις e1, e2, και ένας κύκλος που περιέχει τις e1, e3. Αυτοί οι δύο κύκλοι είναι διαφορετικοί, αφού δεν μπορεί να υπάρξει κύκλος που να περιέχει ταυτόχρονα και τις τρείς ακμές, λόγω του κοινού τους άκρου u.
Β Τρόπος Έστω ότι το Γ έχει n κορυφές και m ακμές. Από την Άσκηση 1 ΕΓΘΑ 2.5 3n 2m , αφού κάθε βαθμός είναι τουλάχιστον 3. Ακόμα n 4 , αφού δεν υπάρχουν πολλαπλές ακμές ή βρόχοι. To Γ θα έχει ακριβώς m n 1 χορδές / στοιχειώδεις κύκλους ως προς οποιοδήποτε δέντρο επικάλυψης Τ – βλέπε ΕΓΘΑ 3.3. Επειδή m n 1 ½(3n) n + 1 = ½n + 1 , και επίσης n 4 , έχουμε m n 1 3 – άρα θα υπάρχουν τουλάχιστον 3 χορδές / στοιχειώδεις κύκλοι. Οι 3 στοιχειώδεις κύκλοι θα είναι διαφορετικοί, αφού καθένας τους περιέχει ακριβώς μία χορδή ως προς το δέντρο επικάλυψης Τ .
2β Βρείτε άν ισχύει πάντα ότι: Άν οι βαθμοί των κορυφών του Γ είναι όλοι μεγαλύτεροι από 2, κάθε ακμή του Γ θα περιέχεται σε κύκλο.
Στο παρακάτω γράφημα κάθε κορυφή έχει βαθμό 3, και η ακμή { Α , Β } δεν περιέχεται σε κύκλο.
3 Αποδείξτε ότι: Υπάρχει κλειστή διαδρομή του Γ, όπου κάθε ακμή του εμφανίζεται ακριβώς δύο φορές. Χρησιμοποιείστε την επαγωγή για τα συνεκτικά γραφήματα. .
Για την επαγωγή για τα συνεκτικά γραφήματα, βλέπε ΕΓΘΑ 2.4 . Εργαζόμαστε όπως για την Πρόταση 2.4.3: αποδεικνύουμε με επαγωγή ότι η ζητούμενη ιδιότητα ισχύει για όλα τα γραφήματα της υπο-κλάσης Σ(n), για κάθε n≥2 .
Aρχική περίπτωση n = 2 . Κάθε γράφημα Γ στην Σ(2) έχει ακριβώς δύο κορυφές, έστω a , b , και μία ακμή {a, b} που τις συνδέει. Στην κλειστή διαδρομή {a, {a, b}, b, {a, b}, a} , η μοναδική ακμή {a, b} του Γ εμφανίζεται ακριβώς δύο φορές.
Eπαγωγικό βήμα Έστω ότι το ζητούμενο ισχύει για n = i 1 2. Θα δείξουμε ότι ισχύει για n = i . Έστω ένα συνεκτικό γράφημα G στην Σ(i) , i>2 .
Από την επαγωγική κατασκευή της Σ(i) έχουμε: G = (VU{a} , EU{{a, b1}, … , {a, bm}}) , όπου G = (V, E) είναι συνεκτικό γράφημα της υπο-κλάσης Σ(i 1) , a V, και οι κορυφές b1 , …, bm (m≥1) είναι στο V. Υποθέτουμε επαγωγικά ότι: υπάρχει κλειστή διαδρομή δ του G , όπου κάθε ακμή του εμφανίζεται ακριβώς δύο φορές.
Κάθε μία από τις κορυφές b1,…, bm του συνεκτικού γραφήματος G είναι άκρο μιάς τουλάχιστον ακμής του επομένως θα εμφανίζεται στη διαδρομή δ . Υποθέτουμε ότι η δ έχει τη μορφή (u, ... , b1 , e1 , … , bm , em , ... , u) , και κατασκευάζουμε μιά κλειστή διαδρομή δ προσθέτοντας κατάλληλες ακμές και κορυφές στη δ :
δ = (u, ... , b1 , {a, b1}, a, {a, b1}, b1 , e1 , … , bm , {a, bm}, a, {a, bm}, bm , em , ... , u) .
Κάθε ακμή του Ε εμφανίζεται ακριβώς δύο φορές στη δ λόγω της επαγωγικής υπόθεσης για την δ . Επίση;, κάθε μία από τις ακμές {a, b1}, … , {a, bm} εμφανίζεται ακριβώς δύο φορές στη δ λόγω της κατασκευής της. Άρα, κάθε ακμή του G εμφανίζεται ακριβώς δύο φορές στη δ .
4 Υποθέτουμε ότι το Γ είναι δέντρο, και ότι ο βαθμός κάθε κορυφής του είναι 1 και 3 . Αποδείξτε ότι: (ο αριθμός των κορυφών βαθμού 1) (ο αριθμός των κορυφών βαθμού 3) = 2 . Χρησιμοποιείστε την επαγωγή για τα δέντρα.
Για την επαγωγή για τα δέντρα, βλέπε ΕΓΘΑ 3.1 .
Εργαζόμαστε όπως για την Πρόταση 3.1.2: αποδεικνύουμε με επαγωγή ότι η ζητούμενη ιδιότητα ισχύει για όλα τα γραφήματα της υπο-κλάσης T(n), για κάθε n≥1 .
Aρχική περίπτωση n = 1 . Επειδή κάθε γράφημα στην Τ(1) έχει μόνο μία κορυφή και καμμία ακμή, δεν υπάρχει Γ στην Τ(1) για το οποίο να ισχύει ότι ο βαθμός κάθε κορυφής είναι 1 και 3 . Επομένως κανένα Γ στην Τ(1) δεν διαψεύδει την ζητούμενη ιδιότητα -- (false implies x) = true για κάθε x -- οπότε ισχύει για όλα τα γραφήματα της T(1).
ΣΗΜΕΙΩΣΗ Εναλλακτικά, μπορούμε να έχουμε ως αρχική περίπτωση n = 2 . Κάθε γράφημα στην Τ(2) έχει ακριβώς δύο κορυφές με μία ακμή που τις συνδέει, και (αριθμός των κορυφών βαθμού 1) = 2 , (αριθμός των κορυφών βαθμού 3) = 0 .
Eπαγωγικό βήμα Έστω ότι το ζητούμενο ισχύει για n = i 1 1. Θα δείξουμε ότι ισχύει για n = i .
Έστω ένα δέντρο G στην Τ(i), i>1, με βαθμούς κορυφών μεταξύ 1 και 3.
Από την επαγωγική κατασκευή της Τ(i) θα έχουμε G = (VU{a}, EU{{a, b}}) , όπου G = (V, E) θα είναι δέντρο της υπο-κλάσης Τ(i 1) , και a V, b є V. Προφανώς, ο βαθμός κάθε κορυφής του G θα είναι 1 και 3 . Υποθέτουμε επαγωγικά ότι:
(ο αριθμός των κορυφών βαθμού 1 του G ) (ο αριθμός των κορυφών βαθμού 3 του G ) = 2 .
Έστω Κ ο βαθμός της b στο G . Διακρίνουμε τις εξής περιπτώσεις:
(α) Κ' = 1 : Στο G η κορυφή b θα έχει βαθμό 2, οι βαθμοί των άλλων κορυφών του G δεν θα αλλάξουν, και θα υπάρχει η νέα κορυφή a με βαθμό 1. Eπομένως,
(ο αριθμός των κορυφών βαθμού 1 του G) = (ο αριθμός των κορυφών βαθμού 1 του G ) ,
(ο αριθμός των κορυφών βαθμού 3 του G) = (ο αριθμός των κορυφών βαθμού 3 του G ) . Χρησιμοποιώντας την επαγωγική υπόθεση, βλέπουμε ότι
(ο αριθμός των κορυφών βαθμού 1 του G) (ο αριθμός των κορυφών βαθμού 3 του G) = 2 .
(β) Κ' = 2 : Στο G η κορυφή b θα έχει βαθμό 3, οι βαθμοί των άλλων κορυφών του G δεν θα αλλάξουν, και θα υπάρχει η νέα κορυφή a με βαθμό 1. Eπομένως,
(ο αριθμός των κορυφών βαθμού 1 του G) = 1+(ο αριθμός των κορυφών βαθμού 1 του G ) , (ο αριθμός των κορυφών βαθμού 3 του G) = 1+(ο αριθμός των κορυφών βαθμού 3 του G ) . Χρησιμοποιώντας την επαγωγική υπόθεση, βλέπουμε ότι
(ο αριθμός των κορυφών βαθμού 1 του G) (ο αριθμός των κορυφών βαθμού 3 του G) = 2 .
(γ) Κ' = 3 : Στο G η κορυφή b θα έχει βαθμό >3. Mε βάση την υπόθεση ότι ο βαθμός κάθε κορυφής του G είναι 1 και 3 , η περίπτωση αυτή αποκλείεται.
- 5 Έστω Δ ένα άκυκλο υπογράφημα του Γ. Αποδείξτε ότι: Υπάρχει υπογράφημα Τ του Γ που είναι δέντρο, και που περιεχει το Δ.
Α Τρόπος Άν το Γ είναι άκυκλο θα είναι δέντρο, και μπορούμε να πάρουμε Τ = Γ . Έστω ότι στο Γ υπάρχει κάποιος κύκλος Κ. Επειδή το Δ είναι άκυκλο, υπάρχει κάποια ακμή του Κ, έστω η e , που δεν είναι ακμή του Δ.
Από την Πρόταση 2.3.1 ΕΓΘΑ 2.3, η ακμή e δεν είναι γέφυρα του Γ. Άρα, το γράφημα Γ1 = Γ e είναι συνεκτικό. Το Δ είναι υπογράφημα του Γ1 , αφού η ακμή που αφαιρέθηκε δεν είναι στο Δ . Εκτελώντας την παραπάνω διαδικασία επαναληπτικά, κατασκευάζουμε γραφήματα Γk , k = 1,...,m , που καθένα τους είναι συνεκτικό και περιέχει το Δ . Επειδή κάθε φορά αφαιρείται κάποια ακμή που ανήκει σε κύκλο, το τελευταίο Γm -- από όπου δεν μπορεί να αφαιρεθεί άλλη ακμή -- θα είναι άκυκλο. Επίσης το Γm περιέχει το Δ , και μπορούμε να πάρουμε Τ = Γm .
Β Τρόπος Άν το Δ είναι συνεκτικό θα είναι δέντρο, και μπορούμε να πάρουμε Τ = Δ . Άν το Δ δεν είναι συνεκτικό, θα έχει σuνεκτικές συνιστώσες Η1 , ... , Ηp , p 2 . Mπορούμε να «συνδέσουμε» την Η1 , μέσω κάποιου μονοπατιού του Γ , με μία – και μόνο μία – από τις υπόλοιπες σuνεκτικές συνιστώσες του Δ : χρησιμοποιώντας την Πρόταση 2.2.2 ΕΓΘΑ 2.2, βρίσκουμε ένα μονοπάτι μ του Γ με αρχή στο Η1 , τέλος στο Η2 ... Ηp , και χωρίς καμμία άλλη κορυφή στο Δ . Το γράφημα Δ1 = Δ μ θα έχει ακριβώς p 1 συνεκτικές συνιστώσες (η Η1 συνδέθηκε με ακριβώς μία από τις Η2 , ... , Ηp ). Επίσης το Δ1 θα είναι άκυκλο : οι κορυφές και ακμές του μ που δεν είναι στο Δ δεν μπορούν να αποτελέσουν μέρος κάποιου κύκλου, επειδή τα άκρα του μ βρίσκονται σε διαφορετικές συνεκτικές συνιστώσες του Δ , άρα δεν είναι προσβάσιμα μεταξύ τους.
Εκτελώντας την παραπάνω διαδικασία επαναληπτικά κατασκευάζουμε άκυκλα γραφήματα Δk, 1 k p 1 , που καθένα τους περιέχει το Δ . Κάθε φορά o αριθμός των συνεκτικών συνιστωσών μειώνεται κατά μία -- άρα το Δp 1 είναι συνεκτικό, και μπορούμε να πάρουμε Τ = Δp 1 .
- 6 Έστω Η μία δισυνεκτική συνιστώσα του Γ ως προς ακμές, Θ μία δισυνεκτική συνιστώσα του Γ ως προς κορυφές.
α Αποδείξτε ότι: άν το Η περιέχεται στο Θ, θα είναι Η = Θ .
Έστω α μία κορυφή του Η. Aπό την υπόθεση, η α θα είναι κορυφή και του Θ. Διακρίνουμε δύο περιπτώσεις.
(1) Κάθε ακμή με άκρο την α είναι γέφυρα του Γ: Από την Πρόταση 2.3.1 ΕΓΘΑ 2.3 , δεν υπάρχει κύκλος που να περιέχει την α . Άρα, για κάθε κορυφή β διαφορετική από την α δεν ισχύει α Rκ β -- βλέπε ΕΓΘΑ 4.1 -- οπότε η β δεν μπορεί να είναι κορυφή του Θ . Καταλήγουμε ότι το Θ αποτελείται από την κορυφή α (και μόνο), οπότε Η = Θ , αφού το Η περιέχεται στο Θ .
(2) Υπάρχει ακμή e με άκρο την α , που δεν είναι γέφυρα του Γ: Επειδή υπάρχει κύκλος που περιέχει την e , από την Πρόταση 4.2.4. ΕΓΘΑ 4.2 -- κάθε κύκλος είναι και κλειστό ίχνος -- η ακμή e είναι ακμή του Η . Aπό την υπόθεση, η e θα είναι ακμή και του Θ .
Έστω e oποιαδήποτε (τυχαία) ακμή του Θ . Από την Πρόταση 4.1.4 ΕΓΘΑ 4.1 , υπάρχει κάποιος κύκλος που περιέχει τις ακμές e , e . Επειδή κάθε κύκλος είναι και κλειστό ίχνος, από την Πρόταση 4.2.4. ΕΓΘΑ 4.2 , η ακμή e είναι και ακμή του Η -- άρα οι ακμές του Θ περιέχονται και στο Η . Αφού το Θ δεν έχει απομονωμένες κορυφές καταλήγουμε ότι το Θ περιέχεται στο Η . Επομένως Η = Θ .
β Βρείτε άν ισχύει πάντα ότι: άν το Θ περιέχεται στο Η, θα είναι Η = Θ .
Το παρακάτω γράφημα Γ αποτελείται από ένα κλειστό ίχνος, επομένως το Γ είναι δισυνεκτικό ως προς ακμές (βλέπε ΕΓΘΑ 4.2) , και μπορούμε να πάρουμε Η = Γ (το Γ θα είναι η μοναδική δισυνεκτική συνιστώσα του Γ ως προς ακμές). Άρα, οποιαδήποτε δισυνεκτική συνιστώσα Θ του Γ ως προς κορυφές θα περιέχεται στο Η .
Επειδή η κορυφή b είναι κομβικό σημείο του Γ , το Γ δεν είναι δισυνεκτικό ως προς κορυφές -- Πρόταση 4.1.2 ΕΓΘΑ 4.1. Άρα, οποιαδήποτε δισυνεκτική συνιστώσα Θ του Γ ως προς κορυφές θα είναι διαφορετική από το Γ = Η .
Στα ερωτήματα 7 και 8, υποθέτουμε ότι το Γ είναι οποιοδήποτε κατευθυνόμενο ισχυρά συνεκτικό γράφημα.
7 Βρείτε άν ισχύει πάντα ότι: Κάθε ακμή του Γ θα περιέχεται σε κύκλο.
Δείχνουμε ότι η δεδομένη ιδιότητα ισχύει πάντα: Έστω e = (a, b) μία ακμή του Γ , όπου a b (το Γ δεν έχει βρόχους). Από τον ορισμό της ισχυρής συνεκτικότητας – βλέπε ΕΓΘΑ 4.3 – υπάρχουν δύο μονοπάτια: το ένα με αρχή την a και τέλος τη b, και το άλλο με αρχή τη b και τέλος την a . Συγχωνεύοντας το μονοπάτι που έχει αρχή τη b και τέλος την a , με το μονοπάτι (a, e, b) , προκύπτει ένας κατευθυνόμενος κύκλος που περιέχει την ακμή e .
ΣΗΜΕΙΩΣΗ
Άν το Γ αποτελείται από μία κορυφή (και δεν έχει ακμές) η δεδομένη ιδιότητα ισχύει: για να την διαψεύσουμε θα πρέπει να βρούμε κάποια ακμή που να μην περιέχεται σε κύκλο, όμως αυτό είναι αδύνατον αφού δεν υπάρχουν ακμές, και καταλήγουμε ότι η δεδομένη ιδιότητα ισχύει.
8 Βρείτε άν ισχύει πάντα ότι: Υπάρχει μία κλειστή διαδρομή του Γ, που περιέχει όλες τις κορυφές του.
Δείχνουμε ότι η δεδομένη ιδιότητα ισχύει όταν το Γ έχει δύο τουλάχιστον κορυφές : Έστω u1 , u2 , ... , um οι κορυφές του Γ ( m 2 και uj uj+1 , j = 1,...,m 1 ) . Από τον ορισμό της ισχυρής συνεκτικότητας – βλέπε ΕΓΘΑ 4.3 – υπάρχει μονοπάτι με αρχή τη uj και τέλος τη uj+1 , για j = 1,...,m 1 . Επίσης υπάρχει μονοπάτι με αρχή τη um και τέλος τη u1 . Συγχωνεύοντας τα παραπάνω μονοπάτια, προκύπτει μία κλειστή διαδρομή του Γ που περιέχει όλες τις κορυφές του. ΣΗΜΕΙΩΣΗ
Άν το Γ αποτελείται από μία κορυφή (και δεν έχει ακμές) η δεδομένη ιδιότητα δεν ισχύει: για να την επαληθεύσουμε θα πρέπει να βρούμε κάποια διαδρομή του Γ, όμως αυτό είναι αδύνατον αφού το Γ δεν έχει ακμές – βλέπε τον ορισμό της διαδρομής ΕΓΘΑ 2.2. Καταλήγουμε ότι η δεδομένη ιδιότητα δεν ισχύει.