Θεωρία Γραφημάτων και Εφαρμογές — Σεπτέμβριος 2019¶

Μεταγραφή από το αρχείο του eClass «Εξεταση Σεπτ 2019 - Απαντησεις.pdf» (6 σελίδες).

Σημείωση: το αρχείο περιέχει και λύσεις. Δεν μεταγράφονται οι αποδείξεις και οι επεξηγήσεις των λύσεων, οι απαντήσεις «ΣΩΣΤΟ / ΛΑΘΟΣ» και τα σχήματα που δείχνουν μόνο λύσεις (στα A2, B2 και Γ2 η εκφώνηση δεν συνοδεύεται από σχήμα).

Εξεταση Σεπτ 2019 - Απαντησεις.pdf¶

Διακριτά Μαθ/κά ΙΙ - Θεωρία Γραφημάτων & Εφαρμογές

Σεπτέμβριος 2019

ΕΓΘΑ : Σ. Κοσμαδάκης, «Εισαγωγή στα Γραφήματα, Θεωρία-Ασκήσεις»

Το Γ είναι πάντα ένα τυχαίο μη-κατευθυνόμενο γράφημα

Α1 - Β1 - Γ1

Για οποιαδήποτε σύνολα \(X, Y, Z\), ισχύει ότι:

(1) \(X \oplus Y = Y \oplus X\) αντιμεταθετικότητα
(2) \((X \oplus Y) \oplus Z = X \oplus (Y \oplus Z)\) προσεταιριστικότητα
(3) \(X \oplus X = \emptyset\)
(4) \(X \oplus \emptyset = X\)
\(\emptyset \oplus X = X\)

Α1 Αποδείξτε ότι, για οποιαδήποτε σύνολα \(A, B\), ισχύει \(B \oplus (A \oplus A) \oplus B = \emptyset\).

Β1 Αποδείξτε ότι, για οποιαδήποτε σύνολα \(A, B\), ισχύει \(B \oplus (A \oplus B) = A\).

Γ1 Αποδείξτε ότι, για οποιαδήποτε σύνολα \(A, B, C\), ισχύει \((A \oplus B) \oplus (B \oplus C) \oplus (C \oplus A) = \emptyset\).

Α2 Βρείτε ένα \(\Gamma\) δισυνεκτικό ως προς ακμές, που να έχει ακριβώς δύο κομβικά σημεία.

Β2 Βρείτε ένα συνεκτικό \(\Gamma\) που να έχει ακριβώς τρεις δισυνεκτικές συνιστώσες ως προς ακμές.

Γ2 Βρείτε ένα συνεκτικό \(\Gamma\) που να έχει ακριβώς τρεις δισυνεκτικές συνιστώσες ως προς κορυφές, και ακριβώς ένα κομβικό σημείο.

Α3 Έστω η σχέση \(P = \{(u, v) \mid u + v = 1\}\) πάνω στο σύνολο των ακέραιων αριθμών.

α Αποδείξτε ότι η \(P\) είναι συμμετρική.
β Αποδείξτε ότι η \(P\) δεν είναι μεταβατική.

Β3 Έστω η σχέση \(P = \{(u, v) \mid u - v = 1\}\) πάνω στο σύνολο των ακέραιων αριθμών.

α Αποδείξτε ότι η \(P\) δεν είναι συμμετρική.
β Αποδείξτε ότι η \(P\) δεν είναι μεταβατική.

Γ3 Έστω η σχέση \(P = \{(0, 0), (2, 2), (2, 0), (0, 2)\}\) πάνω στο σύνολο των ακέραιων αριθμών.

α Βρείτε άν η \(P\) είναι συμμετρική.
β Βρείτε άν η \(P\) είναι μεταβατική.

Α4 α Στο κατευθυνόμενο γράφημα \(G2\), βρείτε μία κλειστή διαδρομή που να μην είναι κύκλος.

Α4 β Στο κατευθυνόμενο γράφημα \(G1\), βρείτε ένα κλειστό ίχνος που να μην είναι κύκλος.

[Σχήμα: κατευθυνόμενα γραφήματα G1 (κορυφές 0, 1, 2, 3) και G2 (κορυφές 1, 2, 3)]

Α5 Για το κατευθυνόμενο γράφημα \(G2\) του παραπάνω σχήματος:

α Βρείτε άν είναι ισχυρά συνεκτικό.
β Βρείτε τις ισχυρά συνεκτικές συνιστώσες του.

Β4 α Στο κατευθυνόμενο γράφημα \(G2\), βρείτε μία κλειστή διαδρομή που να μην είναι κύκλος.

Β4 β Στο κατευθυνόμενο γράφημα \(G1\), βρείτε ένα κλειστό ίχνος που να μην είναι κύκλος.

[Σχήμα: κατευθυνόμενα γραφήματα G1 και G2 με κορυφές 1, 2, 3, 4]

