Φροντιστήριο #9

Ασκήσεις σε Γράφους

21/5/2020

Άσκηση 9.1:

Στο παρακάτω σχήμα φαίνονται δέκα λατινικοί χαρακτήρες (A, F, K, M, R, S, T, V, X και Z) με

τη μορφή γράφων. Ποιοι από αυτούς είναι ισομορφικοί;

Λύση

Το παραπάνω σύνολο γράφων μπορεί να χωριστεί σε τέσσερα υποσύνολα έτσι ώστε τα μέλη

κάθε υποσυνόλου να είναι ισομορφικά μεταξύ τους.

1. Μ, S, V, Z

2. A, R

3. X, K

4. F, T (το δυσκολότερο ίσως να δει κάποιος, δες παρακάτω σχήμα)

Άσκηση 9.2:

Έστω ο γράφος G που φαίνεται στο παρακάτω σχήμα.

(i) Περιλαμβάνει ο γράφος αυτός μονοπάτι Euler;

(ii) Περιλαμβάνει ο γράφος αυτός κύκλωμα Euler;

Σε κάθε περίπτωση, δικαιολογείστε την απάντησή σας.

Λύση

(α)

(i) Ναι, περιλαμβάνει μονοπάτι Euler γιατί ο γράφος αυτός έχει ακριβώς δύο κόμβους

περιττού βαθμού.

(ii) Όχι, δεν περιλαμβάνει κύκλωμα Euler γιατί ο γράφος αυτός έχει κόμβους περιττού

βαθμού.

Άσκηση 9.3:

Έστω οι δύο γράφοι που φαίνονται στο παρακάτω σχήμα.

Είναι αυτοί οι δύο γράφοι ισομορφικοί; Δικαιολογείστε την απάντησή σας.

Λύση

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

τρόπους. Παρατηρούμε για παράδειγμα ότι ο γράφος στα δεξιά περιλαμβάνει κόμβο με

βαθμό 4, ενώ αυτό δεν ισχύει για τον γράφο στα αριστερά.

Άσκηση 9.4:

Για καθένα από τους γράφους (i), (ii) και (iii) του παρακάτω σχήματος,

(α) περιλαμβάνει ο γράφος κύκλωμα Euler;

(β) περιλαμβάνει ο γράφος κύκλωμα Hamilton;

Στην περίπτωση που η απάντησή σας σε κάποιο ερώτημα και για κάποιο γράφο είναι θετική,

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

(i) (ii) (iii)

Λύση

(α)

(i) Όχι, γιατί υπάρχουν κόμβοι με περιττό βαθμό (ο 2 και ο 5)

(ii) Ναι, γιατί όλοι οι κόμβοι έχουν άρτιο βαθμό. Π.χ. 1,2,3,5,6,9,8,7,5,4,2,5,8,4,1.

(iii) Όχι, γιατί υπάρχουν κόμβοι με περιττό βαθμό (για την ακρίβεια, όλοι έχουν περιττό

βαθμό).

(β)

(i) Ναι, π.χ. 1,4,3,6,7,8,5,2,1

(ii) Οχι.

(iii) Ναι, π.χ. 1,5,3,6,2,4,1

Άσκηση 9.5:

Σχεδιάστε ένα γράφο με έξι κορυφές που να περιλαμβάνει κύκλωμα Hamilton και που να μην

περιλαμβάνει κύκλωμα Euler.

Λύση

Υπάρχουν πολλοί τέτοιοι γράφοι. Ένα παράδειγμα είναι το παρακάτω:

Άσκηση 9.6:

Έχει ο πλήρης διμερής γράφος K3,4

(α) μονοπάτι Euler;

(β) κύκλωμα Euler;

(γ) μονοπάτι Hamilton;

(δ) κύκλωμα Hamilton;

Σε κάθε περίπτωση, δικαιολογείστε την απάντησή σας.

Λύση

(α) Όχι, γιατί ο K3,4 δεν έχει ακριβώς δύο κορυφές περιττού βαθμού

