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

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

\forall (u,v)\in V.~f(u)\not =f(v)

,

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

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

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

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

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

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

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

Ο γράφος

G=(\{1,2\},\{(1,2)\})

δεν μπορεί να χρωματιστεί με ένα χρώμα.

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

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

Ιδιότητες

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

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

Χρωματισμός κύκλων με 5 και 6 κόμβους αντίστοιχα.
Εύκολα φαίνεται ότι
$\chi (G)=1\Leftrightarrow E(G)=\emptyset$ ,
δηλαδή ότι ένα χρώμα αρκεί για να χρωματίσουμε έναν γράφο αν και μόνο αν αυτό είναι πλήρως ασυνδετικός.
Θεώρημα του Κένιχ: Ένας γράφος έχει έναν 2-χρωματισμό αν και μόνον αν δεν περιέχει περιττούς κύκλους
$\chi (G)=2\Leftrightarrow \forall m.~C_{2m+1}\not \subseteq G$ .
Για κάθε γράφο $G$ με $\Delta (G)$ να είναι ο μεγαλύτερος βαθμός που αντιστοιχεί σε κάποιον από τους κόμβους του $G$ , δηλαδή
$\Delta (G)=\max _{u_{i}\in V}\delta (u_{i})$ ,
ισχύει ότι
$\chi (G)\leq 1+\Delta (G)$ .
Θεώρημα του Brooks:^[3] Για κάθε συννεκτικό γράφο που δεν είναι ούτε πλήρης ούτε περιττός κύκλος, ισχύει ότι
$\chi (G)\leq \Delta (G)$ .

Κάθε γράφος

G

με

m

ακμές ικανοποιεί

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

.

Απόδειξη

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

m\geq {\binom {\chi (G)}{2}}={\frac {1}{2}}\cdot \chi (G)\cdot (\chi (G)-1).

Λύνοντας το τριώνυμο, λαμβάνουμε την ζητούμενη ανισότητα.

Θεώρημα των πέντε χρωμάτων:^[4] Για κάθε επίπεδο γράφο

G

αρκούν το πολύ πέντε χρώματα για να χρωματιστεί, δηλαδή

\chi (G)\leq 5

.

Απόδειξη

Έστω ότι ο $G$ έχει $n$ κόμβους. Θα εφαρμόσουμε τη μέθοδο της (ισχυρής) μαθηματικής επαγωγής.

Αν $n\leq 5$ , τότε το θεώρημα ισχύει από την ιδιότητα 1. Υποθέτουμε λοιπόν ότι το θεώρημα ισχύει για $n$ κόμβους.

Αν ο $G$ έχει $n+1$ κόμβους, με $n\geq 5$ , αποδεικνύεται ότι θα περιέχει οπωσδήποτε έναν κόμβο $v$ με βαθμό $\delta (v)\leq 5$ . Από την επαγωγική υπόθεση έχουμε επίσης $X(G-v)\leq 5$ , μια και ο γράφος $G-v$ έχει $n$ κόμβους.

Έστω τώρα ότι οι πέντε κόμβοι που συνδέονται με τον $v$ θα χρωματιστούν με τα χρώματα $a,b,c,d,e$ , μέσω χρωματισμού $f$ . Αν κάποια από τα χρώματα αυτά συμπίπτουν ή αν ο βαθμός του $v$ είναι μικρότερος από 5, τότε το θεώρημα ισχύει. Αν αντίθετα τα χρώματα είναι διακεκριμένα και $\delta (v)=5$ , τότε έχουμε την περίπτωση του σχήματος 2. Αρκεί να δείξουμε ότι ο $v$ μπορεί να χρωματιστεί με κάποιο από τα $a,b,c,d,e$ . Θεωρούμε τον υπογράφο $G_{a,c}\subset G-v$ , που ορίζεται ως εξής:

G_{a,c}=\{u\in V(G-v):f(u)=a\ {\dot {\eta }}\ f(u)=c\}

,

δηλαδή που αποτελείται από τους κόμβους που έχουν χρώμα $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 κόμβους και η επαγωγή ολοκληρώθηκε.

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

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

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

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

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

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

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

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

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

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

Δείτε επίσης

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

Παραπομπές

↑ Νικολόπουλος, Σταύρος· Γεωργιάδης, Λουκάς· Παληός, Λεωνίδας (2015). Αλγοριθμική θεωρία γραφημάτων (PDF). Αθήνα: Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. σελίδες 245–271. ISBN 978-960-603-365-0.
↑ Diestel, Reinhard (2005). Graph theory (3η έκδοση). Berlin Heidelberg: Springer. σελίδες 111-138. ISBN 9783540261834.
↑ 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.
↑ Heawood, P. J. (1890). «Map-colour theorem». The Quarterly Journal of Pure and Applied Mathematics (24): 332–338.
↑ 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.
↑ 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
.

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

[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
.

[1]

[2]

[3]

[4]

[5]

[6]