Χρωματισμός ακμών

Χρωματισμός ακμών με 3 χρώματα του Desargues Graph.

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

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

Παραδείγματα

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

Γεωμετρική κατασκευή χρωματισμού ακμών με 7 χρώματα ενός κανονικού γραφήματος Πρότυπο:Math. Κάθε μία από τις χρωματικές κλάσεις περιέχει μια ακμή η οποία ξεκινά από το κέντρο του πολυγώνου και καταλήγει σε μια κορυφή του,και 3 επιπλέον ακμές κάθετες σε αυτήν.

Ένα πλήρες γράφημα Πρότυπο:Mvar με Πρότυπο:Mvar μπορεί να έχει τις ακμές του χρωματισμένες με Πρότυπο:Math χρώματα όταν το Πρότυπο:Mvar είναι ζυγός αριθμός, αυτή είναι η ειδική περίπτωση του θεωρήματος του Baranyai. Ο Πρότυπο:Harvtxt παρείχε την ακόλουθη την γεωμετρική κατασκευή χρωμάτων στην περίπτωση αυτή: τοποθέτησε Πρότυπο:Mvar σημεία στις κορυφές και το κέντρο ενός πολυγώνου Πρότυπο:Math ακμών. Για κάθε χρωματική κλάση, συμπεριέλαβε τις ακμές με το ένα άκρο στο κέντρο του πολυγώνου και το άλλο σε μια από τις κορυφές του, και επίσης όλες τις κάθετες ακμές που συνδέουν ζεύγη κορυφών του πολυγώνου. Ωστόσο,όταν το Πρότυπο:Mvar είναι περιττός αριθμός, χρειάζονται Πρότυπο:Mvar χρώματα, όπου κάθε χρώμα μπορεί να χρησιμοποιηθεί μόνο για Πρότυπο:Math κορυφές δηλαδή για το Πρότυπο:Math του συνόλου.

Πολλοί συγγραφείς έχουν μελετήσει το χρωματισμό ακμών για γραφήματα περιττών ακμών ως εξής: στα Πρότυπο:Mvar-κανονικά γραφήματα οι κορυφές αντιπροσωπεύουν ομάδες από Πρότυπο:Math παίκτες που επιλέγονται από ένα σύνολο Πρότυπο:Mvar παικτών. Στην περίπτωση αυτή οι ακμές αντιπροσωπεύουν πιθανές αντιστοιχίσεις αυτών των ομάδων (με έναν παίκτη να μένει εκτός σαν να "επιβλέπει" τον αγώνα). Η περίπτωση όπου το Πρότυπο:Math gείναι γνωστή ως το γράφημα Petersen. Όπως εξηγεί ο Πρότυπο:Harvtxt στο πρόβλημα (για Πρότυπο:Math), οι παίκτες αναζητούν την οργάνωση αυτών των αντιστοιχίσεων έτσι ώστε κάθε παίκτης να παίζει τα 6 παιχνίδια του σε διαφορετικές μέρες της εβδομάδας, με τις Κυριακές να είναι αργίες για όλες τις ομάδες. Δηλαδή, διατυπώνοντας το μαθηματικά, αναζητούν το χρωματισμό 6 ακμών του κανονικού περιττού γραφήματος Πρότυπο:Math. Όταν το Πρότυπο:Mvar είναι 3, 4, ή 8, ο χρωματισμός ακμών του Πρότυπο:Math χρειάζεται Πρότυπο:Mathχρώματα, ενώ όταν είναι 5, 6 ή 7 χρειάζονται μόνο Πρότυπο:Mvar χρώματα.

Ορισμοί

Όπως και ο χρωματισμόs κορυφών, ο χρωματισμός ακμών ενός γραφήματος,όταν αναφέρεται χωρίς καμία διευκρίνηση,θεωρείται πάντα ότι είναι ο ορθός δηλαδή ότι δεν υπάρχουν γειτονικές ακμές με το ίδιο χρώμα. Εδώ,δύο ακμές λέγονται γειτονικές όταν έχουν μια κοινή κορυφή.Ο χρωματισμός ακμών ενός γραφήματος Πρότυπο:Mvar μπορεί επίσης να θεωρηθεί ισοδύναμος με το χρωματισμό κορυφών του γραμμικού γραφήματος Πρότυπο:Math, δηλαδή αυτού που διαθέτει μια κορυφή για κάθε άκρο του G και ένα άκρο για κάθε ζευγάρι γειτονικών κορυφών του Πρότυπο:Mvar.

Ο σωστός χρωματισμός ακμών με Πρότυπο:Mvar διαφορετικά χρώματα ονομάζεται Πρότυπο:Mvar-χρωματισμός ακμών. Ένα γράφημα στο οποίο μπορούμε να τοποθετήσουμε το σωστό αριθμό k χρωμάτων ονομάζεται Πρότυπο:Mvar-χρωματιζόμενο γράφημα. Ο ελάχιστος αριθμός χρωμάτων που απαιτείται για τον ορθό χρωματισμό ενός γραφήματος Πρότυπο:Mvar λέγεται χρωματικός αριθμός και συμβολίζεται Πρότυπο:Math. Ο χρωματισμός αριθμός συμβολίζεται πολλές φορές χρησιμοποιώντας δείκτη ωσ εξής Πρότυπο:Math και εδώ ο δείκτης 1 αντιστοιχεί σε ακμές μίας διάστασης. Ένα γράφημα είναι k-χρωματιζόμενο αν ο χρωματικός του δείκτης είναι ακριβώς Πρότυπο:Mvar. Ο χρωματικός δείκτης δεν πρέπει να συγχέεται με τον χρωματικό αριθμό Πρότυπο:Math ή Πρότυπο:Math, που είναι ο ελάχιστος αριθμός απαιτούμενων χρωμάτων για τον ορθό χρωματισμό κορυφών του Πρότυπο:Mvar.

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