(β) Όχι, γιατί ο K3,4 περιλαμβάνει κορυφές με περιττό βαθμό.

(γ) Ναι, π.χ. το μονοπάτι 4, 1, 5, 2, 6, 3, 7 στο παρακάτω σχήμα

(δ) Όχι…

Άσκηση 9.7:

Ποια από τα παρακάτω δύο σχήματα μπορούν να σχεδιαστούν με μονοκοντυλιά, δηλαδή

χωρίς να σηκώσει κανείς το μολύβι από το χαρτί και χωρίς να περάσει δύο φορές από την

ίδια γραμμή; Εξηγείστε την απάντησή σας.

Λύση

Στο παρακάτω σχήμα φαίνεται η αναπαράσταση των σχημάτων της άσκησης ως γράφοι. Ο

γράφος (a) έχει μονοπάτι Euler αφού έχει ακριβώς δύο κόμβους περιττού βαθμού. Για τον

γράφο (b) δεν ισχύει αυτό. Επομένως ο (a) μπορεί να σχεδιαστεί ως μονοκοντυλιά, ενώ αυτό

δεν ισχύει για τον (b).

Άσκηση 9.8:

Καθένα από τα τρία τα σπίτια Α, Β και Γ του παρακάτω σχήματος πρέπει να συνδεθεί με τις

κεντρικές παροχές ηλεκτρικού ρεύματος, νερού και τηλεφώνου. Σύμφωνα με τις

προδιαγραφές ασφαλείας, καμία σύνδεση δεν πρέπει να διασταυρώνεται με οποιαδήποτε

άλλη. Μπορεί να γίνει αυτό; Αν ναι, δώστε το σχετικό διάγραμμα συνδέσεων. Αν όχι, γιατί;

Λύση

Η απαίτηση της άσκησης για απευθείας σύνδεση των σπιτιών με τις κεντρικές παροχές

ηλεκτρικού ρεύματος, νερού και τηλεφώνου οδηγεί στην απαίτηση κατασκευής ενός

πλήρους διμερούς γράφου (Κ3,3) για τον οποίο γνωρίζουμε ότι δεν είναι επίπεδος. Επομένως,

δεν γίνεται να ικανοποιηθούν οι προδιαγραφές ασφαλείας.

Άσκηση 9.9

Να αποδείξετε ότι δεν μπορεί να υπάρξει απλός γράφος με

a. 6 κορυφές με βαθμό 2, 3, 3, 4, 4, και 5 αντίστοιχα.

b. 5 κορυφές με βαθμό 2, 3, 4, 4, και 5 αντίστοιχα.

c. 4 κορυφές με βαθμό 1, 3, 3, και 3 αντίστοιχα.

d. 7 κορυφές με βαθμό 1, 3, 3, 4, 5, 6 και 6 αντίστοιχα.

Λύση

(a)

� ������ = 2|�| ∈�

Το άθροισμα των βαθμών των κόμβων του γράφου είναι 21, δηλαδή περιττός αριθμός,

και ξέρουμε ότι κάτι τέτοιο δεν είναι δυνατόν (το άθροισμα των βαθμών των κόμβων

ενός γράφου είναι άρτιος αριθμός και μάλιστα ίσος με το διπλάσιο του πλήθους των

ακμών του).

(b) Δεν μπορεί ένας απλός γράφος 5 κορυφών να έχει κόμβο με βαθμό 5 (θα πρέπει να

συνδέεται με τον εαυτό του, πράγμα που δεν γίνεται σε απλούς γράφους)

(c) Τρείς κόμβοι έχουν βαθμό 3, δηλαδή συνδέονται με όλους τους άλλους. Επομένως,

κάτι τέτοιο δεν γίνεται, αφού ο τέταρτος κόμβος έχει βαθμό 1.

(d) Ένας κόμβος έχει βαθμό 1. Έστω ότι τον αφαιρούμε από το γράφο, καθώς και την

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

