Εφαρμογές Θεωρίας Γραφημάτων

Theory Notes


Εισαγωγή

Ένα γράφημα \(G (V,E)\) είναι μια δομή που αποτελείται από ένα σύνολο κορυφών \(V = \{v1, v2,...\}\) και από ένα σύνολο ακμών \(Ε = \{e1, e2,...\}\).

Γενικά το \(V\) και \(E\) είναι πεπερασμένα, έτσι λέμε ότι και το γράφημα \(G\) είναι πεπερασμένο.

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

Γράφημα 1.1 graph_number_1

Οπότε στο πάνω γράφημα έχουμε: \(d(v1)= 2, d(v3) = 3\) κτλ.

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

Πχ Έστω V και E είναι ο αριθμός των κορυφών και ο αριθμός των ακμών. Παρατηρούμε ότι:
\[\displaystyle\sum_{i=1}^{|V|}d(v_i) = 2\cdot|E|\]

Αν την εφαρμόσουμε στο γράφημα 1.1, μπορούμε να δούμε ότι η παραπάνω σχέση ισχύει:

\[d(v1) + d(v2) + d(v3) + d(v4) + d(v5) = 2 \cdot |E| \iff \\ \iff 2 + 3 + 3 + 2 + 2 = 2\cdot 6 \iff \\ 12 = 12\]

Ένα μονοπάτι \(\textrm{P}\) είναι μια ακολουθία κορυφών και ακμών, που διαπλέκονται με τον ακόλουθο τρόπο:

To \(\textrm{P}\) αρχίζει από μία κορυφή και ακολουθεί την ακμή στην επόμενη κορυφή κτλ.

Αν το μονοπάτι είναι πεπερασμένο τότε λέμε ότι αρχίζει από μία κορυφή (ας πούμε v0) και τελειώνει σε μία άλλη (ας πούμε v1).

Ο αριθμός των ακμών στο κάθε μονοπάτι είναι και το μέγεθος(length) του μονοπατιού P.

Ένα πεπερασμένο μονοπάτι P στο οποίο η αρχή και το τέλος είναι ίδια κορυφή ονομάζεται κύκλος \(\textrm{C}\).

Ένα γράφημα \(G (V,E)\) ονομάζεται directed graph, όταν το τέλος κάθε ακμής δείχνει σε μία κορυφή.

\[u\to v\]

Η κορυφή \(u\) ονομάζεται αρχική κορυφή και η κορυφή \(v\) ονομάζεται τελική κορυφή.

Οι ακμές με την ίδια αρχική και τελική κορυφή ονομάζονται παράλληλες. Σε αντίθετη περίπτωση ονομάζονται μη-παράλληλες.

Ο βαθμός εξόδου μίας καρυφής \(v\) είναι ο αριθμός των (directed) ακμών, που έχουν την \(v\) ως αρχική κορυφή. Το αντίστοιχο ισχύει και για τον βαθμό εισόδου.

Από το πάνω συμπεραίνουμε ότι:

\[\displaystyle\sum_{v \in V}d_{out}(v) = \displaystyle\sum_{v \in V}d_{in}(v)\]


Γραφήματα Euler

Ένα Euler μονοπάτι ενός πεπερασμένου undirected γραφήματος \(G (V,E)\) είναι ένα μονοπάτι όπου κάθε ακμή εμφανίζεται μόνο μία φορά. Οπότε το μέγεθος του μονοπατιού είναι όσο και οι ακμές του γραφήματος length = \(E\).

Αν ένα γράφημα έχει Euler μονοπάτι τότε λέγεται γράφημα Euler.

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

Κύκλοι Hamilton

Κύκλος Hamilton είναι ένας κύκλος ενός γραφήματος \(G\) ο οποίος περιέχει όλες τις κορυφές του.

Μονοπάτι Hamilton είναι ένα μονοπάτι το οποίο περιέχει όλες τις κορυφές του γραφήματος \(G\).

Ένα γράφημα το οποίο περιέχει έναν κύκλο Hamilton ονομάζεται και γράφημα Hamilton.

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

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

Dirac's Theorem: Έστω ένα γράφημα \(G\) το οποίο έχει πάνω από τρεις κορυφές \((n \geq 3)\), αν για κάθε κορυφή του γραφήματος \(G\) ισχύει \(d(v)\geq{\dfrac{n}{2}}\) τότε το γράφημα \(G\) έχει κύκλο Hamilton