Β5 Για το κατευθυνόμενο γράφημα \(G2\) του παραπάνω σχήματος:

α Βρείτε άν είναι ισχυρά συνεκτικό.
β Βρείτε τις ισχυρά συνεκτικές συνιστώσες του.

Γ4 α Στο κατευθυνόμενο γράφημα \(G2\), βρείτε μία κλειστή διαδρομή που να μην είναι κύκλος.

Γ4 β Στο κατευθυνόμενο γράφημα \(G1\), βρείτε ένα κλειστό ίχνος που να μην είναι κύκλος.

[Σχήμα: κατευθυνόμενα γραφήματα G1 και G2 με κορυφές 1, 2, 3, 4]

Γ5 Για το κατευθυνόμενο γράφημα \(G2\) του παραπάνω σχήματος:

α Βρείτε άν είναι ισχυρά συνεκτικό.
β Βρείτε τις ισχυρά συνεκτικές συνιστώσες του.

Α6 - Β6 - Γ6 Έστω ότι το \(\Gamma\) έχει \(n\) κορυφές, και το πολύ \(n-3\) ακμές. Αποδείξτε ότι: το \(\Gamma\) θα έχει τουλάχιστον τρείς συνεκτικές συνιστώσες.

Α7 - Β7 - Γ7 Έστω \(\Gamma\) ένα δέντρο με \(n\) κορυφές. Αποδείξτε ότι το άθροισμα των βαθμών των κορυφών του \(\Gamma\) είναι \(2(n-1)\), χρησιμοποιώντας μόνο την επαγωγή για τα δέντρα.

Στα παρακάτω θέματα να αναφέρετε, για κάθε μία επιλογή, αν είναι σωστή ή λάθος. Δεν χρειάζεται να εξηγήσετε τις απαντήσεις σας.

Α8 Για κάθε \(\Gamma\) με ακριβώς \(n\) κορυφές, \(m\) ακμές, Κ κύκλους και Χ χορδές, θα ισχύει ότι:

a Αν \(n > m+1\), το \(\Gamma\) δεν είναι συνεκτικό.
b Αν Κ ≥ 1, θα είναι \(m \ge n\).
c Χ = Κ.
d Αν Κ=2 και το \(\Gamma\) είναι συνεκτικό, θα έχει κομβικό σημείο.

Α9 Για κάθε μη-κατευθυνόμενο γράφημα \(\Gamma\) ισχύει ότι:

a Δύο διαφορετικές δισυνεκτικές συνιστώσες του \(\Gamma\) ως προς κορυφές, δεν μπορούν να έχουν κοινή κορυφή.
b Αν το \(\Gamma\) περιέχει κλειστό ίχνος, θα περιέχει και κύκλο.
c Αν το \(\Gamma\) είναι δισυνεκτικό ως προς κορυφές, κάποιος κύκλος του θα περιέχει όλες τις κορυφές του.
d Αν το \(\Gamma\) είναι δισυνεκτικό ως προς ακμές, κάθε ακμή του θα περιέχεται σε κάποιο κύκλο.

Β8 Για κάθε \(\Gamma\) με ακριβώς \(n\) κορυφές, \(m\) ακμές, Κ κύκλους και Χ χορδές, θα ισχύει ότι:

a Αν το \(\Gamma\) δεν είναι συνεκτικό, θα είναι \(n > m+1\).
b Αν \(n \ge m\), θα είναι Χ ≤ 1.
c Αν Κ=0, θα είναι \(m < n\).
d Αν Κ ≥ 3, θα είναι Χ ≥ 3.

Β9 Για κάθε μη-κατευθυνόμενο γράφημα \(\Gamma\) ισχύει ότι:

a Δύο διαφορετικές δισυνεκτικές συνιστώσες του \(\Gamma\) ως προς ακμές, δεν μπορούν να έχουν κοινή κορυφή.
b Αν υπάρχει κλειστό ίχνος του \(\Gamma\) που περιέχει δύο κορυφές \(a, b\), θα υπάρχει και κύκλος του \(\Gamma\) που περιέχει τις \(a, b\).
c Αν το \(\Gamma\) είναι συνεκτικό, κάποια διαδρομή του \(\Gamma\) θα περιέχει όλες τις κορυφές του \(\Gamma\).
d Αν το \(\Gamma\) δεν είναι δισυνεκτικό ως προς ακμές, δεν θα είναι δισυνεκτικό ως προς κορυφές.

Γ8 Για κάθε \(\Gamma\) με ακριβώς \(n\) κορυφές, \(m\) ακμές, Κ κύκλους και Χ χορδές, θα ισχύει ότι:

a Αν \(n \le m+1\) και Κ=0, το \(\Gamma\) θα είναι συνεκτικό.
b Αν Κ=0, το \(\Gamma\) θα έχει κομβικό σημείο.
c Αν Κ=2 και το \(\Gamma\) είναι συνεκτικό, θα έχει γέφυρα.
d Χ ≤ 1, αν και μόνο αν Κ ≤ 1.