χειρότερη περίπτωση, ένα κόμβο με βαθμό 6. Κάτι τέτοιο δεν γίνεται (δες περίπτωση (b)).

Άσκηση 9.10

Απαντήστε στα παρακάτω δύο ερωτήματα. Αν η απάντησή σας είναι θετική, δώστε

παράδειγμα. Αν είναι αρνητική, εξηγείστε γιατί.

a. Μπορεί ένας απλός γράφος να είναι ταυτόχρονα πλήρης και κυκλικός;

b. Μπορεί ένας απλός γράφος να είναι ταυτόχρονα διμερής και πλήρης;

Λύση

a. Ο μόνος γράφος που μπορεί να είναι πλήρης και κυκλικός ταυτόχρονα είναι

ένας πλήρης γράφος με 3 κόμβους

π.χ.

Κάθε άλλος πλήρης γράφος με περισσότερους κόμβους αναγκαστικά θα έχει «ενδιάμεσες»

ακμές

Π.χ.

b. Γενικά όχι, ο μόνος απλός πλήρης γράφος που είναι διμερής είναι ο Κ2

Άσκηση 9.11

Αποδείξτε ότι η σχέση ισομορφισμού γράφων είναι σχέση ισοδυναμίας.

Λύση

Για να είναι σχέση ισοδυναμίας πρέπει να έχει την ανακλαστική – συμμετρική και μεταβατική

ιδιότητα

1. Πράγματι κάθε γράφος είναι ισόμορφος με τον εαυτό του (πληρούνται τα

κριτήρια για τους κόμβους και τις ακμές και η συνάρτηση που μετατρέπει

τους κόμβους του ενός σε κόμβους του άλλου είναι η ταυτοτική συνάρτηση).

Άρα έχει την ανακλαστική ιδιότητα

2. Έστω γράφος G ισομορφικός με τον D. Τότε και ο D είναι ισομορφικός με τον

G μια και πληρούνται τα κριτήρια για τους κόμβους και τις ακμές και αν f η

συνάρτηση που μετατρέπει τους κόμβους του G δε κόμβους του D,

αντίστοιχα η f-1, μετατρέπει τους κόμβους του D σε κόμβους του G. Έχει τη

συμμετρική ιδιότητα

3. Έστω γράφος G1 ισομορφικός με τον G2 και G2 ισομορφικός με τον G3. Ο G1

είναι ισομορφικός με τον G3 μια και πληρούνται τα κριτήρια για τους

κόμβους και τις ακμές και αν f: G1⟶ G2 και g: G2⟶ G3 οι συναρτήσεις που

απεικονίζουν τους κόμβους του G1 στον G2 και του G2 στον G3 αντίστοιχα τότε

η g∘f: G1⟶ G3 απεικονίζει τους κόμβους του G1 σε αυτούς του G3. Άρα έχει

και τη μεταβατική ιδιότητα

Άσκηση 9.12

Είναι ισομορφικοί οι δύο παρακάτω απλοί, μη κατευθυνόμενοι γράφοι;

Λύση

Όπως φαίνεται και από το παρακάτω σχήμα είναι ισομορφικοί. Έχουμε ίδιο αριθμό

κορυφών, ίδιο αριθμό ακμών και μπορώ να βρω μια συνάρτηση που να αντιστοιχεί τις

κορυφές/ακμές του πρώτου στις κορυφές/ακμές του 2ου γράφου (ή αλλιώς να μετατρέψω

τον πρώτο στο δεύτερο γράφο)

Άσκηση 9.13

Σε ποιο ειδικό τύπο γράφου κατατάσσεται ένας γράφος για τον οποίο ισχύει ότι κάθε

κύκλωμα Euler που έχει, είναι επίσης και κύκλωμα Hamilton;

Λύση

Στους κυκλικούς γράφους

Άσκηση 9.14

Να βρείτε αν τα παρακάτω ζεύγη γράφων είναι ισομορφικά.

Λύση

