Χρωματισμός Γραφημάτων — Χρωματικός Αριθμός και Εφαρμογές

Ο χρωματισμός γραφημάτων συνήθως σημαίνει χρωματισμό κορυφών: αντιστοιχίζουμε ένα χρώμα σε κάθε κορυφή έτσι ώστε γειτονικές κορυφές να μην έχουν το ίδιο χρώμα. Ο μικρότερος αριθμός χρωμάτων που αρκεί λέγεται χρωματικός αριθμός και γράφεται $\chi(G)$.

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

Ορισμός του χρωματισμού γραφημάτων σε ένα λεπτό

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

Άρα αν $\chi(G)=3$, τότε ισχύουν ταυτόχρονα δύο πράγματα:

• υπάρχει σωστός χρωματισμός με $3$ χρώματα
• δεν υπάρχει σωστός χρωματισμός μόνο με $2$ χρώματα

Γι’ αυτό ο χρωματικός αριθμός είναι ελάχιστο, όχι απλώς ο αριθμός χρωμάτων που έτυχε να χρησιμοποιήσεις σε ένα σχέδιο.

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

Τι μετρά πραγματικά ο χρωματικός αριθμός

Τα ονόματα των χρωμάτων δεν έχουν σημασία. Μπορείς να χρησιμοποιήσεις κόκκινο, μπλε και πράσινο ή τις ετικέτες $1$, $2$ και $3$.

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

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

Λυμένο παράδειγμα: γιατί ένας κύκλος 5 κορυφών χρειάζεται 3 χρώματα

Θεώρησε το κυκλικό γράφημα $C_5$ με ακμές $AB, BC, CD, DE,$ και $EA$.

Δοκίμασε πρώτα $2$ χρώματα. Δώσε στην $A$ το χρώμα $1$ και στη $B$ το χρώμα $2$. Τότε ο χρωματισμός επιβάλλεται γύρω από τον κύκλο:

$$A=1,\quad B=2,\quad C=1,\quad D=2$$

Τώρα κοίτα την $E$. Είναι γειτονική και με τη $D$ και με την $A$, άρα δεν μπορεί να πάρει το χρώμα $2$ λόγω της $D$, και δεν μπορεί να πάρει το χρώμα $1$ λόγω της $A$.

Άρα τα $2$ χρώματα αποτυγχάνουν.

Όμως τα $3$ χρώματα λειτουργούν. Ένας σωστός χρωματισμός είναι ο εξής:

$$A=1,\quad B=2,\quad C=1,\quad D=2,\quad E=3$$

οπότε

$$\chi(C_5)=3$$

Αυτό το παράδειγμα αξίζει να το θυμάσαι, γιατί δείχνει ένα σημαντικό μοτίβο: για τα κυκλικά γραφήματα, ένας άρτιος κύκλος μπορεί να χρωματιστεί με $2$ χρώματα, ενώ ένας περιττός κύκλος χρειάζεται $3$.

Πώς να σκέφτεσαι τον χρωματισμό γραφημάτων σε μικρά γραφήματα

Δύο γρήγοροι έλεγχοι βοηθούν.

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

Δεύτερον, ψάξε για ένα κάτω φράγμα. Αν ένα γράφημα περιέχει τρίγωνο, τότε αυτές οι τρεις κορυφές είναι ανά δύο γειτονικές, άρα χρειάζονται ήδη $3$ διαφορετικά χρώματα. Αυτό δεν δίνει πάντα την ακριβή απάντηση, αλλά αποδεικνύει ότι ο χρωματικός αριθμός είναι τουλάχιστον $3$.

Συνηθισμένα λάθη σε προβλήματα χρωματισμού γραφημάτων

Ένα συνηθισμένο λάθος είναι να θεωρείς ότι δύο κορυφές είναι γειτονικές μόνο και μόνο επειδή είναι σχεδιασμένες κοντά η μία στην άλλη. Μόνο μια πραγματική ακμή δημιουργεί περιορισμό στον χρωματισμό.

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

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

Ένα τελευταίο λάθος είναι να αναφέρεις τον αριθμό χρωμάτων που έτυχε να χρησιμοποιήσεις αντί για τον ελάχιστο απαιτούμενο αριθμό. Το ότι χρησιμοποίησες $4$ χρώματα σε ένα γράφημα δεν αποδεικνύει ότι ο χρωματικός αριθμός είναι $4$.

Πού χρησιμοποιείται ο χρωματισμός γραφημάτων

Μια κλασική εφαρμογή είναι ο προγραμματισμός εξετάσεων. Υπόθεσε ότι κάθε κορυφή είναι μια εξέταση και μια ακμή σημαίνει ότι δύο εξετάσεις έχουν κοινούς φοιτητές και δεν μπορούν να τοποθετηθούν την ίδια ώρα. Τότε ένα χρώμα μπορεί να παριστάνει μία χρονική ζώνη.

Σε αυτό το μοντέλο, ο χρωματικός αριθμός σου λέει πόσες είναι οι λιγότερες δυνατές χρονικές ζώνες. Αν $\chi(G)=4$, τότε δεν υπάρχει έγκυρο πρόγραμμα μόνο με $3$ ζώνες.

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

Δοκίμασε ένα παρόμοιο πρόβλημα χρωματισμού γραφημάτων

Σχεδίασε ένα γράφημα με κορυφές $P,Q,R,S,T$ και ακμές $PQ, QR, RS, ST, TP,$ και $PR$.

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