Γ9 Για κάθε μη-κατευθυνόμενο γράφημα \(\Gamma\) ισχύει ότι:

a Δύο διαφορετικές δισυνεκτικές συνιστώσες του \(\Gamma\) ως προς κορυφές, δεν μπορούν να έχουν κοινή ακμή.
b Αν υπάρχει κλειστό ίχνος του \(\Gamma\) που περιέχει μία ακμή \(\{a, b\}\), θα υπάρχει και κύκλος του \(\Gamma\) που περιέχει την \(\{a, b\}\).
c Αν το \(\Gamma\) είναι συνεκτικό, κάποιο μονοπάτι του \(\Gamma\) θα περιέχει όλες τις κορυφές του \(\Gamma\).
d Αν το \(\Gamma\) δεν είναι δισυνεκτικό ως προς κορυφές, θα υπάρχει κορυφή που δεν περιέχεται σε κύκλο.

Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις → 2019-09.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας): Screenshot_2025-01-22_204135.png

Λύσεις (🟢 official)

Κατάσταση: 🟢 official Πηγή: eClass μαθήματος, αρχείο «Θέματα Εξετάσεων και Απαντήσεις» (Εξεταση Σεπτ 2019 - Απαντησεις.pdf)

Λύσεις — Θεωρία Γραφημάτων και Εφαρμογές — Σεπτέμβριος 2019¶

Οι λύσεις μεταφέρονται από το αρχείο του eClass όπως είναι, χωρίς αλλαγές. Το Screenshot_2025-01-22_204135.png είναι διπλότυπο της σελίδας 3 του ίδιου αρχείου με επισημάνσεις και δεν μεταφέρεται ξανά εδώ.

Εξεταση Σεπτ 2019 - Απαντησεις.pdf¶

Διακριτά Μαθ/κά ΙΙ - Θεωρία Γραφημάτων & Εφαρμογές

Σεπτέμβριος 2019

ΕΓΘΑ : Σ. Κοσμαδάκης, «Εισαγωγή στα Γραφήματα, Θεωρία-Ασκήσεις»

Το Γ είναι πάντα ένα τυχαίο μη-κατευθυνόμενο γράφημα

A1 - B1 - Γ1

Για οποιαδήποτε σύνολα Χ , Υ , Ζ , ισχύει ότι:

(1) XY = YX αντιμεταθετικότητα Απόδειξη : XY = (XY)(ΥΧ) = (ΥΧ)(XY) = YX

(2) (XY) = XYZ) προσεταιριστικότητα

Απόδειξη : χρησιμοποιώντας την Άσκηση 9 ΕΓΘΑ 3.4 βλέπουμε ότι το σύνολο (XY)αποτελείται από τα στοιχεία που, είτε ανήκουν σε ένα μόνο από τα Χ , Υ , Ζ , ή ανήκουν και στα τρία -- και το ίδιο ισχύει για το σύνολο XYZ) .

(3) XΧ =  Απόδειξη : XΧ = (XΧ)(ΧΧ) =  =  (4) X = Χ Απόδειξη : X = (X)(Χ) = Χ = Χ Χ = Χ Απόδειξη : Χ = X=Χ

Α1 Αποδείξτε ότι, για οποιαδήποτε σύνολα Α , Β , ισχύει Β  (Α  A)  Β =  .

Β(ΑA)Β = ΒΒ (επειδή ΑA = από 3) = ΒΒ (επειδή Β =Βαπό 4) =  (από 3).

Β1 Αποδείξτε ότι, για οποιαδήποτε σύνολα Α , Β , ισχύει Β  (Α  Β)  = Α . Β(ΑΒ) = Β(ΒΑ) (επειδή ΑΒ = ΒΑ , από 1) = (ΒΒ)Α (από 2) = Α (επειδή ΒΒ =  , από 3) = Α (από 4)

Γ1 Αποδείξτε ότι, για οποιαδήποτε σύνολα Α , Β , C , ισχύει (Α  Β)  (B  C)  (C  A) =  .

(ΑΒ)(BC)(CA) = ΑΒB)CC)A (αλλαγή των παρενθέσεων με χρήση της 2) = ΑA (επειδή Β B = CC = από 3) = (ΑA) (χρησιμοποιώντας την 2) = ΑA (από 4) =  (από 3)

-----------------------------------------------------------------------------------------------------------------------------------------------------------

Α2 Βρείτε ένα Γ δισυνεκτικό ως προς ακμές, που να έχει ακριβώς δύο κομβικά σημεία.¶

Το παρακάτω γράφημα Γ αποτελείται από τρείς κύκλους. Κάθε ακμή του περιέχεται σε έναν από τους κύκλους, οπότε στο Γ δεν υπάρχει γέφυρα – ΕΓΘΑ 2.3.1 – και από ΕΓΘΑ 4.2.2 το Γ είναι δισυνεκτικό ως προς ακμές.