1. Ναι. Η συνάρτηση ισομορφισμού είναι

f(u1)=v1, f(u2)=v3, f(u3)=v2, f(u4)=v5, f(u5)=v4

2. Ναι. Η συνάρτηση ισομορφισμού είναι

f(u1)=v2, f(u2)=v4, f(u3)=v3, f(u4)=v1

Άσκηση 9.15

Οι γράφοι που παριστάνουν οι παρακάτω πίνακες γειτνίασης είναι ισομορφικοί;

Λύση

Παρατηρούμε ότι ο πρώτος γράφος έχει 1 κορυφή βαθμού 1 (3η σειρά) ενώ ο 2ος δεν έχει.

Αρα δεν μπορούν να είναι ισομορφικοί

Άσκηση 9.16

Να σχεδιάσετε τους παρακάτω γράφους χωρίς διασταυρώσεις

Λύση

Άσκηση 9.17

Έστω ότι ένας συνεκτικός επίπεδος γράφος έχει 8 κορυφές, καθεμία από τις οποίες έχει

βαθμό 3. Σε πόσες περιοχές χωρίζεται το επίπεδο από μια επίπεδη αναπαράσταση αυτού

του γράφου;

Λύση

Ο γράφος έχει v=8 κορυφές, e=12 ακμές (Από κάθε κορυφή με βαθμό 3 ξεκινάν 3 ακμές

(3*8=24) και διαιρώ δια 2 για να μην μετρήσω 2 φορές κάθε ακμή)

Από τον τύπο του Euler το επίπεδο χωρίζεται σε f=2-v+e=2-8+12=6 περιοχές

Άσκηση 9.18

Προσδιορίστε αν οι παρακάτω γράφοι έχουν κύκλωμα Euler. Αν υπάρχει να το υποδείξετε.

Αν δεν υπάρχει, να προσδιορίσετε αν έχουν μονοπάτι Euler και αν υπάρχει τέτοιο μονοπάτι

να το υποδείξετε.

Λύση

1. Ο γράφος 1 έχει κόμβους περιττού βαθμού άρα δεν μπορεί να έχει κύκλωμα Euler.

Έχει ακριβώς 2 κόμβους περιττού βαθμού (f και c) άρα έχει μονοπάτι Euler

Π.χ. f->a->b->f->e->a->d->e->c->d->b->c

2. Ομοίως ο γράφος 2 έχει 2 κόμβους περιττού βαθμού (b και c) άρα δεν μπορεί να έχει

κύκλωμα Euler, αλλά έχει μονοπάτι Euler π.χ. b->a->i->h->a->d->e->f->d->i->g->d->c->i->b->c

Άσκηση 9.19

Προσδιορίστε αν οι παρακάτω γράφοι έχουν

α. Μονοπάτι Hamilton

β. Κύκλωμα Hamilton

Αν έχουν να τα υποδείξετε

Λύση

α. Δεν έχει κύκλωμα Hamilton. Έχει μονοπάτι Hamilton: a->b->c->f->d->e

b. Έχει κύκλωμα Hamilton (π.χ. a->b->c->d->e->a), άρα και μονοπάτι Hamilton

Άσκηση 9.20

Είναι οι δύο γράφοι του σχήματος ισομορφικοί; Δικαιολογείστε την απάντησή σας.

Λύση

Ναι, οι γράφοι είναι ισομορφικοί. Για να το αποδείξουμε πρέπει να βρούμε μία

αμφιμονοσήμαντη συνάρτηση μεταξύ αντίστοιχων κορυφών. Μια τέτοια είναι η

(u, y, w, z, v, z) (l, p, m, q, n, r)

Άσκηση 9.21

Έστω ο γράφος που φαίνεται στο παρακάτω σχήμα. Είναι επίπεδος; Είναι διμερής;

Λύση

Αν ξανασχεδιάσουμε το γράφο όπως στο σχήμα παρακάτω, διαπιστώνουμε ότι είναι

επίπεδος

