Χρωματισμός γραφήματος

Χρωματικός αριθμός

Για δοσμένο γράφημα 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 τότε X(G)\leq p, αφού για ένα γράφημα μπορούμε να χρησιμοποιήσουμε το πολύ τόσα διαφορετικά χρώματα, όσοι είναι και οι κόμβοι του. Η ισότητα ισχύει όταν το γράφημα είναι πλήρες, όπου κάθε κόμβος χρειάζεται το δικό του χρώμα, καθώς συνδέεται με κάθε άλλον.
2. Αν K_p είναι το πλήρες γράφημα p κόμβων και x είναι ένας δεσμός του, τότε X(K_p-x)=p-1.
3. Αν K_{m,n} είναι ένα οποιοδήποτε διγράφημα, τότε X(K_{m,n})=2.
4. Για τους άρτιους κύκλους είναι X(C_{2m}), αφού εναλλάξ μπορούμε να αλλάζουμε χρώμα από κόμβο σε κόμβο, ενώ για τους περιττούς κύκλους ισχύει ανάλογα X(C_{2m+1})=3.
5. Αν Τ είναι ένα δέντρο, τότε X(T)=2.
6. Εύκολα φαίνεται ότι X(G)=1\Leftrightarrow E(G)=\emptyset, ότι αρκεί δηλαδή ένα χρώμα για να χρωματίσουμε ένα γράφημα μόνον όταν αυτό είναι πλήρως ασυνδετικό.
7. Θεώρημα του Κένιχ: Ένα γράφημα έχει έναν 2-χρωματισμό αν και μόνον αν δεν περιέχει περιττούς κύκλους
8. Αν Δ(G) είναι ο μεγαλύτερος βαθμός που αντιστοιχεί σε κάποιον από τους κόμβους του G, δηλαδή
τότε ισχύει η εξής ανισότητα:
9. Θεώρημα των πέντε χρωμάτων (Heawood, 1890): Αν G είναι επίπεδο γράφημα, τότε αρκούν το πολύ πέντε χρώματα για να χρωματιστεί, δηλαδή X(G)\leq 5.
Απόδειξη: Ας πούμε ότι το G έχει p στο πλήθος κόμβους. Θα εφαρμόσουμε τη μέθοδο της (ισχυρής) μαθηματικής επαγωγής.
Αν p\leq 5, τότε το θεώρημα ισχύει με βάση την ιδιότητα 1. Υποθέτουμε λοιπόν ότι το θεώρημα ισχύει για p κόμβους.
Αν το G έχει p+1 κόμβους, με p\geq 5, αποδεικνύεται ότι θα περιέχει έναν οπωσδήποτε κόμβο v με βαθμό \delta(v)\leq 5. Από την επαγωγική υπόθεση έχουμε επίσης X(G-v)\leq 5, μια και το γράφημα G - v έχει p κόμβους.
Έστω τώρα ότι οι πέντε κόμβοι που συνδέονται με τον v θα χρωματιστούν με τα χρώματα a, b, c, d, e, μέσω χρωματισμού f. Αν κάποια από τα χρώματα αυτά συμπίπτουν ή αν ο βαθμός του v είναι μικρότερος από 5, τότε το θεώρημα ισχύει. Αν αντίθετα τα χρώματα είναι διακεκριμένα και δ(v) = 5, τότε έχουμε την περίπτωση του σχήματος 2. Αρκεί να δείξουμε ότι ο v μπορεί να χρωματιστεί με κάποιο από τα a, b, c, d, e. Θεωρούμε το υπογράφημα G_{a,c}\subset G-v, που ορίζεται ως εξής:
που αποτελείται δηλαδή από τους κόμβους που έχουν χρώμα a ή b. Αν οι v_1, v_3 ανήκουν σε διαφορετικούς παράγοντες του G_{a,b}, τότε αλλάζουμε τα χρώματα στον παράγοντα του v_1 και θέτουμε f(v) = a, χρωματίζουμε δηλαδή τον v με a. (Θα μπορούσαμε αντί για αυτό να αλλάξουμε χρώματα στον παράγοντα που βρίσκεται ο v_3 και να χρωματίζαμε τον v με b.) Αν οι v_1, v_3 ανήκουν στον ίδιο παράγοντα, τότε θα υπάρχει ένα μονοπάτι στο G_{a,b} από τον έναν στον άλλο, δηλαδή ένα μονοπάτι στο G που είναι χρωματισμένο μόνο με a και c και που δεν περιέχει τις v_2, v_4, v_5. Ο κύκλος που σχηματίζει το μονοπάτι v_1\cdots v3 με το μονοπάτι v_3\cdots v_1, θα περικυκλώνει είτε τoν κόμβο v_2 είτε τους κόμβους v_4, v_5, μια και το G είναι επίπεδο γράφημα. Όπως και να έχει, οι v_2, v_4 θα ανήκουν σε διαφορετικούς παράγοντες του υπογραφήματος G_{b,d} (ορίζεται όπως το G_{a,b}), οπότε, όμοια με προηγούμενα, αλλάζοντας τα χρώματα είτε στον παράγοντα του v_2 είτε στου v_4 χρωματίζουμε ανάλογα τον v με b ή d. Αποδείξαμε δηλαδή σε κάθε περίπτωση, ότι το θεώρημα ισχύει και για p + 1 κόμβους και η επαγωγή ολοκληρώθηκε.
10. Θεώρημα των τεσσάρων χρωμάτων (Appel & Haken, 1976): Αν G είναι επίπεδο γράφημα τότε αρκούν το πολύ τέσσερα χρώματα για να χρωματιστεί, δηλαδή X(G)\leq 4.

Αλγόριθμοι χρωματισμού

Οι αλγόριθμοι χρωματισμού αποσκοπούν στο να προσδιορίσουν το χρωματικό αριθμό ενός δοσμένου γραφήματος. Οι επόμενοι δύο αλγόριθμοι βασίζονται στην τεχνική branch & bound, σε απαρίθμηση δηλαδή περιπτώσεων υπό περιορισμούς.