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

Στην θεωρία γράφων, για έναν γράφο ${\displaystyle G=(V,E)}$ και ένα σύνολο χρωμάτων ${\displaystyle C}$, λέμε ότι η συνάρτηση ${\displaystyle f:V\rightarrow C}$ είναι χρωματισμός του ${\displaystyle G}$ όταν^[1][2]

${\displaystyle \forall (u,v)\in V.~f(u)\not =f(v)}$,

Χρωματισμός γράφου με χρώματα ${\displaystyle C=\{{\color {red}{\rm {K}}},{\color {blue}{\rm {M}}},{\color {green}{\rm {\Pi }}}\}}$, που αντιστοιχεί στο ${\displaystyle f=\{(1,{\color {red}{\rm {K}}}),(2,{\color {blue}{\rm {M}}}),(3,{\color {green}{\rm {\Pi }}}),(4,{\color {green}{\rm {\Pi }}}),(5,{\color {blue}{\rm {M}}})\}.}$ Παρατηρήστε ότι δεν υπάρχουν δύο γειτονικοί κόμβοι με το ίδιο χρώμα.

δηλαδή όταν θέτει χρώματα στους κόμβους του ${\displaystyle G}$ έτσι ώστε κάθε δύο συνδεμένοι κόμβοι να έχουν διαφορετικό χρώμα.

Αν το ${\displaystyle C}$ έχει ${\displaystyle k}$ διακεκριμένα στοιχεία και ο χρωματισμός ${\displaystyle f}$ είναι επί, τότε ονομάζεται ${\displaystyle k}$-χρωματισμός. Κάθε χρωματισμός διαμερίζει το ${\displaystyle V}$ σε κλάσεις κόμβων οι οποίοι έχουν κοινό χρώμα. Οι κλάσεις αυτές ονομάζονται χρωματικές κλάσεις.

Παραδείγματα δύο χρωματισμών και ενός μη έγκυρου χρωματισμού για τον ίδιο γράφο.

3-χρωματισμός γράφου

4-χρωματισμός γράφου

Μη-έγκυρος χρωματισμός γράφου

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

Ο γράφος ${\displaystyle G=(\{1,2\},\{(1,2)\})}$ δεν μπορεί να χρωματιστεί με ένα χρώμα.

Για έναν δοσμένο γράφο ${\displaystyle G=(V,E)}$ και δοσμένα χρώματα ${\displaystyle C}$ δεν υπάρχει πάντα απεικόνιση ${\displaystyle f}$ που να είναι χρωματισμός του ${\displaystyle G}$. Συγκεκριμένα η ύπαρξη χρωματισμού εξαρτάται από το πλήθος των στοιχείων (πληθάριθμος) του C. Για παράδειγμα, για τον γράφο ${\displaystyle G}$ του σχήματος που αποτελείται από μόνο μία ακμή, και έχοντας μόνο ένα διαθέσιμο χρώμα, ${\displaystyle C=\{{\color {red}{\rm {K}}}\}}$, δεν μπορούμε να χρωματίσουμε τους δύο κόμβους διαφορετικά, καθώς χρειαζόμαστε τουλάχιστον ένα ακόμη χρώμα.

Ο ελάχιστος πληθάριθμος ${\displaystyle k}$ του συνόλου ${\displaystyle C}$, για τον οποίο υπάρχει ${\displaystyle k}$-χρωματισμός του ${\displaystyle G}$ ονομάζεται χρωματικός αριθμός του ${\displaystyle G}$ και συμβολίζεται με ${\displaystyle \chi (G)}$, και ο γράφος λέγεται ${\displaystyle k}$-χρωματικός.

Ιδιότητες

Μερικές από τις ιδιότητες που ικανοποιεί ο χρωματικός αριθμός είναι οι παρακάτω:

1. Για κάθε γράφο ${\displaystyle G}$ με ${\displaystyle n}$ κόμβους, έχουμε ότι ${\displaystyle \chi (G)\leq n}$, καθώς μπορούμε να αντιστοιχίσουμε κάθε κόμβο σε διαφορετικό χρώμα.
   Σημείωση: Η ισότητα ισχύει για τον πλήρη γράφο ${\displaystyle K_{n}}$, όπου κάθε κόμβος χρειάζεται το δικό του χρώμα, καθώς συνδέεται με κάθε άλλον.