Συσχέτιση με το ταίριασμα

Αυτό το κανονικό επίπεδο γράφημα έχει 16 κορυφές και 24 ακμές, αλλά μόνο 7 ακμές σε κάθε τέλειο ταίριασμα. Γι'αυτό απαιτούνται μόνο 4 χρώματα για οποιασδήποτε μορφής χρωματισμό του.

Ένα ταίριασμα(matching) σε ένα γράφημα Πρότυπο:Mvar είναι ένα σύνολο ακμών,με την ιδιότητα ότι κάθε κόμβος εμφανίζεται το πολύ σε μια ακμή του. Ένα τέλειο ταίριασμα είναι αυτό στο οποίο κάθε κόμβος εμφανίζεται σε μία μόνο ακμή και ένα ανώτατου ταίριασμα(maximum matching) είναι εκείνο που περιέχει όσο το δυνατόν περισσότερες ακμές.Δηλαδή, ένας σωστός χρωματισμός ακμών είναι το ίδιο πράγμα με τη διαμέριση του γραφήματος σε ασυνεχή ταιριάσματα.

Αν το μέγεθος ενός ανώτατου ταιριάσματος σε ένα δοθέν γράφημα είναι μικρό,τότε θα χρειαστούν πολλά ταιριάσματα ώσπου να καλυφθούν όλα τα άκρα του γραφήματος.Ειδικότερα, με βάση αυτή τη λογική το γράφημα έχει Πρότυπο:Mvar ακμές συνολικά,και αν το πολύ Πρότυπο:Math από αυτά ανήκουν στο ανώτατο ταίριασμα,τότε για κάθε χρωματισμό ακμών του γραφήματος πρέπει να χρησιμοποιηθούν τουλάχιστον Πρότυπο:Math διαφορετικά χρώματα.Για παράδειγμα,το επίπεδο γράφημα 16-κορυφών που φαίνεται στην εικόνα έχει Πρότυπο:Math ακμές.Σε αυτό το γράφημα,δεν υπάρχει τέλειο ταίριασμα; αν η κορυφή του κέντρου αποτελεί κόμβο στο ταίριασμα,οι υπόλοιπες κορυφές που δεν μετέχουν στο ταίριασμα μπορούν μπορούν να ομαδοποιηθούν σε τρια διαφορετικά σύνολα με τέσσερις,πέντε και πέντε κορυφές και τα υποσύνολα με μονό αριθμό κορυφών δεν μπορούν να σχηματίσουν τέλειο ταίριασμα. Ωστόσο,στο γράφημα υπάρχει ανώτατο ταίριασμα με 7 ακμές,έτσι ισχύει Πρότυπο:Math. Ως εκ τούτου, ο αριθμός των χρωμάτων που απαιτούνται για το χρωματισμό των ακμών είναι τουλάχιστον 24/7, και δεδομένου ότι ο αριθμός των χρωμάτων θα πρέπει να είναι ακέραιος,είναι τουλάχιστον τέσσερα. Για ένα κανονικό γράφημα βαθμού Πρότυπο:Mvar στο οποίο δεν υπάρχει τέλειο ταίριασμα,αυτό το κατώτερο όριο μπορεί να χρησιμοποιηθεί για να δείξει ότι απαιτούνται τουλάχιστον Πρότυπο:Math χρώματα.Ειδικότερα, αυτό είναι αληθές για ένα κανονικό γράφημα με περιττό αριθμό κορυφών (όπως στα odd complete graphs ). Σ'αυτά τα γραφήματα,σύμφωνα με το handshaking lemma,το Πρότυπο:Mvar πρέπει να είναι ζυγός αριθμός. Ωστόσο,η ανισότητα Πρότυπο:Math δεν ορίζει πλήρως το χρωματικό δείκτη για κάθε κανονικό γράφημα,διότι υπάρχουν κανονικά γραφήματα στα οποία υπάρχει τέλειο ταίριασμα αλλά δεν έχουν k χρωματισμένες ακμές.Για παράδειγμα,το γράφημα Petersen είναι κανονικό,με Πρότυπο:Math και Πρότυπο:Math ακμές στο τέλειο ταίρασμα αλλά δεν έχει χρωματισμό ακμών με 3 χρώματα.

Συσχέτιση με το βαθμό

Θεώρημα του Vizing

Ο χρωματικός αριθμός ενός γραφήματος Πρότυπο:Mvar είναι πολύ στενά συνδεδεμένος με τον μέγιστο βαθμό Δ(G) , τον μεγαλύτερο αριθμό των άκρων σε οποιοδήποτε μεμονωμένη κορυφή του Πρότυπο:Mvar . Σαφώς, Πρότυπο:Math, αν για Δ διαφορετικές ακμές που καταλήγουν στην ίδια κορυφή ν, όλες αυτές οι ακμές να αποδίδονται με διαφορετικά χρώματα η μία από την άλλη, και αυτό μπορεί να συμβεί μόνο αν υπάρχουν τουλάχιστον Πρότυπο:Math διαθέσιμα χρώματα.Σύμφωνα με το θεώρημα του Vizing(που πήρε το όνομά του από τον Vadim G. Vizing ο οποίος το διατύπωσε το 1964) αυτό το όριο χρωμάτων είναι πολύ περιορισμένο: δηλαδή για κάθε γράφημα ο χρωματικός δείκτης των ακμών είναι είτε Πρότυπο:Math είτε Πρότυπο:Math.Όταν ισχύει Πρότυπο:Math, το G λέγεται γράφημα τάξης 1, ενώ αλλιώς γράφημα τάξης 2.