Αν διαμερίσουμε το σύνολο κορυφών του σε δύο υποσύνολα {a,c} και {b,e,f} διαπιστώνουμε

ότι είναι και διμερής

Άσκηση 9.22

Έχει ο γράφος του σχήματος κύκλωμα Hamilton; Αν ναι, ποιο; Αν όχι, γιατί;

Λύση

Δεν μπορεί να έχει κύκλωμα Hamilton εφόσον έχει κορυφή βαθμού 1

Άσκηση 9.23

Για ποιες τιμές του n ο γράφος Kn αποτελεί κύκλωμα Euler; Για ποιες τιμές των n, m

ο γράφος Kn,m αποτελεί κύκλωμα Euler; Δικαιολογείστε τις απαντήσεις σας.

Λύση

Για να αποτελεί ένας γράφος κύκλωμα Euler πρέπει όλοι του οι κόμβοι να έχουν άρτιο

βαθμό. Αυτό επιτυγχάνεται για περιττό αριθμό κόμβων n για τον πλήρη γράφο Kn

και για άρτιες τιμές των n, m για τον πλήρη διμερή γράφο Kn,m (κάθε κόμβος έχει

βαθμό n-1 ή m-1 αντίστοιχα και στις 2 περιπτώσεις )

Άσκηση 9.24

Έστω οι τέσσερις γράφοι που φαίνονται στο παρακάτω σχήμα. Βρείτε (αν υπάρχουν)

ζευγάρια ισομορφικών γράφων.

(a) (b) (c) (d)

Λύση

Γνωρίζουμε ότι οι ισομορφικοί γράφοι μοιράζονται όλες τους τις ιδιότητες.

Επομένως:

Γράφος 1 Γράφος 2 Ισομορφισμός

(a) (b) Όχι, ο (a) δεν έχει κύκλωμα με 5 κορυφές όπως ο

(b)

(a) (c) Όχι, ο (a) δεν έχει κύκλωμα με 3 κορυφές όπως ο

(c)

(a) (d) Όχι, ο (a) δεν έχει κύκλωμα με 3 κορυφές όπως ο

(d)

(b) (c) Όχι, ο (c) δεν έχει κύκλωμα με 5 κορυφές όπως ο

(b)

(b) (d) Όχι, ο (d) δεν έχει κύκλωμα με 5 κορυφές όπως ο

(b)

(c) (d) Ναι, είναι ισομορφικοί (εύκολα φαίνονται οι

αντιστοιχίες των κόμβων…)

Επομένως, το μόνο ζεύγος ισομορφικών γράφων είναι οι (c), (d).

Άσκηση 9.25

Μπορεί σε ένα γράφο όλες οι κορυφές να έχουν διαφορετικό βαθμό? Εξηγείστε την

απάντησή σας.

Λύση Έστω ότι ο γράφος έχει n κορυφές. Οι δυνατοί βαθμοί για κάθε κορυφή είναι από 0 ως

n-1 (n διαφορετικές τιμές) Για να έχουν όλες οι κορυφές διαφορετικό βαθμό σημαίνει

ότι υπάρχει μια αμφιμονοσήμαντη αντιστοίχηση των n κορυφών στο {0,1,...n-1}. Στο

γράφο δηλαδή θα υπάρχει κάποια κορυφή με βαθμό 0 αλλά και κάποια με βαθμό n-1.

Αντίφαση, γιατί η πρώτη δεν θα συνδέεται με καμία, ενώ η δεύτερη θα συνδέεται με

όλες τις υπόλοιπες!

Άσκηση 9.26

Είναι οι γράφοι των σχημάτων (i), (ii) και (iii) ισομορφικοί;

Λύση

Ο (i) είναι ο πλήρης διμερής γράφος Κ3,3.

Με το γράφο (ii) έχουν ίδιο αριθμό κορυφών και κάθε κορυφή έχει βαθμό 3.