2. Για κάθε πλήρη γράφο ${\displaystyle K_{n}}$ με ${\displaystyle n}$ κόμβους και ${\displaystyle e}$ μία οποιαδήποτε ακμή του, ισχύει ότι ${\displaystyle \chi (K_{n}-e)=n-1}$.
3. Για κάθε διμερή γράφο ${\displaystyle K_{m,n}}$, ισχύει ότι ${\displaystyle \chi (K_{m,n})=2}$.
   Σημείωση: Για κάθε δέντρο ${\displaystyle T}$, ισχύει ότι ${\displaystyle \chi (T)=2}$.
4. Για κάθε κύκλο με άρτιο αριθμό κόμβων είναι ${\displaystyle \chi (C_{2m})}$, αφού εναλλάξ μπορούμε να αλλάζουμε χρώμα από κόμβο σε κόμβο, ενώ για τους περιττούς κύκλους ισχύει ανάλογα ${\displaystyle \chi (C_{2m+1})=3}$.
   

   

   Χρωματισμός κύκλων με 5 και 6 κόμβους αντίστοιχα.
5. Εύκολα φαίνεται ότι

   ${\displaystyle \chi (G)=1\Leftrightarrow E(G)=\emptyset }$,

   δηλαδή ότι ένα χρώμα αρκεί για να χρωματίσουμε έναν γράφο αν και μόνο αν αυτό είναι πλήρως ασυνδετικός.
6. Θεώρημα του Κένιχ: Ένας γράφος έχει έναν 2-χρωματισμό αν και μόνον αν δεν περιέχει περιττούς κύκλους

   ${\displaystyle \chi (G)=2\Leftrightarrow \forall m.~C_{2m+1}\not \subseteq G}$.

7. Για κάθε γράφο ${\displaystyle G}$ με ${\displaystyle \Delta (G)}$ να είναι ο μεγαλύτερος βαθμός που αντιστοιχεί σε κάποιον από τους κόμβους του ${\displaystyle G}$, δηλαδή

   ${\displaystyle \Delta (G)=\max _{u_{i}\in V}\delta (u_{i})}$,

   ισχύει ότι

   ${\displaystyle \chi (G)\leq 1+\Delta (G)}$.

8. Θεώρημα του Brooks:^[3] Για κάθε συννεκτικό γράφο που δεν είναι ούτε πλήρης ούτε περιττός κύκλος, ισχύει ότι

   ${\displaystyle \chi (G)\leq \Delta (G)}$.

9. Κάθε γράφος ${\displaystyle G}$ με ${\displaystyle m}$ ακμές ικανοποιεί

   ${\displaystyle \chi (G)\leq {\frac {1}{2}}+{\sqrt {2m+{\frac {1}{4}}}}}$.

   Απόδειξη

   Για κάθε ένα από τα ${\textstyle {\binom {\chi (G)}{2}}}$ διαφορετικά ζεύγη χρωμάτων πρέπει να υπάρχει μία ακμή μεταξύ τους, διαφορετικά θα μπορούσαμε να αντικαταστήσουμε τα δύο χρώματα με ένα. Επομένως, ${\displaystyle m\geq {\binom {\chi (G)}{2}}={\frac {1}{2}}\cdot \chi (G)\cdot (\chi (G)-1).}$ Λύνοντας το τριώνυμο, λαμβάνουμε την ζητούμενη ανισότητα.