Κάθε διμερές γράφημα είναι τάξης 1 και σχεδόν όλα τα τυχαία γραφήματα είναι επίσης τάξης 1. . Ωστόσο, η εξακρίβωση για το αν ένα αυθαίρετο γράφημα είναι τάξης 1 πραγματοποιείται με το NP-complete .

Ο Πρότυπο:Harvtxt απέδειξε ότι τα επίπεδα γραφήματα με μέγιστο βαθμό από 8 και πάνω είναι τάξης 1 και εικάζοταν ότι το ίδιο ισχύει και για τα επίπεδα γραφήματα με μέγιστο βαθμό 6 ή 7.Παρόλα αυτά,υπάρχουν επίπεδα γραφήματα με μέγιστο βαθμό που κυμαίνεται ανάμεσα στο 2 και το 5, τα οποία είναι γραφήματα τάξης 2. Η εικασία έκτοτε έχει αποδειχθεί για γραφήματα με μέγιστο βαθμό επτά. Τα μη συνεκτικά επίπεδα κυβικά γραφήματα είναι όλα τάξης 1 και αυτό αποτελεί μια ισοδύναμη έκφραση του θεωρήματος των τεσσάρων χρωμάτων.

Κανονικά γραφήματα

Η 1-παραγοντοποίηση ενός k-κανονικού γραφήματος, δηλαδή ο διαμελισμός των ακμών του γραφήματος σε τέλεια ταιριάσματα, είναι το ίδιο με το χρωματισμό k-ακμών του γραφήματος. Αυτό συμβαίνει γιατί, ένα κανονικό γράφημα έχει μια 1-παραγοντοποίηση αν και μόνο εάν είναι πρώτης τάξης. Μία ειδική περίπτωση είναι ο χρωματισμός τριών ακμών ενός κύβου (3-κανονικό) γραφήματος και ονομάζεται Tait χρωματισμός.

Δεν έχουν όλα τα κανονικά γραφήματα 1-παραγοντοποίηση, για παράδειγμα, το γράφημα του Patersen δεν έχει. Γενικότερα τα γραφήματα του Snark ορίζονται ως τα γραφήματα, όπως το γράφημα του Petersen,τα οποία δεν είναι πλήρη, 3-κανονικά , και δεύτερης τάξης.

Σύμφωνα με το θεώρημα του Πρότυπο:Harvtxt, κάθε διμερές κανονικό γράφημα έχει μία 1-παραγοντοποίηση. Το θεώρημα ορίστηκε νωρίτερα με τον όρο προβολικός σχηματισμός και αποδείχθηκε από τον Ernst Steinitz.

Πολυγραφήματα

'Ενα Shannon πολυγράφημα με 6 ακμές,πολλαπλότητα ακμών ίση με 3 στο οποίο απαιτούνται 9 χρώματα για το χρωματισμό ακμών του.

Στα πολυγραφήματα, στα οποία πολλαπλές παράλληλες ακμές τέμνονται στην ίδια κορυφή, έχουν διαπιστωθεί συμπεράσματα παρόμοια με αυτά του θεωρήματος Vizing, βέβαια με μικρότερη ισχύ, τα οποία συσχετίζουν το χρωματικό αριθμό των ακμών του Πρότυπο:Math, το μέγιστο δείκτη Πρότυπο:Math, και την πολλαπλότητα Πρότυπο:Math, η οποία είναι ο μέγιστος αριθμός ακμών σε κάθε δέσμη παράλληλων ακμών. Με ένα απλό παράδειγμα επαληθεύεται ότι το θεώρημα του Vizing δεν ισχύει για τα πολυγραφήματα: θεωρώντας ένα πολυγράφημα Shannon, δηλαδή ένα πολυγράφημα με 3 κορυφές και 3 δέσμες παράλληλων ακμών Πρότυπο:Math που συνδέουν τα 3 ζεύη κορυφών. Σε αυτό το παράδειγμα ισχύει, Πρότυπο:Math (κάθε κορυφή προσπίπτει μόνο σε δύο από τις τρεις δέσμες παράλληλων ακμών Πρότυπο:Math ) αλλά ο χρωματικός αριθμός των ακμών είναι Πρότυπο:Math (υπάρχουν τρεις Πρότυπο:Math ακμές συνολικά, και οι ακμές είναι παρακείμενες ανα δύο άρα πρέπει να ανατεθεί διαφορετικό χρώμα σε κάθε ακμή). Ένα συμπέρασμα του Shannon(1949), το οποίο ενέπνευσε τον Vizing, δείχνει ότι η δυσκολότερη περίπτωση για κάθε πολυγράφημα είναι: Πρότυπο:Math . Ακόμη για κάθε πολυγράφημα ισχύει, Πρότυπο:Math, κάτι το οποίο περιορίζει το θεώρημα του Vizing στην περίπτωση απλών γραφημάτων (για την οποία Πρότυπο:Math).

Αλγόριθμοι

Επειδή το πρόβλημα ελέγχου αν ένα γράφημα είναι πρώτης τάξης είναι NP-complete, δεν υπάρχει γνωστός polynomial time algorithm για τον χρωματισμό ακμών γραφήματος με τον βέλτιστο αριθμό χρωμάτων. Παρ'όλα αυτά, έχει αναπτυχθεί ένα πλήθος αλγορίθμων το οποίο επιτρέπει τουλάχιστον ένα από τα ακόλουθα κριτήρια:ισχύουν μόνο για ένα υποσύνολο γραφημάτων, ή δεν χρησιμοποιείται πάντα ο βέλτιστος αριθμός χρωμάτων, ή δεν μπορούν πάντα να επιλυθούν σε πολυωνιμικό χρόνο.

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