Ore's Theorem: Έστω ένα γράφημα \(G\) το οποίο έχει πάνω από τρεις κορυφές \((n \geq 3)\), αν \(d(x)+d(y)\geq{n}\) για όλες τις διαφορετικές μη γειτονικές κορυφές τότε το γράφημα \(G\) έχει κύκλο Hamilton.

\(G_1\) hamilton_G1.png

To \(G_1\) είναι γράφημα Hamilton.

\(G_2\) hamilton_G2.png

To \(G_2\) είναι επίσης γράφημα Hamilton.


S.P Αλγόριθμοι

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

Υπάρχουν ορισμένα χαρακτηριστικά που μας βοηθάνε να βρούμε ποιόν αλγόριθμο θα χρησιμοποιήσουμε:

  • Αν το γράφημα είναι πεπερασμένο ή μη.
  • Αν το γράφημα είναι directed ή undirected.
  • Αν οι ακμές είναι μεγέθους 1 ή όλα τα μεγέθη είναι μη αρνητικά ή είναι όλα αρνητικά
  • Αν έχουμε μία αρχική κορυφή και μία τελική ή αν έχουμε πολλές τελικές κορυφές ή από κάθε κορυφή σε όλες τις κορυφές.

Dijkstra’s Algorithm

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

Κάθε κορυφή αποτελείται από δύο μέρη \(L(v)=(x, (w(v)))\). Το πρώτο μέρος είναι το όνομα της κορυφής που χρησιμοποιήθηκε για να φτάσουμε στο \(v\) ενώ το δεύτερο είναι το weight του μονοπατιού που χρησιμοποιήθηκε για να φτάσουμε στο \(v\). Σε κάθε βήμα του αλγορίθμου θα έχουμε ορισμένες ελεύθερες κορυφές τις οποίες θα τις συμβολίζουμε με \(F\). Αυτές οι κορυφές είναι οι γείτονες των κορυφών που έχουμε επισκεφτεί.

Βήματα για τον Αλγόριθμο:

  1. Για κάθε κορυφή του γραφήματος \(G\) δίνουμε ορίζουμε μία ετικέτα \(L(x)\) έτσι ώστε \(L(x)=(-,0)\) αν \(x=\textrm{Αρχή}\) και \(L(x)=(-,\infty)\).

  2. Σημειώνουμε την αρχή ως \(u=\textrm{Αρχή}\) και ορίζουμε το σύνολο \(F\) να είναι οι γείτονες του \(u\) .Μετά ανανεώνουμε τις ετικέτες για κάθε κορυφή \(v\) στο \(F\) με τον εξής τρόπο:

    Αν \(w(u)+w(a) < w(v)\) τότε \(L(v)=(u, w(u)+w(uv))\) αλλιώς το \(L(v)\) παραμένει ίδιο.

  3. Σημειώνουμε την κορυφή με το μικρότερο weight καθώς και την ακμή \(uv\) που χρισημοποιήθηκαν για να ανανεώσουμε την ετικέτα. Ορίζουμε \(u=v\).

  4. Επαναλαμβάνουμε τα βήματα \(2\) και \(3\) μέχρι να έχουμε περάσει από κάθε κορυφή.

  5. Πλέον γνωρίζουμε το συντομότερο μονοπάτι από την κορυφή Αρχή μέχρι οποιαδήποτε κορυφή του γραφήματος.


Breadth-First Search (BFS)

Ο αλγόριθμος αυτός είναι αρκετά απλός στην κατανάοηση αλλά και στην υλοποίηση του.


Χρωματισμός

Για κάθε γράφημα \(G\) ισχύει \(χ'(G)\geqΔ(G)\). Για κάθε διμερές γράφημα ισχύει \(χ'(G)=Δ(G)\)

Διμερές ονομάζουμε το γραφήμα όπου το \(V\) μπορεί να διαμεριστεί σε δύο υποσύνολα \(V1, V2\) τέτοια ώστε κάθε \(e \isin E\) ενώνει ένα κόμβο του \(V1\) με ένα κόμβο του \(V2\).

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


Ακμών