10. Θεώρημα των πέντε χρωμάτων:^[4] Για κάθε επίπεδο γράφο ${\displaystyle G}$ αρκούν το πολύ πέντε χρώματα για να χρωματιστεί, δηλαδή ${\displaystyle \chi (G)\leq 5}$.

    Απόδειξη

    Έστω ότι ο ${\displaystyle G}$ έχει ${\displaystyle n}$ κόμβους. Θα εφαρμόσουμε τη μέθοδο της (ισχυρής) μαθηματικής επαγωγής. Αν ${\displaystyle n\leq 5}$, τότε το θεώρημα ισχύει από την ιδιότητα 1. Υποθέτουμε λοιπόν ότι το θεώρημα ισχύει για ${\displaystyle n}$ κόμβους. Αν ο ${\displaystyle G}$ έχει ${\displaystyle n+1}$ κόμβους, με ${\displaystyle n\geq 5}$, αποδεικνύεται ότι θα περιέχει οπωσδήποτε έναν κόμβο ${\displaystyle v}$ με βαθμό ${\displaystyle \delta (v)\leq 5}$. Από την επαγωγική υπόθεση έχουμε επίσης ${\displaystyle X(G-v)\leq 5}$, μια και ο γράφος ${\displaystyle G-v}$ έχει ${\displaystyle n}$ κόμβους. Έστω τώρα ότι οι πέντε κόμβοι που συνδέονται με τον ${\displaystyle v}$ θα χρωματιστούν με τα χρώματα ${\displaystyle a,b,c,d,e}$, μέσω χρωματισμού ${\displaystyle f}$. Αν κάποια από τα χρώματα αυτά συμπίπτουν ή αν ο βαθμός του ${\displaystyle v}$ είναι μικρότερος από 5, τότε το θεώρημα ισχύει. Αν αντίθετα τα χρώματα είναι διακεκριμένα και ${\displaystyle \delta (v)=5}$, τότε έχουμε την περίπτωση του σχήματος 2. Αρκεί να δείξουμε ότι ο ${\displaystyle v}$ μπορεί να χρωματιστεί με κάποιο από τα ${\displaystyle a,b,c,d,e}$. Θεωρούμε τον υπογράφο ${\displaystyle G_{a,c}\subset G-v}$, που ορίζεται ως εξής: ${\displaystyle G_{a,c}=\{u\in V(G-v):f(u)=a\ {\dot {\eta }}\ f(u)=c\}}$, δηλαδή που αποτελείται από τους κόμβους που έχουν χρώμα ${\displaystyle a}$ ή ${\displaystyle b}$. Αν οι ${\displaystyle v_{1}}$, ${\displaystyle v_{3}}$ ανήκουν σε διαφορετικούς παράγοντες του ${\displaystyle G_{a,b}}$, τότε αλλάζουμε τα χρώματα στον παράγοντα του ${\displaystyle v_{1}}$ και θέτουμε f(v) = a, χρωματίζουμε δηλαδή τον v με a. (Θα μπορούσαμε αντί για αυτό να αλλάξουμε χρώματα στον παράγοντα που βρίσκεται ο ${\displaystyle v_{3}}$ και να χρωματίζαμε τον v με b.) Αν οι ${\displaystyle v_{1}}$, ${\displaystyle v_{3}}$ ανήκουν στον ίδιο παράγοντα, τότε θα υπάρχει ένα μονοπάτι στο ${\displaystyle G_{a,b}}$ από τον έναν στον άλλο, δηλαδή ένα μονοπάτι στο G που είναι χρωματισμένο μόνο με a και c και που δεν περιέχει τις ${\displaystyle v_{2}}$, ${\displaystyle v_{4}}$, ${\displaystyle v_{5}}$. Ο κύκλος που σχηματίζει το μονοπάτι ${\displaystyle v_{1}\cdots v3}$ με το μονοπάτι ${\displaystyle v_{3}\cdots v_{1}}$, θα περικυκλώνει είτε τoν κόμβο ${\displaystyle v_{2}}$ είτε τους κόμβους ${\displaystyle v_{4}}$, ${\displaystyle v_{5}}$, μιας και ο ${\displaystyle G}$ είναι επίπεδος γράφος. Όπως και να έχει, οι ${\displaystyle v_{2}}$, ${\displaystyle v_{4}}$ θα ανήκουν σε διαφορετικούς παράγοντες του υπογράφου ${\displaystyle G_{b,d}}$ (ορίζεται όπως το ${\displaystyle G_{a,b}}$), οπότε, όμοια με προηγούμενα, αλλάζοντας τα χρώματα είτε στον παράγοντα του ${\displaystyle v_{2}}$ είτε στου ${\displaystyle v_{4}}$ χρωματίζουμε ανάλογα τον v με b ή d. Αποδείξαμε δηλαδή σε κάθε περίπτωση, ότι το θεώρημα ισχύει και για p + 1 κόμβους και η επαγωγή ολοκληρώθηκε.

