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

Αρχείο:Graph coloring 3 colors example with labels.svg

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

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

$\mathrm{\forall }(u,v)\in V.f(u)=f(v)$,

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

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

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

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

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

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

Ιδιότητες

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

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

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

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

Καλούμε ανεξάρτητο σύνολο κόμβων ενός γράφου $G=(V,E)$ κάθε υποσύνολο του $V$ που έχει πλήρως ασυνδετικό φέρον γράφημα (spanning graph). Κάθε τέτοιο σύνολο εκπροσωπεί και μία χρωματική κλάση. Αν $U_1,\dots ,U_r$ είναι ανεξάρτητα σύνολα κόμβων τέτοια ώστε $\mathrm{\forall }i=i^{\prime }.U_i\subseteq ̸U_{i^{\prime }}$, και υπάρχει ελάχιστος s το πολύ ίσος με τον r, για τον οποίο ${\bigcup }_{j=1}^r{U}_{i_j}=V$, τότε $\chi (G)=s$.

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

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

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

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

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

Δείτε επίσης

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