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

δηλαδή όταν αντιστοιχεί χρώματα στους κόμβους του G έτσι ώστε κάθε δύο συνδεμένοι κόμβοι να έχουν διαφορετικό χρώμα. Αν το C έχει n διακεκριμένα στοιχεία και ο χρωματισμός f είναι επί, τότε ονομάζεται n-χρωματισμός. Κάθε χρωματισμός διαμερίζει το V(G) σε κλάσεις κόμβων οι οποίοι έχουν κοινό χρώμα. Οι κλάσεις αυτές ονομάζονται χρωματικές κλάσεις.
Πίνακας περιεχομένων |
[Επεξεργασία] Χρωματικός αριθμός
Για δοσμένο γράφημα G και δοσμένα χρώματα C δεν υπάρχει πάντα απεικόνιση f που να είναι χρωματισμός του G. Συγκεκριμένα η ύπαρξη χρωματισμού εξαρτάται από τον πληθάριθμο του C. Αν για παράδειγμα έχουμε το γράφημα G του σχήματος 1, όπου έχουμε V(G) = {u,v} και E(G)={(u,v)}, και έχουμε μόνον ένα διαθέσιμο χρώμα, C = {μαύρο}, τότε δεν μπορούμε να χρωματίσουμε τους δύο κόμβους διαφορετικά, παρά χρειαζόμαστε τουλάχιστον ένα ακόμη χρώμα.
Ο ελάχιστος πληθάριθμος του C, n, για τον οποίο υπάρχει n-χρωματισμός του G ονομάζεται χρωματικός αριθμός του G και συμβολίζεται με Χ(G).
[Επεξεργασία] Ιδιότητες
Μερικές από τις ιδιότητες που ικανοποιεί ο χρωματικός αριθμός είναι οι παρακάτω:
1. Αν p είναι στο πλήθος οι κόμβοι του G τότε , αφού για ένα γράφημα μπορούμε να χρησιμοποιήσουμε το πολύ τόσα διαφορετικά χρώματα, όσοι είναι και οι κόμβοι του. Η ισότητα ισχύει όταν το γράφημα είναι πλήρες, όπου κάθε κόμβος χρειάζεται το δικό του χρώμα, καθώς συνδέεται με κάθε άλλον.
2. Αν Kp είναι το πλήρες γράφημα p κόμβων και x είναι ένας δεσμός του, τότε X(Kp − x) = p − 1.
3. Αν Km,n είναι ένα οποιοδήποτε διγράφημα, τότε X(Km,n) = 2.
4. Για τους άρτιους κύκλους είναι X(C2m), αφού εναλλάξ μπορούμε να αλλάζουμε χρώμα από κόμβο σε κόμβο, ενώ για τους περιττούς κύκλους ισχύει ανάλογα X(C2m + 1) = 3.
5. Αν Τ είναι ένα δέντρο, τότε X(T) = 2.
6. Εύκολα φαίνεται ότι , ότι αρκεί δηλαδή ένα χρώμα για να χρωματίσουμε ένα γράφημα μόνον όταν αυτό είναι πλήρως ασυνδετικό.
7. Θεώρημα του Κένιχ: Ένα γράφημα έχει έναν 2-χρωματισμό αν και μόνον αν δεν περιέχει περιττούς κύκλους

8. Αν Δ(G) είναι ο μεγαλύτερος βαθμός που αντιστοιχεί σε κάποιον από τους κόμβους του G, δηλαδή

τότε ισχύει η εξής ανισότητα:

9. Θεώρημα των πέντε χρωμάτων (Heawood, 1890): Αν G είναι επίπεδο γράφημα, τότε αρκούν το πολύ πέντε χρώματα για να χρωματιστεί, δηλαδή .
Απόδειξη: Ας πούμε ότι το G έχει p στο πλήθος κόμβους. Θα εφαρμόσουμε τη μέθοδο της (ισχυρής) μαθηματικής επαγωγής.
Αν , τότε το θεώρημα ισχύει με βάση την ιδιότητα 1. Υποθέτουμε λοιπόν ότι το θεώρημα ισχύει για p κόμβους.
Αν το G έχει p+1 κόμβους, με , αποδεικνύεται ότι θα περιέχει έναν οπωσδήποτε κόμβο v με βαθμό
. Από την επαγωγική υπόθεση έχουμε επίσης
, μια και το γράφημα G - v έχει p κόμβους.
Έστω τώρα ότι οι πέντε κόμβοι που συνδέονται με τον v θα χρωματιστούν με τα χρώματα a, b, c, d, e, μέσω χρωματισμού f. Αν κάποια από τα χρώματα αυτά συμπίπτουν ή αν ο βαθμός του v είναι μικρότερος από 5, τότε το θεώρημα ισχύει. Αν αντίθετα τα χρώματα είναι διακεκριμένα και δ(v) = 5, τότε έχουμε την περίπτωση του σχήματος 2. Αρκεί να δείξουμε ότι ο v μπορεί να χρωματιστεί με κάποιο από τα a, b, c, d, e. Θεωρούμε το υπογράφημα , που ορίζεται ως εξής:

