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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

Αν G είναι ένα γράφημα και C ένα σύνολο χρωμάτων, λέμε ότι η απεικόνιση f:V(G)\rightarrow C είναι χρωματισμός του G όταν

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

δηλαδή όταν αντιστοιχεί χρώματα στους κόμβους του G έτσι ώστε κάθε δύο συνδεμένοι κόμβοι να έχουν διαφορετικό χρώμα. Αν το C έχει n διακεκριμένα στοιχεία και ο χρωματισμός f είναι επί, τότε ονομάζεται n-χρωματισμός. Κάθε χρωματισμός διαμερίζει το V(G) σε κλάσεις κόμβων οι οποίοι έχουν κοινό χρώμα. Οι κλάσεις αυτές ονομάζονται χρωματικές κλάσεις.

Χρωματικός αριθμός[Επεξεργασία | επεξεργασία κώδικα]

Σχήμα 1

Για δοσμένο γράφημα 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-χρωματισμό αν και μόνον αν δεν περιέχει περιττούς κύκλους

X(G)=2\Leftrightarrow\forall m(C_{2m+1}\not\subseteq G)

8. Αν Δ(G) είναι ο μεγαλύτερος βαθμός που αντιστοιχεί σε κάποιον από τους κόμβους του G, δηλαδή

\Delta(G)=\max_{u_i\in V(G)}\delta(u_i)

τότε ισχύει η εξής ανισότητα:

X(G)\leq 1+\Delta(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 κόμβους.

Σχήμα 2

Έστω τώρα ότι οι πέντε κόμβοι που συνδέονται με τον v θα χρωματιστούν με τα χρώματα a, b, c, d, e, μέσω χρωματισμού f. Αν κάποια από τα χρώματα αυτά συμπίπτουν ή αν ο βαθμός του v είναι μικρότερος από 5, τότε το θεώρημα ισχύει. Αν αντίθετα τα χρώματα είναι διακεκριμένα και δ(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 κόμβους και η επαγωγή ολοκληρώθηκε.

10. Θεώρημα των τεσσάρων χρωμάτων (Appel & Haken, 1976): Αν G είναι επίπεδο γράφημα τότε αρκούν το πολύ τέσσερα χρώματα για να χρωματιστεί, δηλαδή X(G)\leq 4.

Αλγόριθμοι χρωματισμού[Επεξεργασία | επεξεργασία κώδικα]

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

Αλγόριθμος ανεξάρτητων συνόλων κορυφών[Επεξεργασία | επεξεργασία κώδικα]

Καλούμε ανεξάρτητο σύνολο κόμβων ενός γραφήματος G κάθε υποσύνολο του V(G) που έχει πλήρως ασυνδετικό φέρον γράφημα (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(G), τότε X(G) = s.

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

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

Αλγόριθμος του Χριστοφίδη[Επεξεργασία | επεξεργασία κώδικα]

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

  1. Διατάσουμε τους κόμβους του γραφήματος σε φθίνουσα σειρά βαθμών, x_1,\ldots,x_q.
  2. Θέτουμε f(x_1)=1
  3. Ελέγχουμε τον x_m, όταν ήδη έχουν δοθεί κ χρώματα. Αν δεν συνδέεται άμεσα με ήδη ελεγγμένους κόμβους και x_n, με n < m, είναι ο αρχύτερος από αυτούς, τότε θέτουμε f(x_m)=f(x_n). Αλλιώς θέτουμε f(x_m)=\kappa+1.

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]