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

right|120px|thumb|Χρωματισμός γράφου με χρώματα <math>C = \{ {\color{red} \rm K }, {\color{blue} \rm M }, {\color{green} \rm \Pi } \}</math>, που αντιστοιχεί στο <math>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 }) \}.</math> Παρατηρήστε ότι δεν υπάρχουν δύο γειτονικοί κόμβοι με το ίδιο χρώμα.
Στην θεωρία γράφων, για έναν γράφο G = (V, E) και ένα σύνολο χρωμάτων C, λέμε ότι η συνάρτηση f:V \rightarrow C είναι **χρωματισμός** του G όταν
:\forall(u,v)\in V. ~ f(u)\not=f(v),
δηλαδή όταν θέτει χρώματα στους κόμβους του G έτσι ώστε κάθε δύο συνδεμένοι κόμβοι να έχουν διαφορετικό χρώμα. 

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

## Χρωματικός αριθμός
thumbnail|Ο γράφος <math>G = (\{ 1, 2 \}, \{ (1, 2) \} )</math> δεν μπορεί να χρωματιστεί με ένα χρώμα.|200px
Για έναν δοσμένο γράφο G = (V, E) και δοσμένα χρώματα C δεν υπάρχει πάντα απεικόνιση f που να είναι χρωματισμός του G. Συγκεκριμένα η ύπαρξη χρωματισμού εξαρτάται από το πλήθος των στοιχείων (πληθάριθμος) του *C*. Για παράδειγμα, για τον γράφο G του σχήματος που αποτελείται από μόνο μία ακμή, και έχοντας μόνο ένα διαθέσιμο χρώμα, C = \{ {\color{red} \rm K } \}, δεν μπορούμε να χρωματίσουμε τους δύο κόμβους διαφορετικά, καθώς χρειαζόμαστε τουλάχιστον ένα ακόμη χρώμα.

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

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

.

| **Θεώρημα των πέντε χρωμάτων**: Για κάθε επίπεδο γράφο G αρκούν το πολύ πέντε χρώματα για να χρωματιστεί, δηλαδή \chi(G)\leq 5.

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

## Αλγόριθμοι χρωματισμού
Οι **[[Αλγόριθμος|αλγόριθμοι]] χρωματισμού** αποσκοπούν να προσδιορίσουν το χρωματικό αριθμό ενός δοσμένου γράφου. Οι επόμενοι δύο αλγόριθμοι βασίζονται στην μέθοδο *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*, για τον οποίο \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 , είναι ο αρχύτερος από αυτούς, τότε θέτουμε f(x_i) = f(x_j). Διαφορετικά, θέτουμε f(x_i)=k+1.

## Δείτε επίσης
* Θεωρία γράφων

## Παραπομπές


Κατηγορία:Διακριτά μαθηματικά
Κατηγορία:Θεωρία γράφων