Στην περίπτωση των διμερών γραφημάτων ή των πολυγραφημάτων μεγίστου βαθμού Πρότυπο:Math, το βέλτιστο πλήθος χρωμάτων είναι ακριβώς Πρότυπο:Math. Οι Πρότυπο:Harvtxt απέδειξαν ότι ο βέλτιστος χρωματισμός ακμών αυτών των γραφημάτων υπολογίζεται από το όριο της σχεδόν γραμμικής σχέσης Πρότυπο:Math, όπουΠρότυπο:Mvar το πλήθος ακμών του γραφήματος, αλλά, πιο συγκεκριμένα οι αλγόριθμοι περιγράφηκαν από τους Πρότυπο:Harvtxt και Πρότυπο:Harvtxt. Ο αλγόριθμος του Πρότυπο:Harvtxtαρχίζει εισάγοντας το κανονικό γράφημα, χωρίς να υπολογίζει τον βαθμό του ή το μέγεθός του, συγχωνεύει τα ζεύγη των κορυφών που βρίσκονται στην ίδια πλευρά των διμερών γραφημάτων και μετά προσθέτει κάποιες επιπλέον κορυφές και ακμές. έπειτα, αν ο βαθμός είναι περιττός, ο Alon εφηύρε ένα μοναδικό τέλειο ταίριασμα στην σχεδόν γραμμική σχέση , του προσδιόρισε ένα χρώμα, και το απομάκρυνε απ το γράφημα, ώστε ο βαθμός να γίνει άρτιος. Τέλος, ο Alon εφάρμοσε την παρατήρηση Πρότυπο:Harvtxt, κατά την οποία συγκεντρώνει εναλλασσόμενα υποσύνολα ακμών σε ένα Euler tour του γραφήματος και τα χωρίζει σε δύο κανονικά υπογραφήματα , για να διασπάσει το πρόβλημα του χρωματισμού ακμών σε δύο μικρότερα υποπροβλήματα, και ο αλγόριθμός του λύνει τα δύο υποπροβλήματα αναδρομικά. Ο συνολικός χρόνος του αλγόριθμου αυτού είναι Πρότυπο:Math.

Για επίπεδες καμπύλες με μέγιστο βαθμό Πρότυπο:Math, ο βέλτιστος αριθμός χρωμάτων είναι και πάλι Πρότυπο:Math. Ισχυρότερη είναι η υπόθεση Πρότυπο:Math, και είναι δυνατό να βρεθεί ο βέλτιστος χρωματισμός ακμών σε γραμμικό χρόνο Πρότυπο:Harv.

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

Οι Πρότυπο:Harvtxt και Πρότυπο:Harvtxt περιγράφουν πολυωνυμικούς αλγόριθμους για το χρωματισμό οποιουδήποτε γραφήματος με Πρότυπο:Math χρώματα, συναντώντας το όριο απ το θεώρημα του Vizing.

Για τα πολυγραφήματα, οι Πρότυπο:Harvtxt παρουσιάζουν τον ακόλουθο αλγόριθμο, τον οποίο απέδωσαν στον Eli Upfal. Κάνει την εισαγωγή ενός πολυγραφήματος G Πρότυπο:Mvar Eulerian προσθέτοντας μία νέα κορυφή που συνδέεται με μία ακμή σε κάθε περιττού βαθμού κορυφή, βρίσκει ένα Euler tour, και επιλέγει έναν προσανατολισμό για αυτό. Σχηματίζει ένα διμερές γράφημα Πρότυπο:Mvar στο οποίο υπάρχουν δύο αντίγραφα κάθε κορυφής του Πρότυπο:Mvar, ένα σε κάθε πλευρά, με τη μία ακμή μίας κορυφής Πρότυπο:Mvar στην αριστερή πλευρά του γραφήματος και μίας κορυφής Πρότυπο:Mvar στην δεξιά πλευρά, κάθε φορά που ο προσανατολισμός είναι από το Πρότυπο:Mvar προς το Πρότυπο:Mvar στο Πρότυπο:Mvar. Έτσι εφαρμόζεται ο αλγόριθμος χρωματισμού ακμών για το διμερές γράφημα Πρότυπο:Mvar. Κάθε χρωματική τάξη του Πρότυπο:Mvar αντιστοιχεί σε μία συλλογή από ακμές του Πρότυπο:Mvar που σχηματίζουν ένα υπογράφημα βαθμού το πολύ δύο. Αυτό συμβαίνει επειδή, μία ξένη ένωση μονοπατιών και κύκλων, είναι δυνατόν κάθε κλάση χρωμάτων του Πρότυπο:Mvar να αντιστοιχεί σε τρεις τάξεις χρωμάτων του Πρότυπο:Mvar. Τη στιγμή που ο αλγόριθμος οριοθετείται από το χρώμα της ακμής ενός διμερούς γραφήματος Πρότυπο:Math χρησιμοποιούμε τον αλγόριθμο των Πρότυπο:Harvtxt. Το πλήθος των χρωμάτων που χρησιμοποιεί αυτός ο αλγόριθμος είναι το πολύ $3\lceil \frac{\mathrm{\Delta }}{2}\rceil$, που μοιάζει αλλά δεν είναι ίδιο με το όριο του Shannon $\lfloor \frac{3\mathrm{\Delta }}{2}\rfloor$. Μπορεί, επίσης, να μετατραπεί σε έναν παράλληλο αλγόριθμο με άμεσο τρόπο. Οι Karloff και Shmoys παρουσιάζουν ένα γραμμικό αλγόριθμο για τον χρωματισμό πολυγραφημάτων μεγίστου βαθμού τρία με τέσσερα χρώματα (συνδυασμός ορίων από τα θεωρήματα Shannon και Vizing) ο οποίος λειτουργεί με παρόμοιο τρόπο. Ο αλγόριθμός τους προσθέτει μία νέα κορυφή για να γίνει το γράφημα σαν του Euler, βρίσκει ένα Euler tour, και επιλέγει εναλλασσόμενα σύνολα από ακμές για να χωρίσει το γράφημα σε δύο υπογραφήματα μεγίστου βαθμού δύο. Τα μονοπάτια ακόμα και οι κύκλοι κάθε υπογραφήματος μπορούν να χρωματιστούν με δύο χρώματα ανά υπογράφημα. Μετά από αυτό, κάθε υπολοιπόμενος κύκλος περιέχει τουλάχιστον μία ακμή η οποία μπορεί να χρωματιστεί με ένα από τα δύο χρώματα του απέναντι υπογραφήματος. Μετακινώντας την ακμή από τον κύκλο αφήνει ένα μονοπάτι, το οποίο μπορεί να χρωματιστεί χρησιμοποιώντας τα δύο χρώματα του αντίστοιχου υπογραφήμτος.

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

