Θεωρία Γράφων — Κορυφές, Ακμές και Βασικές Έννοιες

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

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

Τι Σημαίνει Ένας Γράφος Στα Μαθηματικά

Σε έναν μη κατευθυνόμενο γράφο, μια ακμή δηλώνει ότι δύο κορυφές είναι συνδεδεμένες και η σύνδεση δεν έχει κατεύθυνση. Αν το $A$ συνδέεται με το $B$, τότε και το $B$ συνδέεται με το $A$.

Σε έναν κατευθυνόμενο γράφο, οι ακμές έχουν κατεύθυνση, οπότε οι προτάσεις $A \to B$ και $B \to A$ είναι διαφορετικές. Πολλά εισαγωγικά παραδείγματα χρησιμοποιούν απλούς μη κατευθυνόμενους γράφους, που σημαίνει ότι δεν υπάρχουν βρόχοι και δεν υπάρχουν επαναλαμβανόμενες ακμές ανάμεσα στις ίδιες δύο κορυφές.

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

Βασικοί Όροι της Θεωρίας Γράφων που Πρέπει να Ξέρεις Πρώτα

Κορυφές και ακμές

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

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

Βαθμός

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

Αν μια πόλη έχει δρόμους προς τρεις άλλες πόλεις, ο βαθμός της είναι $3$.

Μονοπάτι

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

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

Κύκλος

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

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

Συνεκτικός γράφος και συνεκτικές συνιστώσες

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

Αν αυτό δεν ισχύει, ο γράφος χωρίζεται σε συνεκτικές συνιστώσες. Κάθε συνιστώσα είναι ένα συνεκτικό κομμάτι του γράφου.

Λυμένο Παράδειγμα: Ένας Μικρός Γράφος

Έστω ότι ένας γράφος έχει κορυφές $A$, $B$, $C$, $D$ και $E$, με ακμές

$$AB,\ AC,\ BC,\ CD$$

Αυτό δίνει ένα τρίγωνο στις κορυφές $A$, $B$ και $C$, μία επιπλέον ακμή από το $C$ στο $D$ και μία απομονωμένη κορυφή $E$.

Τώρα οι βασικές ιδέες φαίνονται εύκολα.

Οι βαθμοί είναι

$$\deg(A)=2,\ \deg(B)=2,\ \deg(C)=3,\ \deg(D)=1,\ \deg(E)=0$$

Υπάρχει ένα μονοπάτι από το $A$ στο $D$:

$$A-C-D$$

Υπάρχει ένας κύκλος:

$$A-B-C-A$$

Ο γράφος δεν είναι συνεκτικός, επειδή το $E$ δεν μπορεί να προσεγγιστεί από τις άλλες κορυφές. Άρα ο γράφος έχει δύο συνεκτικές συνιστώσες: μία που περιέχει τα $A,B,C,D$ και μία που περιέχει μόνο το $E$.

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

Ένας Γρήγορος Έλεγχος: Άθροισμα Βαθμών

Για κάθε πεπερασμένο μη κατευθυνόμενο γράφο,

$$\sum \deg(v) = 2|E|$$

Αυτό ισχύει επειδή κάθε ακμή έχει ακριβώς δύο άκρα, οπότε κάθε ακμή προσθέτει $1$ σε δύο μετρήσεις βαθμού.

Στο παραπάνω παράδειγμα, το άθροισμα των βαθμών είναι

$$2+2+3+1+0=8$$

και ο αριθμός των ακμών είναι $4$, άρα

$$2|E| = 2 \cdot 4 = 8$$

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

Συνηθισμένα Λάθη στη Θεωρία Γράφων

Μπέρδεμα ανάμεσα σε κορυφές και ακμές

Οι κορυφές είναι τα αντικείμενα. Οι ακμές είναι οι σχέσεις ανάμεσά τους.

Να ξεχνάς τι είδους γράφο έχεις

Μια πρόταση που είναι αληθής για έναν απλό μη κατευθυνόμενο γράφο μπορεί να χρειάζεται αλλαγή για έναν κατευθυνόμενο γράφο ή για έναν γράφο που επιτρέπει βρόχους.

Να αντιμετωπίζεις ένα μονοπάτι σαν κύκλο

Ένα μονοπάτι δεν χρειάζεται να επιστρέφει εκεί από όπου ξεκίνησε. Ένας κύκλος χρειάζεται.

Να αγνοείς τις απομονωμένες κορυφές

Μια κορυφή με βαθμό $0$ εξακολουθεί να είναι μέρος του γράφου. Μπορεί να αλλάξει το αν ο γράφος είναι συνεκτικός.

Πού Χρησιμοποιούνται τα Βασικά της Θεωρίας Γράφων

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

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

Δοκίμασε Έναν Παρόμοιο Γράφο

Σχεδίασε τέσσερις κορυφές $P$, $Q$, $R$ και $S$. Πρόσθεσε τις ακμές $PQ$, $QR$, $RS$ και $SP$.

Έπειτα απάντησε σε τρεις ερωτήσεις: ποιος είναι ο βαθμός κάθε κορυφής, είναι ο γράφος συνεκτικός και περιέχει ο γράφος κύκλο;