Χρωματισμός ακμών
From Wikipedia, the free encyclopedia
Στη Θεωρία γράφων ο χρωματισμός ακμών ενός γραφήματος είναι η τοποθέτηση "χρωμάτων" στα άκρα του γραφήματος, έτσι ώστε να μην υπάρχουν δύο γειτονικές ακμές με το ίδιο χρώμα. Για παράδειγμα, η εικόνα στα δεξιά είναι ο χρωματισμός ακμών ενός γραφήματος με κόκκινο, μπλε και πράσινο χρώμα. Ο χρωματισμός ακμών είναι ένας από τους ποικίλους τρόπους χρωματισμού γραφημάτων. Το πρόβλημα χρωματισμού ακμών διερευνά αν είναι εφικτό να χρωματίσουμε τις ακμές ενός δοθέντος γραφήματος χρησιμοποιώντας μέχρι κ διαφορετικά χρώματα, όπου κ μια δεδομένη τιμή, ή με όσο το δυνατόν λιγότερα χρώματα. Ο ελάχιστος αριθμός χρωμάτων για τις ακμές ενός δοθέντος γραφήματος ονομάζεται χρωματικός δείκτης του γραφήματος. Για παράδειγμα, οι ακμές του γραφήματος της εικόνας μπορούν να χρωματιστούν με τρία χρώματα αλλά όχι με δύο,οπότε το εμφανιζόμενο γράφημα έχει χρωματικό δείκτη ίσο με τρία.
Σύμφωνα με το θεώρημα του Vizing, ο απαιτούμενος αριθμός χρωμάτων για το χρωματισμό ενός απλού γραφήματος είναι σε μέγιστο βαθμό είτε Δ ή Δ+1. Σε κάποια γραφήματα, όπως στα διμερή ή στα επίπεδα γραφήματα υψηλού βαθμού,ο αριθμός των χρωμάτων είναι πάντα Δ , και για τα πολλαπλά γραφήματα ο αριθμός των χρωμάτων μπορεί να είναι ως και 3Δ/2. Υπάρχουν πολυωνυμικοί αλγόριθμοι για το βέλτιστο χρωματισμό διμερών γραφημάτων και το χρωματισμό απλών μη διμερών γραφημάτων οι οποίοι χρησιμοποιούν μέχρι και Δ+1 χρώματα. Ωστόσο, το γενικό πρόβλημα ανεύρεσης του βέλτιστου χρωματισμού ακμών είναι το NP-complete και ακόμα και οι ταχύτεροι γνωστοί αλγόριθμοι χρειάζονται πολύ χρόνο για την αντιμετώπισή του. Έχουν μελετηθεί πολλές παραλλαγές του προβλήματος χρωματισμού ακμών, στις οποίες οι αναθέσεις χρωμάτων στα άκρα/ακμές πρέπει να πληρούν όρους/συνθήκες μη γειτνίασης (στις οποίες δεν μπορούν δύο κοντινές ακμές να έχουν το ίδιο χρώμα). Ο χρωματισμός ακμών έχει εφαρμογή σε προβλήματα προγραμματισμού και στην εκχώρηση συχνοτήτων για δίκτυα οπτικών ινών.