Κάποιοι συγγραφείς έχουν φτιάξει εικασίες που συνεπάγονται πως ο κλασματικός χρωματικός δείκτης κάθε πολυγραφήματος (υπολογίζεται από πολυώνυμα χρησιμοποιώντας γραμμικό προγραμματισμό) έχει μία χρωματική ένδειξη. Αν αυτές οι εικασίες αληθεύου, είναι δυνατό να υπολογίσουμε ένα νούμερο που ποτέ δεν ξεπερνά αυτή τη χρωματική ένδειξη στην περίπτωση των πολυγραφημάτων, συνδυάζοντας ό,τι είναι γνωστό που το θεώρημα του Vizing για απλά γραφήματα. Αν αποδειχθεί αυτό σε γενικές γραμμές, αυτές οι εικασίες μπορούν να ισχύουν όταν οι χρωματικές ενδείξεις είναι τουλάχιστον $\mathrm{\Delta }+\sqrt{\mathrm{\Delta }/2}$, όπως συμβαίνει σε πολυγραφήματα με μεγάλη πολυπλοκότητα .

Ακριβείς αλγόριθμοι

Είναι απλό να εξετάσουμε πότε οι ακμές ενός γραφήματος μπορούν να χρωματιστούν με ένα ή δύο χρώματα, ούτως ώστε στην πρώτη μη τετριμμένη περίπτωση χρωματισμού ακμών να ελέγχεται πότε ένα γράφημα έχει 3 χρώματα για τις ακμές. Όπως έδειξε ο Πρότυπο:Harvtxt, γίνεται να ελέγξουμε πότε ένα γράφημα έχει 3 χρώματα για τις ακμές του σε χρόνο Πρότυπο:Math, χρησιμοποιώντας μόνο τον πολυωνυμικό χώρο. Παρόλο που το όριο αυτού του χρόνου είναι εκθετικό, είναι αισθητά πιο γρήγορο από την απλή αναζήτηση πάνω σε όλες τις πιθανες αναζητήσεις χρωμάτων για ακμές. Κάθε συνδεδεμένο 3-κανονικό γράφημα με Πρότυπο:Mvar κορυφές έχει Πρότυπο:Math 3-χρωματισμούς ακμών, οι οποίοι μπορούν να αναφερθούν σε χρόνο Πρότυπο:Math (πιο αργό από την εύρεση μοναδικού χρώματος). Όπως παρατήρησε ο Greg Kuperberg, το γράφημα ενός πρίσματος με Πρότυπο:Math-πλευρές έχει πολλά χρώματα, δείχνοντας ότι το όριο αυτό είναι αυστηρό.

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

Επειδή ο χρωματισμός ακμών είναι NP-complete ακόμα και για τρία χρώματα, είναι απίθανο να έχουμε σταθερή παράμετρο όταν παραμετρικοποιούμε με βάση το πλήθος των χρωμάτων. Ωστόσο, είναι λογικό να συμβαίνει για άλλες παραμέτρους. Ειδικότερα, οι Πρότυπο:Harvtxt απέδειξαν πως για γραφήματα πλάτους Πρότυπο:Mvar, ο βέλτιστος χρωματισμός ακμών υπολογίζεται ε χρόνο Πρότυπο:Math, ένα όριο με εκθετική εξάρτηση από το Πρότυπο:Mvar, αλλά γραμμική από το πλήθος Πρότυπο:Mvar των κορυφών του γραφήματος.

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

Πρόσθετες Ιδιότητες

Το uniquely 3-colorable γενικευμένο γράφημα Πέτερσεν Πρότυπο:Math. Μία από τις τρεις κατηγορίες χρωμάτων της φαίνεται από τις φωτεινές ακμές και οι άλλες δύο μπορεί να βρεθούν είτε με την περιστροφή των άκρων φωτός κατά 40° προς κάθε κατεύθυνση ή διαχωρίζοντας τον σκοτεινό Hamiltonian κύκλο σε εναλλασσόμενα άκρα.