Οι κορυφές b, c είναι κομβικά σημεία του Γ : για κάθε μία υπάρχουν δύο από τις προσκείμενες ακμές της που δεν περιέχονται στον ίδιο κύκλο του Γ – ΕΓΘΑ 2.3.2. Κάθε άλλη κορυφή έχει ακριβώς δύο προσκείμενες ακμές που περιέχονται στον ίδιο κύκλο, επομένως οι b, c είναι τα μοναδικά κομβικά σημεία του Γ.

Β2 Βρείτε ένα συνεκτικό Γ που να έχει ακριβώς τρείς δισυνεκτικές συνιστώσες ως προς ακμές. Από ΕΓΘΑ 4.4 Άσκηση 22 γνωρίζουμε ότι: οι συνεκτικές συνιστώσες του γραφήματος που προκύπτει αφαιρώντας τις γέφυρες του Γ, είναι οι δισυνεκτικές συνιστώσες ως προς ακμές του Γ. Στο παρακάτω γράφημα Γ οι μοναδικές γέφυρες

είναι οι ακμές {b, c} και {d. e} : κάθε άλλη ακμή περιέχεται σε κάποιο κύκλο του Γ – ΕΓΘΑ 2.3.1. Αφαιρώντας τις γέφυρες προκύπτουν ακριβώς τρείς συνεκτικές συνιστώσες: οι δύο κύκλοι του Γ και η κορυφή e.

Γ2 Βρείτε ένα συνεκτικό Γ που να έχει ακριβώς τρείς δισυνεκτικές συνιστώσες ως προς κορυφές, και ακριβώς ένα κομβικό σημείο.

Στο παρακάτω γράφημα Γ η κορυφή a είναι το μοναδικό κομβικό σημείο, επειδή έχει δύο προσκείμενες ακμές που δεν περιέχονται στον ίδιο κύκλο – ΕΓΘΑ 2.3.2.

Τα παρακάτω υπογραφήματα του Γ είναι δισυνεκτικές συνιστώσες ως προς κορυφές – ΕΓΘΑ 4.1 :

1 Η κορυφή b . Είναι υπο-γράφημα δισυνεκτικό ως προς κορυφές, επειδή δεν έχει δύο διαφορετικές κορυφές για τις οποίες να μην αληθεύει η σχέση Rκ .

Πρoσθέτοντας στην b οποιεσδήποτε κορυφές και ακμές του Γ παίρνουμε υπο-γράφημα που δεν μπορεί να είναι δισυνεκτικό: η κορυφή b έχει βαθμό 1 στο Γ, άρα δεν υπάρχει κύκλος που να περιέχει την b και κάποια άλλη κορυφή.

2 Η κορυφή c . Αντίστοιχα με την b.

3 Ο κύκλος του Γ . Είναι υπο-γράφημα δισυνεκτικό ως προς κορυφές, επειδή για οποιεσδήποτε δύο διαφορετικές κορυφές του αληθεύει η σχέση Rκ .

Πρoσθέτοντας στον κύκλο οποιεσδήποτε κορυφές και ακμές του Γ παίρνουμε υπο-γράφημα που δεν μπορεί να είναι δισυνεκτικό, επειδή η κορυφή a θα είναι κομβικό σημείο – βλέπε ΕΓΘΑ 4.1 Πρόταση 4.1.2 (1) .

-----------------------------------------------------------------------------------------------------------------------------------------------------------

Α3 Έστω η σχέση P = { (u, v) | u+v = 1 } πάνω στο σύνολο των ακέραιων αριθμών.

α Αποδείξτε ότι η P είναι συμμετρική.

Όταν ισχύει x P y για δύο ακέραιους αριθμούς x , y , θα έχουμε x+y = 1 . Άρα y+x = 1 (η πρόσθεση ακέραιων αριθμών είναι αντιμεταθετική), οπότε ισχύει και y P x . Eπομένως η σχέση P πάνω στο σύνολο των ακέραιων αριθμών είναι συμμετρική αφού, όταν ισχύει x Ρ y , θα ισχύει και y Ρ x – ΕΓΘΑ 1.2.

β Αποδείξτε ότι η P δεν είναι μεταβατική.

Μια σχέση Ρ πάνω σε ένα σύνολο Α ονομάζεται μεταβατική αν:

όταν ισχύει x Ρ y και y Ρ z , ισχύει και x Ρ z – ΕΓΘΑ 1.2.

Έστω η τριάδα ακέραιων x=1 , y=0 , z=1 : Bλέπουμε ότι x+y = 1 και y+z = 1 , άρα ισχύει x Ρ y και y Ρ z . Όμως x+z = 2  1 , άρα δεν ισχύει x Ρ z : η τριάδα x=1 , y=0 , z=1 είναι αντιπαράδειγμα για την μεταβατικότητα της Ρ , πάνω στο σύνολο των θετικών ακέραιων αριθμών.