Αντιστοιχίζω τις κορυφές A,B,Γ,Δ,Ε,Ζ με τις a,c,f,d,e,b αντίστοιχα Οπότε είναι

ισομορφικοί

Ο γράφος (i) έχει ίδιο αριθμό κορυφών με το γράφο (iii) και κάθε κορυφή έχει βαθμό

3.

Αντιστοιχίζω τις κορυφές A,B,Γ,Δ,Ε,Ζ με τις 1,2,3,4,5,6 και διαπιστώνω

ισομορφισμό.

Εφόσον τώρα ο (i) είναι ισομορφικός με τον (ii) και με τον (iii) και ο ισομορφισμός

είναι σχέση ισοδυναμίας όπως αποδεικνύεται στην άσκηση Φ9.11 και ο (ii) είναι

ισομορφικός με τον (iii) .

Άσκηση 9.27

Είναι ο παρακάτω γράφος επίπεδος; Αν ναι, υπολογίστε σε πόσες περιοχές χωρίζει το

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

ακμές που είναι επίπεδος γράφος.

Λύση

(a)

O γράφος θα μπορούσε να σχεδιαστεί και όπως στο παρακάτω σχήμα

Οπότε είναι επίπεδος

Έχει n=6 κορυφές και e=12 ακμές.

Από τον τύπο του Euler χωρίζει το επίπεδο σε f=2+e-v=8 περιοχές

Άσκηση 9.28

Μπορούμε να σχεδιάσουμε τους παρακάτω γράφους με μονοκοντυλιά; Αν όχι γιατί.

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

Λύση

Ο γράφος (i) έχει ακριβώς 2 κορυφές περιττού βαθμού (e και f) άρα έχει μονοπάτι

Euler, και έτσι μπορεί να σχεδιαστεί με μονοκοντυλιά. Μια διαδρομή είναι η

e,f,a,e,b,a,c,b,f,c,d,g,f

Ο γράφος (ii) έχει μόνο κορυφές άρτιου βαθμού άρα έχει κύκλωμα Euler και επίσης

μπορεί να σχεδιαστεί με μονοκοντυλιά. Μια διαδρομή είναι η a,e,b,a,f,b,c,f,g,d,c,a

Άσκηση 9.29

Είναι οι γράφοι G1, G2, G3 ισομορφικοί;

Λύση

O G3 έχει μια κορυφή βαθμού 3 (w) ενώ όλες οι άλλες κορυφές είναι βαθμού 2. Άρα

ο G3 δεν είναι ισομορφικός με κανένα άλλο.

Οι G1 , G2 είναι ισομορφικοί μεταξύ τους . Μια συνάρτηση ισομορφισμού είναι η

f(a)=p

f(c)=q

f(d)=t

f(e)=s

f(b)=r

Άσκηση 9.30

Υποθέστε ότι οι δύο παρακάτω λίστες (α) και (β) δίνουν τους βαθμούς κορυφών δύο

διαφορετικών γράφων. Μπορούν να υπάρξουν τέτοιοι γράφοι; Αν ναι, δώστε

παράδειγμα. Αν όχι, εξηγείστε γιατί.

α. 3, 3, 3, 2, 2, 1, 1

β. 6, 6, 6, 4, 4, 2, 2

Λύση

α. Όχι, το άθροισμα των βαθμών αυτών είναι περιττός αριθμός, ενώ γνωρίζουμε ότι για

κάθε γράφο, το άθροισμα των βαθμών των κορυφών του είναι άρτιος αριθμός.

β. Όχι. Αυτός ο γράφος έχει 7 κορυφές. Τρεις από αυτές συνδέονται με 6 (όλες τις

άλλες). Επομένως, οποιαδήποτε από τις υπόλοιπες κορυφές συνδέεται με τουλάχιστον

3 κορυφές. Άρα, δεν μπορεί να υπάρχουν κορυφές με βαθμό 2.

Άσκηση 9.31

Ο γράφος του σχήματος έχει μονοπάτι Euler; Αν ναι περιγράψτε το

Λύση