Ένα γράφημα είναι uniquely Πρότυπο:Mvar-edge-colorable αν υπάρχει μόνο ένας τρόπος για να διαχωρίσει τις άκρες σε Πρότυπο:Mvar τάξεις χρώματος, αγνοώντας τους Πρότυπο:Math πιθανούς συνδυαμούς χρωμάτων. Για Πρότυπο:Math, τα μόνα uniquely Πρότυπο:Mvar-edge-colorable γραφήματα είναι γραμμές, κύκλοι και άστρα, αλλά για Πρότυπο:Math ενδέχεται να είναι uniquely Πρότυπο:Mvar-edge-colorable και άλλα γραφήματα. Κάθε uniquely 3-edge-colorable γράφημα διαθέτει ακριβώς τρεις Χαμιλτονιανούς κύκλους, που σχηματίζεται διαγράφοντας μία από τις τρεις κλάσεις χρώματος, αλλά υπάρχουν 3-κανονικά γραφήματα πυ διαθέτουν τρεις Χαμιλτονιανούς κύκλους και δεν είναι uniquely 3-colorable, όπως το γενικευμένο γράφημα Πέτερσεν Πρότυπο:Math για Πρότυπο:Math. Το μόνο γνωστό μη επίπεδο uniquely 3-colorable γράφημα είναι το γενικευμένο γράφημα Πέτερσεν Πρότυπο:Math και έχει αποδειχθεί ότι δεν υπάρχουν άλλα.

Οι Πρότυπο:Harvtxt ερεύνησαν τις μη αύξουσες ακολουθίες αριθμών Πρότυπο:Math με την ιδιότητα ότι υπάρχει ένας σωστός χρωματισμός ακμών ενός δεδομένου γραφήματος Πρότυπο:Mvar με Πρότυπο:Math ακμές για το πρώτο χρώμα, Πρότυπο:Math ακμές για το δεύτερο χρώμα, κλπ. Παρατήρησαν ότι, αν μία ακολουθία Πρότυπο:Mvar είναι δυνατόν να δημιουργηθεί έτσι, και είναι μεγαλύτερη σε λεξικογραφική σειρά από μια ακολουθία Πρότυπο:Mvar με τις ίδιες ιδιότητες, τότε και η Πρότυπο:Mvar στηρίζεται στον ίδιο τρόπο δημιουργίας. Γιατί, αν Πρότυπο:Math σε λεξικογραφική σειρά, τότε η Πρότυπο:Mvar μπορεί να μετατραπεί σε Πρότυπο:Mvar με μια σειρά βημάτων, κάθε ένα από τα οποία μειώνει έναν από τους αριθμούς Πρότυπο:Math κατά μία μονάδα και αυξάνει έναν επόμενο αριθμό Πρότυπο:Math με Πρότυπο:Math κατά μία μονάδα. Από την άποψη χρωματισμού ακμών, ξεκινώντας από ένα χρώμα που ενεργοποιεί την Πρότυπο:Mvar, καθένα από τα ίδια βήματα μπορούν να γίνουν με την εναλλαγή χρωμάτων Πρότυπο:Mvar και Πρότυπο:Mvar σε μια Kempe αλυσίδα, την μέγιστη διαδρομή των άκρων που εναλλάσσονται μεταξύ των δύο χρωμάτων. Ειδικότερα, κάθε γράφημα έχει έναν ισότιμο χρωματισμό ακμών, έναν χρωματισμό με το βέλτιστο αριθμό χρωμάτων στα οποίο κάθε δύο κλάσσεις διαφέρουν ως προς το μέγεθος το πολύ μία μονάδα.

Άλλοι τύποι για τον χρωματισμό ακμών

Ένας διαχωριμός του πλήρους διμερούς γραφήματος Κ_4,4 into three forests, showing that it has arboricity three.

Ο Thue number ενός γραφήματος είναι ο αριθμός των χρωμάτων που απαιτούνται σε έναν χρωματισμό ακμών, σε συνδυασμό με την ισχυρότερη απαίτηση ότι σε κάθε διαδρομή, ακόμη και μήκους, τα πρώτο και δεύτερο μισό της διαδρομής σχηματίζουν διαφορετικές αλληλουχίες των χρωμάτων. The arboricity ενός γραφήματος είναι ο ελάχιστος αριθμός των χρωμάτων που απαιτούνται έτσι ώστε τα άκρα του κάθε χρώματος να μην έχουν κύκλους (αντί για το προτότυπο πρόβλημα ακμής χρωματισμού, που δεν έχουμε παρακείμενα ζεύγη ακμών). Δηλαδή είναι ο ελάχιστος αριθμός Unlike the chromatic index, the arboricity of a graph may be computed in polynomial time.

