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

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

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

Χρωματικός αριθμός
Για έναν δοσμένο γράφο  και δοσμένα χρώματα  δεν υπάρχει πάντα απεικόνιση  που να είναι χρωματισμός του . Συγκεκριμένα η ύπαρξη χρωματισμού εξαρτάται από το πλήθος των στοιχείων (πληθάριθμος) του C. Για παράδειγμα, για τον γράφο  του σχήματος που αποτελείται από μόνο μία ακμή, και έχοντας μόνο ένα διαθέσιμο χρώμα, , δεν μπορούμε να χρωματίσουμε τους δύο κόμβους διαφορετικά, καθώς χρειαζόμαστε τουλάχιστον ένα ακόμη χρώμα.

Ο ελάχιστος πληθάριθμος  του συνόλου , για τον οποίο υπάρχει -χρωματισμός του  ονομάζεται χρωματικός αριθμός του  και συμβολίζεται με , και ο γράφος λέγεται -χρωματικός. 

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

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

Αλγόριθμος ανεξάρτητων συνόλων κορυφών
Καλούμε ανεξάρτητο σύνολο κόμβων ενός γράφου  κάθε υποσύνολο του  που έχει πλήρως ασυνδετικό φέρον γράφημα (spanning graph). Κάθε τέτοιο σύνολο εκπροσωπεί και μία χρωματική κλάση. Αν  είναι ανεξάρτητα σύνολα κόμβων τέτοια ώστε , και υπάρχει ελάχιστος s το πολύ ίσος με τον r, για τον οποίο , τότε .

Συγκεκριμένα, ο αλγόριθμος εκτελείται σε δύο φάσεις:
Εύρεση όλων των ανεξάρτητων συνόλων κόμβων που πληρούν τα παραπάνω.
Εύρεση του μικρότερου μήκους ένωσης που αποδίδει το .

Αλγόριθμος του Χριστοφίδη
Ο αλγόριθμος συνίσταται στα εξής βήματα:
Διατάσουμε τους κόμβους του γράφου σε φθίνουσα σειρά βαθμών, .
Θέτουμε .
Ελέγχουμε τον , όταν ήδη έχουν δοθεί  χρώματα. Αν δεν συνδέεται άμεσα με ήδη ελεγμένους κόμβους και , με , είναι ο αρχύτερος από αυτούς, τότε θέτουμε . Διαφορετικά, θέτουμε .

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

Παραπομπές

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