που αποτελείται δηλαδή από τους κόμβους που έχουν χρώμα a ή b. Αν οι v1, v3 ανήκουν σε διαφορετικούς παράγοντες του Ga,b, τότε αλλάζουμε τα χρώματα στον παράγοντα του v1 και θέτουμε f(v) = a, χρωματίζουμε δηλαδή τον v με a. (Θα μπορούσαμε αντί για αυτό να αλλάξουμε χρώματα στον παράγοντα που βρίσκεται ο v3 και να χρωματίζαμε τον v με b.) Αν οι v1, v3 ανήκουν στον ίδιο παράγοντα, τότε θα υπάρχει ένα μονοπάτι στο Ga,b από τον έναν στον άλλο, δηλαδή ένα μονοπάτι στο G που είναι χρωματισμένο μόνο με a και c και που δεν περιέχει τις v2, v4, v5. Ο κύκλος που σχηματίζει το μονοπάτι με το μονοπάτι
, θα περικυκλώνει είτε τoν κόμβο v2 είτε τους κόμβους v4, v5, μια και το G είναι επίπεδο γράφημα. Όπως και να έχει, οι v2, v4 θα ανήκουν σε διαφορετικούς παράγοντες του υπογραφήματος Gb,d (ορίζεται όπως το Ga,b), οπότε, όμοια με προηγούμενα, αλλάζοντας τα χρώματα είτε στον παράγοντα του v2 είτε στου v4 χρωματίζουμε ανάλογα τον v με b ή d. Αποδείξαμε δηλαδή σε κάθε περίπτωση, ότι το θεώρημα ισχύει και για p + 1 κόμβους και η επαγωγή ολοκληρώθηκε.
10. Θεώρημα των τεσσάρων χρωμάτων (Appel & Haken, 1976): Αν G είναι επίπεδο γράφημα τότε αρκούν το πολύ τέσσερα χρώματα για να χρωματιστεί, δηλαδή .
[Επεξεργασία] Αλγόριθμοι χρωματισμού
Οι αλγόριθμοι χρωματισμού αποσκοπούν στο να προσδιορίσουν το χρωματικό αριθμό ενός δοσμένου γραφήματος. Οι επόμενοι δύο αλγόριθμοι βασίζονται στην τεχνική branch & bound, σε απαρίθμηση δηλαδή περιπτώσεων υπό περιορισμούς.
[Επεξεργασία] Αλγόριθμος ανεξάρτητων συνόλων κορυφών
Καλούμε ανεξάρτητο σύνολο κόμβων ενός γραφήματος G κάθε υποσύνολο του V(G) που έχει πλήρως ασυνδετικό φέρον γράφημα (spanning graph). Κάθε τέτοιο σύνολο εκπροσωπεί και μία χρωματική κλάση. Αν είναι ανεξάρτητα σύνολα κόμβων τέτοια ώστε
, και υπάρχει ελάχιστος s το πολύ ίσος με τον r, για τον οποίο
, τότε X(G) = s.
Συγκεκριμένα, ο αλγόριθμος εκτελείται σε δύο φάσεις:
- Εύρεση όλων των ανεξάρτητων συνόλων κόμβων που πληρούν τα παραπάνω.
- Εύρεση του μικρότερου μήκους ένωσης που αποδίδει το V(G).
[Επεξεργασία] Αλγόριθμος του Χριστοφίδη
Ο αλγόριθμος συνίσταται στα εξής βήματα:
- Διατάσουμε τους κόμβους του γραφήματος σε φθίνουσα σειρά βαθμών.
- Θέτουμε f(x1) = 1
- Ελέγχουμε τον xm, όταν ήδη έχουν δοθεί κ χρώματα. Αν δεν συνδέεται άμεσα με ήδη ελεγγμένους κόμβους και xn, με n < m, είναι ο αρχύτερος από αυτούς, τότε θέτουμε f(xm) = f(xn). Αλλιώς θέτουμε f(xm) = κ + 1.