11. Θεώρημα των τεσσάρων χρωμάτων:^[5] Για κάθε επίπεδο γράφο ${\displaystyle G}$ αρκούν το πολύ τέσσερα χρώματα για να χρωματιστεί, δηλαδή ${\displaystyle \chi (G)\leq 4}$.
12. Κάθε επίπεδος γράφος ${\displaystyle G}$ που δεν περιέχει ένα τρίγωνο έχει ${\displaystyle \chi (G)\leq 3}$.^[6]

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

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

Αλγόριθμος ανεξάρτητων συνόλων κορυφών

Καλούμε ανεξάρτητο σύνολο κόμβων ενός γράφου ${\displaystyle G=(V,E)}$ κάθε υποσύνολο του ${\displaystyle V}$ που έχει πλήρως ασυνδετικό φέρον γράφημα (spanning graph). Κάθε τέτοιο σύνολο εκπροσωπεί και μία χρωματική κλάση. Αν ${\displaystyle U_{1},\ldots ,U_{r}}$ είναι ανεξάρτητα σύνολα κόμβων τέτοια ώστε ${\displaystyle \forall i\not =i'.~U_{i}\not \subseteq U_{i'}}$, και υπάρχει ελάχιστος s το πολύ ίσος με τον r, για τον οποίο ${\textstyle \bigcup _{j=1}^{r}U_{i_{j}}=V}$, τότε ${\displaystyle \chi (G)=s}$.

Συγκεκριμένα, ο αλγόριθμος εκτελείται σε δύο φάσεις:

1. Εύρεση όλων των ανεξάρτητων συνόλων κόμβων που πληρούν τα παραπάνω.
2. Εύρεση του μικρότερου μήκους ένωσης που αποδίδει το ${\displaystyle V}$.

Αλγόριθμος του Χριστοφίδη

Ο αλγόριθμος συνίσταται στα εξής βήματα:

1. Διατάσουμε τους κόμβους του γράφου σε φθίνουσα σειρά βαθμών, ${\displaystyle x_{1},\ldots ,x_{n}}$.
2. Θέτουμε ${\displaystyle f(x_{1})=1}$.
3. Ελέγχουμε τον ${\displaystyle x_{i}}$, όταν ήδη έχουν δοθεί ${\displaystyle k}$ χρώματα. Αν δεν συνδέεται άμεσα με ήδη ελεγμένους κόμβους και ${\displaystyle x_{j}}$, με ${\displaystyle j<i}$, είναι ο αρχύτερος από αυτούς, τότε θέτουμε ${\displaystyle f(x_{i})=f(x_{j})}$. Διαφορετικά, θέτουμε ${\displaystyle f(x_{i})=k+1}$.

Δείτε επίσης

• Θεωρία γράφων

Παραπομπές

1. Νικολόπουλος, Σταύρος· Γεωργιάδης, Λουκάς· Παληός, Λεωνίδας (2015). Αλγοριθμική θεωρία γραφημάτων (PDF). Αθήνα: Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. σελίδες 245–271. ISBN 978-960-603-365-0.
2. Diestel, Reinhard (2005). Graph theory (3η έκδοση). Berlin Heidelberg: Springer. σελίδες 111-138. ISBN 9783540261834.
3. Brooks, R. L. (Απριλίου 1941). «On colouring the nodes of a network». Mathematical Proceedings of the Cambridge Philosophical Society 37 (2): 194–197. doi:doi:10.1017/S030500410002168X.
4. Heawood, P. J. (1890). «Map-colour theorem». The Quarterly Journal of Pure and Applied Mathematics (24): 332–338.
5. K. Appel; W. Haken (1976). «Every planar map is four colorable». Bull. Amer. Math. Soc. 82 (5): 711-712. https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society-new-series/volume-82/issue-5/Every-planar-map-is-four-colorable/bams/1183538218.full.
6. Grötzsch, Herbert (1959). «Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel». Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe 8: 109–120.

   MR 0116320

   .