Β3 Έστω η σχέση P = { (u, v) | u  v = 1 } πάνω στο σύνολο των ακέραιων αριθμών.

α Αποδείξτε ότι η P δεν είναι συμμετρική.

Μια σχέση Ρ πάνω σε ένα σύνολο Α ονομάζεται συμμετρική αν:

όταν ισχύει x Ρ y , ισχύει και y Ρ x – ΕΓΘΑ 1.2.

Έστω το ζεύγος ακέραιων x=1 , y=0 : Bλέπουμε ότι xy = 1 , άρα ισχύει x Ρ y . Όμως yx = 1  1 , άρα δεν ισχύει y Ρ x : το ζεύγος x=1 , y=0 είναι αντιπαράδειγμα για τη συμμετρία της Ρ , πάνω στο σύνολο των θετικών ακέραιων αριθμών.

β Αποδείξτε ότι η P δεν είναι μεταβατική.

Μια σχέση Ρ πάνω σε ένα σύνολο Α ονομάζεται μεταβατική αν:

όταν ισχύει x Ρ y και y Ρ z , ισχύει και x Ρ z – ΕΓΘΑ 1.2.

Έστω η τριάδα ακέραιων x=1 , y=0 , z=1 : Bλέπουμε ότι xy = 1 και yz = 1 , άρα ισχύει x Ρ y και y Ρ z . Όμως xz = 2  1 , άρα δεν ισχύει x Ρ z : η τριάδα x=1 , y=0 , z=1 είναι αντιπαράδειγμα για την μεταβατικότητα της Ρ , πάνω στο σύνολο των θετικών ακέραιων αριθμών.

Γ3 Έστω η σχέση P = { (0, 0) , (2, 2) , (2, 0) , (0, 2) } πάνω στο σύνολο των ακέραιων αριθμών.

α Βρείτε άν η P είναι συμμετρική.

Όταν ισχύει x P y για ακέραιους αριθμούς x , y θα έχουμε x{0 , 2} και y{0 , 2} , αφού οι μόνοι ακέραιοι που εμφανίζονται στα ζεύγη που αποτελούν την σχέση Ρ , είναι το 0 και το 2 .

Επειδή η Ρ περιέχει κάθε ζεύγος με στοιχεία το 0 είτε το 2 , θα ισχύει και y P x .

Eπομένως η σχέση P πάνω στο σύνολο των ακέραιων αριθμών είναι συμμετρική αφού, όταν ισχύει x Ρ y , θα ισχύει και y Ρ x – ΕΓΘΑ 1.2.

β Βρείτε άν η P είναι μεταβατική .

Όταν ισχύει x P y και y Ρ z για ακέραιους αριθμούς x , y , z , θα έχουμε {x , y , z}  {0 , 2} , αφού οι μόνοι ακέραιοι που εμφανίζονται στα ζεύγη που αποτελούν την σχέση Ρ , είναι το 0 και το 2 .

Επειδή η Ρ περιέχει κάθε ζεύγος με στοιχεία το 0 είτε το 2 , θα ισχύει και x P z .

Eπομένως η σχέση P πάνω στο σύνολο των ακέραιων αριθμών είναι μεταβατική αφού, όταν ισχύει x Ρ y και y Ρ z , θα ισχύει και x P z – ΕΓΘΑ 1.2.

-----------------------------------------------------------------------------------------------------------------------------------------------------------

Α4 α Στο κατευθυνόμενο γράφημα G2 , βρείτε μία κλειστή διαδρομή που να μην είναι κύκλος.

Η διαδρομή (1 , (1,2) , 2 , (2,1) , 1 , (1,2) , 2 , (2,1) , 1) είναι κλειστή, αφου τα άκρα της ταυτίζονται – βλέπε ΕΓΘΑ 2.2. Η διαδρομή δεν είναι κύκλος, αφού επαναλαμβάνεται η κορυφή 2 .

β Στο κατευθυνόμενο γράφημα G1 , βρείτε ένα κλειστό ίχνος που να μην είναι κύκλος.

Η διαδρομή (1 , (1,2) , 2 , (2,3) , 3 , (3,2) , 2 , (2,1) , 1) είναι κλειστή, αφου τα άκρα της ταυτίζονται, και είναι ίχνος, αφού καμμία ακμή δεν εμφανίζεται δύο φορές – βλέπε ΕΓΘΑ 2.2. Η διαδρομή δεν είναι κύκλος, αφού επαναλαμβάνεται η κορυφή 2 .

G1 :

G2 :

Α5 Για το κατευθυνόμενο γράφημα G2 του παραπάνω σχήματος:
α Βρείτε άν είναι ισχυρά συνεκτικό.

