Χρήστης:ΑΚΟΥΑΡΟΝΕ ΕΛΙΖΑ/πρόχειρο
From Wikipedia, the free encyclopedia
Στην θεωρία γράφωνο χρωματισμός ακμών ενός γραφήματος είναι η τοποθέτηση "χρωμάτων" στα άκρα του γραφήματος έτσι ώστε να μην υπάρχουν δύο γειτονικές ακμές με το ίδιο χρώμα.Για παράδειγμα,η εικόνα στα δεξιά είναι ο χρωματισμός ακμών ενός γραφήματος με κόκκινο,μπλε και πράσινο χρώμα.Ο χρωματισμός ακμών είναι ένας από τους ποικίλους τρόπυς χρωματισμού γραφημάτων.Το πρόβλημα χρωματισμού ακμών διερευνά αν είναι εφικτό να χρωματίσουμε τις ακμές ενός δοθέντος γραφήματος χρησιμοποιώντας μέχρι κ διαφορετικά χρώματα,όπου κ μια δεδομένη τιμή,ή με όσο το δυνατόν λιγότερα χρώματα.Ο ελάχιστος αριθμός χρωμάτων για τις ακμές ενός δοθέντος γραφήματος ονομάζεται χρωματικός δείκτης του γραφήματος.Για παράδειγμα,οι αμκές του γραφήματος της εικόνας μπορούν να χρωματιστούν με τρία χρώματα αλλά όχι με δύο,οπότε το εμφανιζόμενο γράφημα έχει χρωματικό δείκτη ίσο με τρία.
By Vizing's theorem, the number of colors needed to edge color a simple graph is either its maximum degree Δ or Δ+1. For some graphs, such as bipartite graphs and high-degree planar graphs, the number of colors is always Δ, and for multigraphs, the number of colors may be as large as 3Δ/2. There are polynomial time algorithms that construct optimal colorings of bipartite graphs, and colorings of non-bipartite simple graphs that use at most Δ+1 colors; however, the general problem of finding an optimal edge coloring is NP-complete and the fastest known algorithms for it take exponential time. Many variations of the edge coloring problem, in which an assignments of colors to edges must satisfy other conditions than non-adjacency, have been studied. Edge colorings have applications in scheduling problems and in frequency assignment for fiber optic networks.