Έστω ένα γράφημα \(G=(V,E)\), edge-coloring είναι η διαδικασία ανάθεσης χρωμάτων στις ακμές του γραφήματος \(G\) έτσι ώστε αν δύο ακμές μοιράζονται την ίδια κορυφή τότε τους δίνονται διαφορετικά χρώματα. Ο μικρότερος αριθμός χρωμάτων που χρειάζονται για όλα τα πιθανά edge-colorings ονομάζεται χρωματικός δείκτης και συμβολίζεται \(χ'(G)\).

Ο χρωματικός αριθμός συμβολίζεται \(χ(G)\) και είναι ίσος με τον αριθμό των κορυφών σε ένα πλήρες γράφημα.

Για παράδειγμα, ας βρούμε τον χρωματικό δείκτη για \(K_n\) για κάθε \(n\) μέχρι το \(5\).

  • \[K_1\]

    Σε αυτή την περίπτωση έχουμε μόνο μία κορυφή χωρίς καμία ακμή. Άρα \(χ'(K_1) = 0\).

color_k_1.png


  • \[K_2\]

    Σε αυτή την περίπτωση έχουμε δύο κορυφές και μία μόνο ακμή. Άρα θα έχουμε \(χ'(K_2) = 1\).

no_color_k_2.png arrow_right.png color_k_2.png


  • \[K_3\]

    Σε αυτή την περίπτωση γνωρίζουμε πως κάθε \(2\) ακμές έχουν κοινή κορυφή. Άρα θα έχουμε \(χ'(K_3) = 3\).

no_color_k_3.png arrow_right.png color_k_3.png


  • \[K_4\]

    Σε αυτή την περίπτωση μπορούμε απλώς να χρωματίσουμε τις αντίθετες ακμές με το ίδιο χρώμα. Οπότε έχουμε \(χ'(K_4) = 3\).

no_color_k_4.png arrow_right.png color_k_4.png

  • \[K_5\]

    Αυτή η περίπτωση είναι λίγο πιο περίπλοκη από τις προηγούμενες. Ο χρωματικός δείκτης είναι \(χ'(K_5) = 5\).

no_color_k_5.png arrow_right.png color_k_5.png

Γενικά ισχυεί ότι αν το \(n\) είναι άρτιος τότε \(χ'(K_n)=n-1\), αν \(n\) είναι περιττός τότε \(χ'(K_n)=n\).

Τέλος για κάθε απλό γράφημα \(G\) ισχύει:

\[Δ(G) \leq χ'(G) \leq Δ(G)+1\]


Επίπεδα Γραφήματα

Τα επίπεδα γραφήματα είναι εκείνα όπου καμία ακμή δεν συμπίπτει με άλλη ακμή.

not_planar_graph.png \(G_1\)


planar_graph.png \(G_2\)

Το \(G_1\) δεν είναι επίπεδο γράφημα ενώ το \(G_2\) είναι επίπεδο γράφημα.

Επίσης κάθε επίπεδο γράφημα έχει μία κορυφή βαθμού μικρότερου ή ίσου του 5.


Το θεώρημα του Kuratowski

Έχουμε τα γραφήματα \(Κ_5\) και \(Κ_{3,3}\).

no_color_k_5.png \(Κ_5\)


graph_k_3_3.png \(Κ_{3,3}\)

Ο Kuratowski λέει πως αν ένα γράφημα περιέχει ένα υπογράφημα που είναι ομοιόμορφο είτε στο \(Κ_5\) είτε στο \(Κ_{3,3}\) ή περιέχει ένα από τα γραφήματα \(Κ_5\) και \(Κ_{3,3}\) τότε δεν είναι επίπεδο γράφημα.

Όντως αφού αν προσπαθήσουμε να ζωγραφήσουμε είτε το \(Κ_5\) είτε το \(Κ_{3,3}\) χωρίς τις ακμές τους να συμπίπτουν θα αποτύχουμε. Άρα προφανώς αν ένα γράφημα περιέχει ένα από τα πάνω γραφήματα δεν θα μπορούμε να το αλλάξουμε με τέτοιο τρόπο ώστε να γίνει επίπεδο γράφημα.

Αν για παράδειγμα έχουμε το \(Κ_4\) γράφημα:

no_color_k_4.png \(Κ_4\)

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

graph_k_4_planar.png \(Κ_4\)

Το από πάνω γράφημα είναι το \(Κ_4\) γράφημα ζωγραφισμένο με τέτοιο τρόπο που φαίνεται ότι είναι επίπεδο.