Βλέπουμε ότι στο G2 δεν υπάρχει μονοπάτι με αρχή την κορυφή 3 (αφού καμμία ακμή δεν αρχίζει από αυτή την κορυφή). Επομένως δεν ισχύει 1 Rδδ 3 , και το G2 δεν είναι ισχυρά συνεκτικό – βλέπε ΕΓΘΑ 4.3.

β Βρείτε τις ισχυρά συνεκτικές συνιστώσες του.

Για κάθε κορυφή α του G2 , βρίσκουμε την ισχυρά συνεκτική συνιστώσα Η(α) που περιέχει την α , χρησιμοποιώντας την ΕΓΘΑ Πρόταση 4.3.4:

Παρατηρούμε ότι στο G2 υπάρχει μία κλειστή διαδρομή που περιέχει τις κορυφές 1 , 2 , και δεν υπάρχει κλειστή διαδρομή που να περιέχει την κορυφή 3 και κάποια άλλη κορυφή. Άρα έχουμε δύο ισχυρά συνεκτικές συνιστώσες, την Η(1) = Η(2) = ( {1, 2} , { (1,2) , (2,1) } ) , και την Η(3) = ( {3} ,  ) .

Β4 α Στο κατευθυνόμενο γράφημα G2 , βρείτε μία κλειστή διαδρομή που να μην είναι κύκλος. Η διαδρομή (3 , (3,2) , 2 , (2,3) , 3 , (3,2) , 2 , (2,3) , 3) είναι κλειστή, αφου τα άκρα της ταυτίζονται – βλέπε ΕΓΘΑ 2.2. Η διαδρομή δεν είναι κύκλος, αφού επαναλαμβάνεται η κορυφή 2 .
β Στο κατευθυνόμενο γράφημα G1 , βρείτε ένα κλειστό ίχνος που να μην είναι κύκλος. Η διαδρομή (1 , (1,4) , 4 , (4,2) , 2 , (2,3) , 3 , (3,2) , 2 , (2,1) , 1) είναι κλειστή, αφου τα άκρα της ταυτίζονται, και είναι ίχνος, αφού καμμία ακμή δεν εμφανίζεται δύο φορές – βλέπε ΕΓΘΑ 2.2. Η διαδρομή δεν είναι κύκλος, αφού επαναλαμβάνεται η κορυφή 2 .

G1 :

G2 :

Β5 Για το κατευθυνόμενο γράφημα G2 του παραπάνω σχήματος:
α Βρείτε άν είναι ισχυρά συνεκτικό.

Βλέπουμε ότι στο G2 δεν υπάρχει μονοπάτι με αρχή την κορυφή 4 (αφού καμμία ακμή δεν αρχίζει από αυτή την κορυφή). Επομένως δεν ισχύει 1 Rδδ 4 , και το G2 δεν είναι ισχυρά συνεκτικό – βλέπε ΕΓΘΑ 4.3.

β Βρείτε τις ισχυρά συνεκτικές συνιστώσες του.

Για κάθε κορυφή α του G2 , βρίσκουμε την ισχυρά συνεκτική συνιστώσα Η(α) που περιέχει την α , χρησιμοποιώντας την ΕΓΘΑ Πρόταση 4.3.4:

Παρατηρούμε ότι στο G2 υπάρχει μία κλειστή διαδρομή που περιέχει τις κορυφές 3 , 2 , και δεν υπάρχει κλειστή διαδρομή που να περιέχει την κορυφή 4 και κάποια άλλη κορυφή, ούτε υπάρχει κλειστή διαδρομή που να περιέχει την κορυφή 1 και κάποια άλλη κορυφή. Άρα έχουμε τρείς ισχυρά συνεκτικές συνιστώσες, την Η(3) = Η(2) = ( {3, 2} , { (3,2) , (2,3) } ) , την Η(4) = ( {4} ,  ) , και την Η(1) = ( {1} ,  ) .

Γ4 α Στο κατευθυνόμενο γράφημα G2 , βρείτε μία κλειστή διαδρομή που να μην είναι κύκλος. Η διαδρομή (3 , (3,2) , 2 , (2,4) , 4 , (4,3) , 3 , (3,2) , 2 , (2,4) , 4 , (4,3) , 3) είναι κλειστή, αφου τα άκρα της ταυτίζοναι – βλέπε ΕΓΘΑ 2.2. Η διαδρομή δεν είναι κύκλος, αφού επαναλαμβάνεται η κορυφή 2 .
β Στο κατευθυνόμενο γράφημα G1 , βρείτε ένα κλειστό ίχνος που να μην είναι κύκλος.

Η διαδρομή (1 , (1,4) , 4 , (4,3) , 3 , (3,2) , 2 , (2,4) , 4 , (4,1) , 1) είναι κλειστή, αφου τα άκρα της ταυτίζονται, και είναι ίχνος, αφού καμμία ακμή δεν εμφανίζεται δύο φορές – βλέπε ΕΓΘΑ 2.2. Η διαδρομή δεν είναι κύκλος, αφού επαναλαμβάνεται η κορυφή 4 .