Η Λίστα Χρωματικών Ακμών είναι ένα πρόβλημα στο οποίο δίνεται ένα γράφημα που η κάθε πλευρά του συνδέεται με μια λίστα χρωμάτων, και πρέπει να βρούμε έναν ορθό χρωματισμό κατά τον οποίο το χρώμα κάθε ακμής επιλέγεται από την λίστα χρωμάτων. Ο χρωματικός δείκτης λιστας, ενός γραφήματος Πρότυπο:Mvar είναι ο μικρότερος αριθμός Πρότυπο:Mvar με την ιδιότητα ότι, ανεξάρτητα από το πώς επιλέγει κάποιος την λίστα χρωμάτων για τις ακμές, εφ 'όσον κάθε ακμή έχει τουλάχιστον Πρότυπο:Mvar χρώματα στη λίστα της, ένας χρωματισμός είναι σίγουρο ότι θα πραγματοποιηθεί. Έτσι, ο χρωματικός δείκτης λίστας είναι πάντα τουλάχιστον τόσο μεγάλος όσο ο χρωματικός δείκτης. Η Dinitz εικασία για την ολοκλήρωση της μερικής Λατινικής πλατείας s μπορεί να αναδιατυπωθεί ως την δήλωση ότι λίστα χρωματικού αριθμού ακμών του πλήρες διμερές γράφημα Πρότυπο:Math ισούται άκρη χρωματικό αριθμό του, Πρότυπο:Mvar. Πρότυπο:Harvtxt επιλυθεί η εικασία αποδεικνύοντας, γενικότερα, ότι σε κάθε διμερές γράφημα το χρωματικό δείκτη και λίστα χρωματική δείκτη είναι ίσες. Η ισότητα μεταξύ του χρωματικού δείκτη και του χρωματικού δείκτη λίστας εικάζεται ότι ισχύει, και ακόμη πιο γενικά, για αυθαίρετα πολυγραφήματα χωρίς αυτοβρόχους.αυτή η υπόθεση παραμένει ανοιχτή.

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