Ολες οι κορυφές είναι άρτιου βαθμού άρα υπάρχουν κυκλώματα Euler. Ένα εξ αυτών

είναι και το aeaebedcecdba

Άσκηση 9.32

Υπάρχει γράφος με 102 κορυφές τέτοιος που ακριβώς 49 κορυφές να έχουν βαθμό 5

και οι υπόλοιπες να έχουν βαθμό 6;

Λύση

Γνωρίζουμε ότι ∑ deg ��� ∈� = 2|E|. Στην περίπτωσή μας θα έπρεπε 49*5+53*6=563

να ισούται με 2|Ε| που δεν είναι εφικτό μια και το αριστερο σκέλος είναι περιττός και

το δεξί άρτιος ακέραιος.

Άσκηση 9.33

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

Λύση

Απόδειξη με βάση την αρχή του περιστερώνα. Ας υποθέσουμε πως ο γράφος έχει n

κορυφές. Κάθε μία από αυτές έχει βαθμό από 0 έως n-1. Αν μία κορυφή έχει βαθμό n-

1, συνδέεται με όλες τις υπόλοιπες, άρα δεν μπορεί να υπάρχει κορυφή με βαθμό 0.

Επομένως, έχουμε n κορυφές με βαθμό από 1 έως n-1, δηλαδή n-1 διαφορετικούς

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

(περιστέρια) που αντιστοιχούν στον ίδιο περιστερώνα (βαθμοί κορυφών).

Άσκηση 9.34

Μπορεί ένας απλός γράφος να έχει 5 κορυφές και 12 ακμές; Αν ναι, σχεδιάστε έναν.

Αν όχι, εξηγείστε γιατί.

Λύση

Σε ένα απλό γράφο δεν επιτρέπεται να υπάρχει ζευγάρι κορυφών που να συνδέονται με

παραπάνω από μία ακμή. Το μεγαλύτερο πλήθος ακμών σε ένα απλό γράφο με n

κορυφές είναι n(n-1)/2 (πλήρης γράφος, κάθε κόμβος συνδέεται με όλους τους άλλους).

Επομένως, ένας γράφος με 5 κορυφές μπορεί να έχει το πολύ 10 ακμές.

Άσκηση 9.35

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

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

ισομορφικοί.

Λύση

Άσκηση 9.36

Μπορεί ένας διμερής γράφος να έχει κύκλωμα με περιττό πλήθος ακμών;

Λύση

Όχι, δεν είναι δυνατόν. Έστω Α, Β τα δύο υποσύνολα κορυφών του διμερούς γράφου.

Χωρίς περιορισμό της γενικότητας, ας υποθέσουμε ότι το κύκλωμα ξεκινά και

καταλήγει σε κορυφή του συνόλου Α. Επειδή ο γράφος είναι διμερής, οι ακμές περιττής

τάξης, μας μεταφέρουν από κορυφή του συνόλου Α σε κορυφή του συνόλου Β. Οι

ακμές άρτιας τάξης, μας μεταφέρουν από κορυφή του συνόλου Β σε κορυφή του

συνόλου Α. Επομένως, ένα κύκλωμα, πρέπει να έχει υποχρεωτικά άρτιο πλήθος ακμών.

Άσκηση 9.37

Είναι οι παρακάτω γράφοι Α, Β ισομορφικοί; Αν ναι, δείξτε τον ισομορφισμό. Αν όχι,

εξηγείστε γιατί.

Λύση

Όχι, δεν είναι ισομορφικοί. Και οι δύο γράφοι, έχουν ακριβώς μία κορυφή βαθμού

τέσσερα. Όμως οι γείτονες του κόμβου αυτού στο γράφο Α έχουν βαθμούς {1, 1, 3, 3},

ενώ στον Β έχουν βαθμούς {1, 2, 3, 3}. Μπορούν ωστόσο να διατυπωθούν και άλλα

επιχειρήματα. Για παράδειγμα, ο γράφος A δεν έχει μονοπάτι Hamilton, ενώ ο Β έχει.