G1 : G2 :

Γ5 Για το κατευθυνόμενο γράφημα G2 του παραπάνω σχήματος:
α Βρείτε άν είναι ισχυρά συνεκτικό.

Βλέπουμε ότι στο G2 δεν υπάρχει μονοπάτι με τέλος την κορυφή 1 (αφού καμμία ακμή δεν καταλήγει σε αυτή την κορυφή). Επομένως δεν ισχύει 1 Rδδ 4 , και το G2 δεν είναι ισχυρά συνεκτικό – βλέπε ΕΓΘΑ 4.3.

β Βρείτε τις ισχυρά συνεκτικές συνιστώσες του.

Για κάθε κορυφή α του G2 , βρίσκουμε την ισχυρά συνεκτική συνιστώσα Η(α) που περιέχει την α , χρησιμοποιώντας την ΕΓΘΑ Πρόταση 4.3.4:

Παρατηρούμε ότι στο G2 υπάρχει μία κλειστή διαδρομή που περιέχει τις κορυφές 4 , 3 , 2 , και δεν υπάρχει κλειστή διαδρομή που να περιέχει την κορυφή 1 και κάποια άλλη κορυφή. Άρα έχουμε δύο ισχυρά συνεκτικές συνιστώσες, την Η(4) = Η(3) = Η(2) = ( {4, 3, 2} , { (4,3) , (3,2) , (2,4) } ) , και την Η(1) = ( {1} ,  ) .

Α6 - B6 - Γ6 Έστω ότι το Γ έχει n κορυφές, και το πολύ n3 ακμές. Αποδείξτε ότι: το Γ θα έχει τουλάχιστον τρείς συνεκτικές συνιστώσες.

Έστω Gj = (Vj , Ej) , j = 1,...k , οι συνεκτικές συνιστώσες του γραφήματος Γ = (V, E).

Κάθε Gj είναι συνεκτικό, οπότε |Ej|  |Vj|1 , j=1,...k (1) (βλέπε ΕΓΘΑ Πρόταση 2.4.3 (ii)). Τα σύνολα Vj διαμερίζουν τις κορυφές του G – ΕΓΘΑ 2.3 – οπότε n =  j=1,...k |Vj| (2) Τα σύνολα Ej διαμερίζουν τις κορυφές του G – ΕΓΘΑ 2.3 και Ασκήσεις 2.5, 2 – οπότε m =  j=1,...k |Ej| (3) Aντικαθιστώντας στην (3) το |Ej| βάσει της (1), και χρησιμοποιώντας την (2), βρίσκουμε m   j=1,...k ( |Vj|1 ) = (  j=1,...k |Vj| )  k = nk , άρα m  nk (4)

Εφόσον n3  m , βρίσκουμε από την (4) ότι n3  nk , επομένως k  3 .

Α7 - B7 - Γ7 Έστω Γ ένα δέντρο με n κορυφές. Αποδείξτε ότι το άθροισμα των βαθμών των κορυφών του Γ είναι 2(n1), χρησιμοποιώντας μόνο την επαγωγή για τα δέντρα .

Για την επαγωγή για τα δέντρα, βλέπε ΕΓΘΑ 3.1 .

Εργαζόμαστε όπως για την Πρόταση 3.1.2 : αποδεικνύουμε με μαθηματική επαγωγή ότι, για κάθε n≥1 , η ζητούμενη πρόταση ισχύει για όλα τα γραφήματα της υπο-κλάσης T(n) .

Γνωρίζουμε ότι κάθε γράφημα της υπο-κλάσης T(n) έχει ακριβώς n κορυφές -- οπότε πρέπει να δείξουμε ότι, για κάθε γράφημα της υπο-κλάσης T(n) , το άθροισμα των βαθμών των κορυφών είναι 2(n1) . Aρχική περίπτωση n = 1 .

Κάθε γράφημα στην Τ(1) έχει μόνο μία κορυφή και καμμία ακμή, οπότε το άθροισμα των βαθμών των κορυφών του είναι 0 . Αφού για n=1 παίρνουμε 2(n1) = 0 , η πρόταση ισχύει για όλα τα γραφήματα της υπο-κλάσης T(1) .

Eπαγωγικό βήμα Έστω ότι το η ζητούμενη πρόταση ισχύει για n = i1  1. Θα δείξουμε ότι ισχύει για n = i .

Έστω ένα δέντρο G στην υπο-κλάση Τ(i) , i>1 . Από την επαγωγική κατασκευή της Τ(i) έχουμε G = ( V U {a} , E U { {a, b} } ) , όπου G= (V, E) είναι δέντρο της υπο-κλάσης Τ(i1) , και a  V, b є V . Υποθέτουμε επαγωγικά, ότι το άθροισμα των βαθμών των κορυφών του G είναι 2( (i1)1 ) = 2(i2) .