Αν ένα 3-κανονικό γράφημα σε μια επιφάνεια είναι 3-πλευρα χρωματισμένο,το διπλό γράφημα του σχηματίζει έναν τριγωνισμός της επιφάνεια η οποία είναι επίσης χρωματισμένο άκρο (παρ' όλου που γενικά δεν) κατά τέτοιον τρόπο ώστε κάθε τρίγωνο να έχει ένα άκρο για κάθε χρώμα. Άλλοι χρωματισμοί και προσανατολισμοί για τους τριγωνισμούς, με άλλους τοπικούς περιορισμούς σχετικά με το πώς τα χρώματα είναι διατεταγμένα στις κορυφές ή επιφάνειες του τριγωνισμού, μπορεί να χρησιμοποιηθούν για να κωδικοποιήσουν διάφορους τύπους γεωμετρικού αντικειμένου. Για παράδειγμα, ορθογώνιες υποδιαιρέσεις (τμήματα μιας υποδιαίρεσης ενός ορθογώνιου σε μικρότερα ορθογώνια, με τρία ορθογώνια να συναντιούνται σε κάθε κορυφή) μπορεί να περιγραφεί συνδυαστικά με μια "κανονική σήμανση», ενός δύο-χρωματισμού των ακμών ενός τριγωνισμού διπλής υποδιαίρεσης, με τον περιορισμό ότι οι άκρες που ενώνονται σε μια κορυφή σχηματίζουν τέσσερις συνεχόμενες υπακολουθίες, μέσα στην κάθε μια τα χρώματα είναι τα ίδια. Αυτή η σήμανση είναι διπλή σε χρωματισμό της ίδιας της ορθογώνιας υποδιαίρεση στην οποία οι κάθετες ακμές έχουν ένα χρώμα και οι οριζόντιες ακμές έχουν το άλλο χρώμα. Παρόμοιοι περιορισμοί για την σειρά με την οποία μπορεί να εμφανιστούν οι χρωματιστές άκρες γύρω από μια κορυφή μπορεί επίσης να χρησιμοποιηθεί για να κωδικοποιήσει την ευθεία γραμμή embeddings του πλέγματος των επίπεδων γραφημάτων και τα τρισδιάστατα πολύεδρα με άξονες παράλληλες πλευρές. Για καθένα από αυτά τα τρία είδη των κανονικών σημάνσεων, το σύνολο των κανινικών σημάνσεων μιας σταθερής μορφής γραφήματος διανεμητικό lattice, στο οποίο μπορεί να χρησιμοποιηθεί για να κατηγοριοποιήσει γρήγορα όλες τις γεωμετρικές δομές που βασίζονται στην ίδια γραφική παράσταση (όπως όλοι οι άξονες παράλληλων πολύεδρων έχουν τον ίδιο σκελετό) ή να βρει δομές που ικανοποιούν επιπλέον περιορισμούς.

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

Το θεώρημα του Ραμσή αφορά το πρόβλημα Πρότυπο:Mvar-χρωματισμένων ακμών ενός μεγάλου πλήρους γραφήματος Πρότυπο:Math έτσι ώστε να αποφευχθεί η δημιουργία μονοχρωματικών πλήρων υποδιαιρέσεων Πρότυπο:Math κάποιου συγκεκριμένου μεγέθους Πρότυπο:Mvar. Σύμφωνα με αυτό το θεώρημα, υπάρχει ένας αριθμός Πρότυπο:Math τέτοιος ώστε, όταν Πρότυπο:Math, ένας τέτοιος χρωματισμός να μην είναι δυνατός. Για παράδειγμα, Πρότυπο:Math, δηλαδή όταν οι ακμές του γραφήματος Πρότυπο:Math είναι 2-χρωμες, πάντα θα υπάρχει ένα μονοχρωματικό τρίγωνο.

Εφαρμογές

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

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

Οι Πρότυπο:Harvtxt μελέτησαν το πρόβλημα της σύνδεσης του προγραμματισμού με τον χρόνο διαίρεσης πολλαπλής πρόσβασηςτων πρωτόκολλων επικοινωνιών δικτύου στους αισθητήρες δικτύου ως μια παραλλαγή του χρωματισμού ακμών. Σε αυτό το πρόβλημα, κάποιος πρέπει να επιλέξει τα χρονικά διαστήματα για τις άκρες ενός ασύρματου δικτύου επικοινωνιών, έτσι ώστε κάθε κόμβος του δικτύου να μπορεί να επικοινωνήσει με κάθε γειτονικό κόμβο χωρίς παρεμβολές. Χρησιμοποιώντας κάποιος τον ισχυρό χρωματισμό ακμών (και χρησιμοποιώντας δύο χρονικά διαστήματα για κάθε χρωματιστή ακμή, ένα για κάθε κατεύθυνση) θα έλυνε το πρόβλημα, αλλά θα χρησιμοποιούσε περισσότερα χρονικά διαστήματα απ' όσα χρειάζονται. Αντ 'αυτού, ζητούν ένα χρωματισμόν του κατευθυνόμενου γραφήματος που σχηματίζεται με διπλασιάζοντας κάθε μη-κατευθυνόμενο άκρο του δικτύου, με την ιδιότητα ότι κάθε κατευθυνόμενη ακμή Πρότυπο:Mvar έχει διαφορετικό χρώμα από τις άκρες που βγαίνουν από Πρότυπο:Mvar και από τους γείτονες της Πρότυπο:Mvar. Προτείνουν μια πειραματική λύση για το πρόβλημα αυτό που βασίζεται σε έναν κατανεμημένο αλγόριθμο για Πρότυπο:Math-άκρες χρωματισμένες, μαζί με μια φάση τελικής επεξεργασίας που αναδιοργανώνει τις ακμές που θα μπορούσαν να αλληλεπιδρούν μεταξύ τους.

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

Ανοικτά Προβλήματα

Οι Πρότυπο:Harvtxt δημιούργησαν μια λίστα από 23 ανοικτά προβλήματα που αφορούν τον χρωματισμό ακμών. Αυτά είναι:

• Η εικασία του Πρότυπο:Harvtxt ότι ο χρωματικός δείκτης και ο κλασματικός δείκτης περιλαμβάνονται το ένα μέσα στο άλλο, πράγμα το οποίο επιτρέπει στον χρωματικό δείκτη να προσεγγιστεί με ένα χρώμα σε πολυωνυμικό χρόνο.
• Πολλές υποθέσεις του Jakobsen και άλλων σχετικά με τη δομή του κύριου γραφήματος για τον χρωματισμό ακμών, γραφήματα κλάσης 2, έτσι ώστε κάθε υπόγραφος να έχει είτε τον μικρότερο μέγιστο βαθμό ή να είναι κλάσης 1. Ο Jakobsen αρχικά θεωρεί ότι όλα τα κύρια γραφήματα έχουν έναν μοναδικό αριθμό κορυφών, αλλά αυτό τελικά διαψεύστηκε. Αρκετές άλλες εικασίες που πλησιάζουν αυτή, ή που οριοθετούν τους αριθμούς των κορυφών των κύριων γραφημάτων και κύριων πολύγραφων, παραμένουν ανοικτές.
• Το πρόβλημα του Vizing της ταξινόμησης των ανώτατων βαθμών που είναι πιθανοί για την κλάση 2 των επίπεδων γραφημάτων.
• Οι εικασίες για το πλήρες υπόγραφο του AJW Hilton, δηλώνοντας ότι γραφήματα με βαθμό τουλάχιστον Πρότυπο:Math είναι είτε κλάσης 1 ή περιέχουν έναν υπόγραφο με τον ίδιο βαθμό Πρότυπο:Math με το αρχικό γράφημα, και με μοναδικό αριθμό Πρότυπο:Mvarτων κορυφών, έτσι ώστε ο αριθμός των ακμών στον υπόγραφο να είναι μεγαλύτερος από Πρότυπο:Math, και μια παρόμοια θεωρία των Herbert Grötzsch και Paul Seymour σχετικά με τα επίπεδα γραφήματα στη θέση των γραφημάτων υψηλού βαθμού.
• Μια θεωρία των Chetwynd και Hilton (ενδεχομένως να σχετίζεται με αυτήν του Gabriel Andrew Dirac) ότι τα τυπικά γραφήματα με ζυγό αριθμό Πρότυπο:Mvar των κορυφών και με βαθμό τουλάχιστον Πρότυπο:Math είναι κλάσης 1.
• Μια υπόθεση των Claude Berge και D. R. Fulkerson ότι ο 6-τυπικός πολύγραφος σχηματίζεται διπλασιάζοντας κάθε άκρη ενός bridgeless 3-τυπικού γραφήματος απλού μπορεί να έχει χρωματισμένες άκρες με έξι χρώματα.
• Μια εικασία των Fiorini και Wilson ότι κάθε τρίγωνο χωρίς επίπεδη γραφική παράσταση, εκτός από το νύχι Κ _1,3 , δεν είναι μοναδικά 3-edge-απατηλός.
• Μια τρέχουσα υπόθεση είναι ότι αν Πρότυπο:Math είναι ένας Πρότυπο:Math-τυπικός πολυγράφος επίπεδος, τότε το Πρότυπο:Math είναι -edge-απατηλός αν και μόνο αν Πρότυπο:Math είναι περίεργο Πρότυπο:Math άκρη συνδεδεμένη. Αυτή η εικασία μπορεί να θεωρηθεί ως μια γενίκευση της Τέσσερις χρώμα θεώρημα όταν Πρότυπο:Math = 3. Μαρία Τσουντνόφσκι, Katherine Edwards, και Paul Seymour απέδειξαν ότι ένα 8-τυπικό πολυγράφημα επίπεδο έχει 8 χρωματικές ακμές.

Πηγές

• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation. As cited by Πρότυπο:Harvtxt.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation. As cited by Πρότυπο:Harvtxt.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation. See also web site for this section of the book in the Stony Brook Algorithm Repository.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation. (In Russian.)
• Πρότυπο:Citation.
• Πρότυπο:Citation.