Άσκηση 9.38

Για ποιες τιμές του n ο απλός πλήρης γράφος Κn έχει κύκλωμα Euler;

Λύση

Κάθε κορυφή του Κn έχει βαθμό n-1. Για να έχει κύκλωμα Euler πρέπει όλες οι κορυφές

του να έχουν άρτιο βαθμό. n-1 άρτιος αν και μόνο αν n περιττός!

Άσκηση 9.39

Έστω V={1,2,3,4,5}. Πόσοι διαφορετικοί απλοί γράφοι μπορούν να σχηματιστούν αν

έχουμε το V ως σύνολο κορυφών;

Λύση

Έστω Ε το σύνολο όλων των δυνατών ακμών. Οι διαφορετικοί γράφοι αντιστοιχούν σε

όλα τα διαφορετικά υποσύνολα του συνόλου των ακμών. Αυτά έχουν πλήθος2|�|. Το Ε περιέχει όλα τα δυνατά ζεύγη διαφορετικών στοιχείων του V, οπότε |Ε|=��

��=10

Άρα μπορούν να σχηματιστούν 2�� γράφοι.

Άσκηση 9.40

Σχεδιάστε ένα κατευθυνόμενο- γράφο με τον παρακάτω πίνακα γειτνίασης

Λύση

Άσκηση 9.41

α. Σχεδιάστε το συμπλήρωμα των παρακάτω γράφων ως προς τους αντίστοιχους

πλήρεις γράφους

β. Είναι τα συμπληρώματα ισομορφικά μεταξύ τους?

Λύση α.

β. Δεν είναι ισομορφικά: ο 1ος γράφος δεν είναι συνεκτικός ενώ ο 2ος είναι.

Άσκηση 9.42

Οι παρακάτω γράφοι έχουν μονοπάτι Hamilton; Κύκλωμα Hamilton;

Λύση

Ο 1ος δεν έχει μονοπάτι, ούτε κύκλωμα

Ο 2ος έχει μονοπάτι (v1,v2,v3,v4) αλλά όχι κύκλωμα

Ο 3ος έχει μονοπάτι και κύκλωμα (v1,v2,v3,v4,v1)

Άσκηση 9.43

Ποιοι από τους G2,G3,G4 του παρακάτω σχήματος είναι υπογράφοι του G1; Ποιοι είναι

επικαλύπτοντες υπογράφοι;

Λύση

O G2 είναι υπογράφος του G1, αλλά όχι επικαλύπτων (δεν συμπίπτουν τα σύνολα

κορυφών τους)

Ο G3 είναι υπογράφος του G1 αλλά όχι επικαλύπτων (ο G3 δεν έχει την κορυφή e και

Ε3⊆ Ε1)

O G4 δεν είναι υπογράφος του G1 μια και Ε4⊈ Ε1 (η ακμή {c,f} του G4 δεν ανήκει στο

E1)

Άσκηση 9.44

Μπορεί ένας γράφος να έχει 6 κορυφές με βαθμούς 2,2,3,4,5,5? Αν ναι, σχεδιάστε

τον. Αν όχι, αποδείξτε γιατί δεν μπορεί.

Λύση

Όχι, γιατί έχει περιττό πλήθος κόμβων περιττού βαθμού.

Άσκηση 9.45

Ένας γράφος G έχει 6 κορυφές με βαθμούς 2,2,3,4,4,5.

α. Πόσες ακμές έχει;

β. Αν είναι επίπεδος, σε πόσες περιοχές χωρίζει το επίπεδο;

Λύση

α. Ο G έχει 10 ακμές μια και �����������

� = 10.

β. Θα είχε 6-10+f=2 ⇒ f=6 περιοχές στο επίπεδο. Για να είναι πραγματικά

επίπεδος θα πρέπει να βεβαιωθούμε ότι μπορεί να σχεδιαστεί χωρίς

διασταυρώσεις ακμών