5.6 Γενικεύσεις της έννοιας του γραφήματος

Ορισμός 5.15   (Κατευθυνόμενα γραφήματα) Κατευθυνόμενα γραφήματα είναι ζευγάρια $(V,E)$, όπου και πάλι $V$ είναι ένα σύνολο κορυφών, αλλά το σύνολο $E$ των ακμών είναι τώρα όχι ένα σύνολο διμελών υποσυνόλων του $V$ αλλά ένα σύνολο διατεταγμένων ζευγών με στοιχεία από το $V$, δηλ. $E \subseteq V\times V$.

Ανάλογα με την περίπτωση μπορεί κανείς να επιτρέπει ή όχι και ζευγάρια της μορφής $(v,v)$ (τέτοιες ακμές ονομάζονται βρόχοι). Το σημαντικό πάντως είναι ότι δε μπορεί πλέον κανείς να λέει ότι «$i$ συνδέεται με το $j$» αλλά πρέπει να προσδιορίζει και την κατεύθυνση της σύνδεσης.

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

Ορισμός 5.17   (Αυτοσυνδέσεις ή βρόχοι) Γραφήματα με αυτοσυνδέσεις (κατευθυνόμενα ή μη) είναι αυτά στα οποία επιτρέπουμε μια κορυφή να συνδέεται με τον εαυτό της. Μια τέτοια ακμή ονομάζεται αυτοσύνδεση ή βρόχος.

Ορισμός 5.18   (Βάρη στις ακμές) Γραφήματα με βάρη/κόστη είναι αυτά (κατευθυνόμενα ή μη) στα οποία κάθε ακμή έχει και ένα βάρος/κόστος.

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

Σχήμα 5.25: Μη απλά γραφήματα

Στο Σχήμα 5.25 δείχνουμε δύο γραφήματα. Το αριστερό είναι ένα κατευθυνόμενο γράφημα με σύνολα κορυφών και ακμών τα

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

$$E = {\left\{{ (2, 3), (2, 4), (3, 1), (4, 2), (4,3)}\right\}}$$

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

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

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

Ορισμός 5.19   (Απόσταση σε γραφήματα με βάρη) Ετσι, το μήκος ενός μονοπατιού σε ένα γράφημα με βάρη είναι απλώς το άθροισμα των βαρών των ακμών που συμμετέχουν στο μονοπάτι. Η απόσταση ανάμεσα στις κορυφές $u$ και $v$ ορίζεται ως το έλάχιστο μήκος μονοπατιού που συνδέει τις $u$ και $v$ ($+\infty$ αν δεν συνδέονται με κάποιο μονοπάτι), και η διάμετρος του γραφήματος $G$ ορίζεται ως η μέγιστη απόσταση ανάμεσα σε δύο κορυφές του $G$, όπως και πριν.

Άσκηση 5.39   Δείξτε ότι η τριγωνική ανισότητα (5.2) εξακολουθεί να ισχύει και για τη νέα έννοια απόστασης (πάντα μιλάμε για γραφήματα με μη αρνητικά βάρη).

Υπόδειξη: Η απόδειξη είναι σχεδόν ταυτόσημη με αυτή για τη συνηθισμένη έννοι απόστασης σε απλά γραφήματα.

Σχήμα 5.26: Για την Άσκηση 5.40

Άσκηση 5.40   Σε μια χώρα υπάρχουν $N$ πόλεις και ακριβώς $N$ δρόμοι ανάμεσά τους, όλοι μονόδρομοι, όπως φαίνεται στο Σχήμα 5.26. Φυσικά κάποιες πόλεις μπορεί και να μην έχουν καθόλου δρόμους που να ξεκινάνε ή να καταλήγουν σε αυτές.

Ας ονομάσουμε $Z$ τον αριθμό των πόλεων στις οποίες δεν καταλήγει κανείς δρόμος και $E$ τον αριθμό των πόλεων στις οποίες καταλήγει άρτιος αριθμός δρόμων (του 0 συμπεριλαμβανομένου). Στο Σχήμα 5.26 έχουμε $Z=2$ και $E=4$.

Δείξτε ότι $2Z \ge E$.