Η νέα ακμή {a, b} του G θα προσθέσει 1 στον βαθμό της κορυφής b , και επίσης η νέα κορυφή a του G θα έχει βαθμό 1 . Άρα, το άθροισμα των βαθμών των κορυφών του G θα είναι 2(i2)+1+1 = 2(i1) .

Στα παρακάτω θέματα να αναφέρετε, για κάθε μία επιλογή, άν είναι σωστή ή λάθος . Δεν χρειάζεται να εξηγήσετε τις απαντήσεις σας¶

Α8 Για κάθε Γ με ακριβώς n κορυφές, m ακμές, Κ κύκλους και Χ χορδές, θα ισχύει ότι:

a Άν n > m+1 , το Γ δεν είναι συνεκτικό. ΣΩΣΤΟ b Άν Κ  1 , θα είναι m  n . ΛΑΘΟΣ c X = K . ΛΑΘΟΣ d Άν Κ=2 και το Γ είναι συνεκτικό, θα έχει κομβικό σημείο. ΣΩΣΤΟ

Α9 Για κάθε μη-κατευθυνόμενο γράφημα Γ ισχύει ότι: a Δύο διαφορετικές δισυνεκτικές συνιστώσες του Γ ως προς κορυφές, δεν μπορούν να έχουν κοινή κορυφή. ΛΑΘΟΣ b Άν το Γ περιέχει κλειστό ίχνος, θα περιέχει και κύκλο. ΣΩΣΤΟ c Άν το Γ είναι δισυνεκτικό ως προς κορυφές, κάποιος κύκλος του θα περιέχει όλες τις κορυφές του. ΛΑΘΟΣ d Άν το Γ είναι δισυνεκτικό ως προς ακμές, κάθε ακμή του θα περιέχεται σε κάποιο κύκλο. ΣΩΣΤΟ

Β8Για κάθε Γ με_ακριβώς_n κορυφές, m ακμές, Κ κύκλους και Χ χορδές, θα ισχύει ότι:
aΆν το Γ δεν είναι συνεκτικό, θα είναι n > m+1 .	ΛΑΘΟΣ
bΆν nm , θα είναι X1 .	ΛΑΘΟΣ
cΆν Κ=0 , θα είναι m < n .	ΣΩΣΤΟ
dΆν Κ3 , θα είναι Χ 3 .	ΛΑΘΟΣ
Β9Για κάθε μη-κατευθυνόμενο γράφημα Γ ισχύει ότι:
aΔύο διαφορετικές δισυνεκτικές συνιστώσες του Γ ως προς ακμές, δεν μπορούν να έχουν κοινή κορυφή.	ΣΩΣΤΟ
bΆν υπάρχει κλειστό ίχνος του Γ που περιέχει δύο κορυφές a , b, θα υπάρχει και κύκλος του Γ που περιέχει τις a , b.	ΛΑΘΟΣ
cΆν το Γ είναι συνεκτικό, κάποια διαδρομή του Γ θα περιέχει όλες τις κορυφές του Γ .	ΣΩΣΤΟ
dΆν το Γ δεν είναι δισυνεκτικό ως προς ακμές,
δεν θα είναι δισυνεκτικό ως προς κορυφές.	ΣΩΣΤΟ
Γ8Για κάθε Γ με_ακριβώς_n κορυφές, m ακμές, Κ κύκλους και Χ χορδές, θα ισχύει ότι:
aΆν nm+1 και Κ=0 , το Γ θα είναι συνεκτικό.	ΣΩΣΤΟ
bΆν Κ=0 , το Γ θα έχει κομβικό σημείο.	ΛΑΘΟΣ
cΆν Κ=2 και το Γ είναι συνεκτικό, θα έχει γέφυρα.	ΛΑΘΟΣ
dΧ1 , αν και μόνο αν Κ1 .	ΣΩΣΤΟ
Γ9Για κάθε μη-κατευθυνόμενο γράφημα Γ ισχύει ότι:
aΔύο διαφορετικές δισυνεκτικές συνιστώσες του Γ ως προς κορυφές, δεν μπορούν να έχουν κοινή ακμή.	ΣΩΣΤΟ
bΆν υπάρχει κλειστό ίχνος του Γ που περιέχει μία ακμή {a , b} , θα υπάρχει και κύκλος του Γ που περιέχει την {a , b} .	ΣΩΣΤΟ
cΆν το Γ είναι συνεκτικό, κάποιο μονοπάτι του Γ θα περιέχει όλες τις κορυφές του Γ .	ΛΑΘΟΣ
dΆν το Γ δεν είναι δισυνεκτικό ως προς κορυφές,
θα υπάρχει κορυφή που δεν περιέχεται σε κύκλο.	ΛΑΘΟΣ

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή