5.1 Απλά γραφήματα

Ένα γράφημα (μερικές φορές στην ελληνική βιβλιογραφία γίνεται λόγος και για ένα γράφο) είναι ο βασικότερος, παραστατικότερος και πλέον εύχρηστος γενικός τρόπος στα Μαθηματικά (αλλά και στις Επιστήμες γενικότερα) να παραστήσει κανείς πληροφορία συνδεσμολογίας, να περιγράψει δηλ. μια ομάδα αντικειμένων μερικά από τα οποία συνδέονται μεταξύ τους, και ενδεχομένως και πληροφορίες για τη συνδεσμολογία.

Ορισμός 5.1   (Απλό γράφημα) Ενα απλό γράφημα $G=(V,E)$ αποτελείται από ένα σύνολο κορυφών $V$ και ένα σύνολο ακμών $E$, το οποίο είναι ένα σύνολο από δισύνολα του $V$. Γράφουμε επίσης $V=V(G)$ και $E=E(G)$ για τα σύνολα κορυφών και ακμών του γραφήματος $G$.

Μια ακμή ανάμεσα σε δύο κορυφές $u$ και $v$ αντιπροσωπεύει κάποια έννοια σύνδεσης των δύο κορυφών. Συνηθίζουμε να παριστάνουμε ένα γράφημα αντιστοιχώντας ένα σημείο του επιπέδου σε κάθε κορυφή και τραβώντας μια γραμμή που ενώνει δυο κορυφές αν και μόνο αν αυτές ενώνονται με μια ακμή στο $G$.

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

Σχήμα 5.1: Κάποιες πόλεις στην Κρήτη και οδικές συνδέσεις ως γράφημα

Για παράδειγμα, στο Σχήμα 5.1 δείχνουμε με δύο διαφορετικούς τρόπους το ίδιο γράφημα που σκοπό έχει να δείξει την οδική συνδεσμολογία ανάμεσα σε πέντε πόλεις της Κρήτης. Η ύπαρξη μιας ακμής ανάμεσα σε δύο κορυφές (πόλεις) υποδηλώνει την ύπαρξη ενός δρόμου. Το σύνολο κορυφών σε αυτό το γράφημα είναι το

$V=\{$ Ηράκλειο, Ρέθυμνο, Ανώγεια, Μοίρες, Σπήλι $\}$

ενώ το σύνολο ακμών είναι το

$E= \{$ $\{$ Ηράκλειο, Ρέθυμνο $\}$, $\{$ Ηράκλειο, Ανώγεια $\}$, $\{$ Ανώγεια, Ρέθυμνο $\}$, $\{$ Ρέθυμνο, Σπήλι $\}$, $\{$ Σπήλι, Μοίρες $\}$, $\{$ Μοίρες, Ηράκλειο $\}$ $\}$.

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

Σχήμα 5.2: Ενα απλό γράφημα με 6 κορυφές και 7 ακμές

Παράδειγμα 5.1   Συνήθως τα ονόματα που επιλέγουμε για τις κορυφές είναι απλά αριθμοί. Ένα τυπικό γράφημα είναι π.χ. το γράφημα του Σχήματος 5.2 που έχει σύνολο κορυφών το

$$V={\left\{{1,2,3,4,5,6}\right\}}$$

και σύνολο ακμών το

$$E={\left\{{ {\left\{{1,2}\right\}}, {\left\{{1,4}\right\}}, {\lef... ...eft\{{3,6}\right\}}, {\left\{{4,6}\right\}}, {\left\{{5,6}\right\}}}\right\}}.$$

Άσκηση 5.1   Δύο απλά γραφήματα $G_1=(V,E)$ και $G_2 =(V,E_2)$ με το ίδιο σύνολο κορυφών λέγονται συμπληρωματικά αν $E_1 \cap E_2 = \emptyset$ και η ένωση $E_1 \cup E_2$ είναι όλα τα διμελή υποσύνολα του $V$. Με άλλα λόγια δύο κορυφές του $V$ συνδέονται με ακμή στο $G_1$ αν και μόνο αν δε συνδέονται στο $G_2$.

Δείτε το Σχήμα 5.3 για παράδειγμα.

Βρείτε το συμπληρωματικό γράφημα αυτού που παρουσιάζεται στο Παράδειγμα 5.1.

Σχήμα 5.3: Εδώ βλέπουμε δύο συμπληρωματικά γραφήματα με κοινό σύνολο κορυφών $V = {\left\{{1, 2, 3, 4, 5}\right\}}$. Τα δύο γραφήματα είναι αυτό με τις μπλε και αυτό με τις κόκκινες ακμές. Κάθε δυνατή ακμή ανάμεσα σε στοιχεία του $V$ είναι χρωματισμένη είτε μπλε είτε κόκκινη.

Σχήμα 5.4: Τα διαφορετικά απλά γραφήματα με 3 κορυφές

Παράδειγμα 5.2   Στο Σχήμα 5.4 δείχνουμε όλα τα διαφορετικά απλά γραφήματα με 3 κορυφές.

Άσκηση 5.2   Πόσα διαφορετικά γραφήματα υπάρχουν με $n$ κορυφές; Πόσα με $n$ κορυφές και $k$ ακμές; ( $0\le k \le n$)

Αν δυο κορυφές $u$ και $v$ ενώνονται στο $G$ (δηλ. αν ${\left\{{u,v}\right\}} \in E$) θα γράφουμε συνήθως $u \sim v$ ή και $u \stackrel{G}{\sim} v$ αν θέλουμε να τονίσουμε για ποιο γράφημα μιλάμε. Ομοίως θα γράφουμε $e_1 \sim e_2$ για δύο ακμές $e_1$ και $e_2$ αν αυτές μοιράζονται μια από τις δυό τους κορυφές.

Ορισμός 5.2   (Γειτονικές κορυφές και ακμές, γειτονιές) Δύο κορυφές που συνδέονται με ακμή (αντ. ακμές που έχουν μια κοινή κορυφή) θα λέγονται γειτονικές ή γείτονες και το σύνολο των γειτόνων μιας κορυφής (αντ. ακμής) $u$ θα λέγεται η γειτονιά του $u$ και θα συμβολίζεται συνήθως με $N(u)$.

Δείτε το Σχήμα 5.5 για παράδειγμα.

Σχήμα 5.5: Στο γράφημα αυτό φαίνεται με πράσινο χρώμα η γειτονιά της κορυφής 3 (οι κορυφές 2, 5, 7) και με κόκκινο χρώμα η γειτονιά της κορυφής 8 (οι κορυφές 5, 6, 9)

Παράδειγμα 5.3   Στο γράφημα του Σχήματος 5.2 έχουμε

$$N(1)={\left\{{2, 4}\right\}}, N(2)={\left\{{1, 3}\right\}}, N(3... ...6}\right\}},\ N(5)={\left\{{3, 6}\right\}}, N(6)={\left\{{3, 4, 5}\right\}}.$$

Η γειτονιά της ακμής ${\left\{{3,6}\right\}}$ είναι το σύνολο ακμών

$$N((3,6)) = {\left\{{{\left\{{2, 3}\right\}}, {\left\{{3, 5}\right... ...\{{4, 6}\right\}}, {\left\{{4, 5}\right\}}, {\left\{{3, 6}\right\}}}\right\}}.$$

Παρατηρήστε ότι μια ακμή είναι πάντα γείτονας του εαυτού της σύμφωνα με τον ορισμό που έχουμε δώσει, ενώ μια κορυφή ποτέ δε γειτονεύει με τον εαυτό της σε ένα απλό γράφημα (αυτό αλλάζει αργότερα όταν θα εξετάζουμε γενικότερα γραφήματα).

Ορισμός 5.3   (Βαθμός κορυφής, ακμής. Κανονικό γράφημα.) Βαθμός μιας κορυφής $u \in V$ (θα συμβολίζεται με $\deg u$) λέγεται το πλήθος των ακμών που έχουν την $u$ ως άκρο τους. Δηλ. $\deg u = {\left\vert{N(u)}\right\vert}$. Ομοίως ορίζεται ο βαθμός μιας ακμής.

Κανονικό ονομάζεται ένα γράφημα όταν όλες οι κορυφές του έχουν τον ίδιο βαθμό. Αν ο κοινός αυτός βαθμός είναι $r$ τότε λέγεται $r$-κανονικό.

Δείτε το Σχήμα 5.6 για παράδειγμα ενός κανονικού γραφήματος.

Σχήμα 5.6: Ένα κανονικό γράφημα βαθμού 4 με 6 κορυφές

Παράδειγμα 5.4   Στο Σχήμα 5.2, αν σβήσουμε την ακμή ${\left\{{3,6}\right\}}$, όλες οι κορυφές έχουν βαθμό 2, άρα είναι το γράφημα αυτό 2-κανονικό. Στο Σχήμα 5.1 ο βαθμός των κορυφών Ηράκλειο και Ρέθυμνο είναι 3 και των άλλων κορυφών είναι 2.

Άσκηση 5.3   Γίνεται σε ένα γράφημα όλες οι κορυφές να έχουν διαφορετικό βαθμό;

Υπόδειξη: Οι δυνατές τιμές για το βαθμό μιας κορυφής σε ένα γράφημα με $n$ κορυφές είναι $0, 1, \ldots, n-1$. Μπορούμε να έχουμε κορυφή βαθμού 0 και κορυφή βαθμού $n-1$ ταυτόχρονα;

Άσκηση 5.4   Δείξτε ότι σε ένα γράφημα $G=(V,E)$ το άθροισμα των βαθμών όλων των κορυφών ισούται με $2 {\left\vert{E}\right\vert}$.

Άσκηση 5.5   Πόσες ακμές έχει ένα $r$-κανονικό γράφημα με $n$ κορυφές; Υπάρχει $3$-κανονικό γράφημα με $7$ κορυφές;

Υπόδειξη: Άσκηση 5.4.

Άσκηση 5.6   Δείξτε ότι σε οποιοδήποτε γράφημα το πλήθος κορυφών με περιττό βαθμό είναι άρτιο.

Άσκηση 5.7   Αν $n>0$ δείξτε ότι υπάρχει $n$-κανονικό γράφημα με $2n$ κορυφές.

Άσκηση 5.8   Ένα σύνολο κορυφών ενός γραφήματος λέγεται ανεξάρτητο αν κάθε δύο κορυφές του δε συνδέεονται με ακμή. Επίσης, ένα σύνολο κορυφών λέγεται κάλυμμα αν κάθε ακμή του γραφήματος περιέχει κάποια από τις κορυφές αυτές.

Δείξτε ότι σ' ένα γράφημα $G=(V,E)$ το σύνολο κορυφών $A \subseteq V$ είναι ανεξάρτητο αν και μόνο αν το σύνολο κορυφών $V\setminus A$ είναι κάλυμμα.

Δείτε το Σχήμα 5.7 για παράδειγμα.

Σχήμα 5.7: Στο γράφημα αυτό οι κόκκινες κορυφές αποτελούν ανεξάρτητο σύνολο και το συμπλήρωμά τους, οι πράσινες κορυφές, αποτελούν κάλυμμα