cyanic-selkie/wikianc huggingface dataset:
Χρωματισμός ακμών
Παραδείγματα
), οι παίκτες αναζητούν την οργάνωση αυτών των αντιστοιχίσεων έτσι ώστε κάθε παίκτης να παίζει τα 6 παιχνίδια του σε διαφορετικές μέρες της εβδομάδας, με τις Κυριακές να είναι αργίες για όλες τις ομάδες. Δηλαδή, διατυπώνοντας το μαθηματικά, αναζητούν το χρωματισμό 6 ακμών του κανονικού περιττού γραφήματος
. Όταν το n είναι 3, 4, ή 8, ο χρωματισμός ακμών του
On
χρειάζεται
χρώματα, ενώ όταν είναι 5, 6 ή 7 χρειάζονται μόνο n χρώματα.
Ορισμοί
Όπως και ο χρωματισμόs κορυφών, ο χρωματισμός ακμών ενός γραφήματος,όταν αναφέρεται χωρίς καμία διευκρίνηση,θεωρείται πάντα ότι είναι ο ορθός δηλαδή ότι δεν υπάρχουν γειτονικές ακμές με το ίδιο χρώμα. Εδώ,δύο ακμές λέγονται γειτονικές όταν έχουν μια κοινή κορυφή.Ο χρωματισμός ακμών ενός γραφήματος G μπορεί επίσης να θεωρηθεί ισοδύναμος με το χρωματισμό κορυφών του γραμμικού γραφήματος
L(G)
, δηλαδή αυτού που διαθέτει μια κορυφή για κάθε άκρο του G και ένα άκρο για κάθε ζευγάρι γειτονικών κορυφών του G.
Ο σωστός χρωματισμός ακμών με k διαφορετικά χρώματα ονομάζεται  k-χρωματισμός ακμών. Ένα γράφημα στο οποίο μπορούμε να τοποθετήσουμε το σωστό αριθμό k χρωμάτων ονομάζεται k-χρωματιζόμενο γράφημα. Ο ελάχιστος αριθμός χρωμάτων που απαιτείται για τον ορθό χρωματισμό ενός γραφήματος G λέγεται χρωματικός αριθμός και συμβολίζεται
χ′(G)
. Ο χρωματισμός αριθμός συμβολίζεται πολλές φορές χρησιμοποιώντας δείκτη ωσ εξής
χ1(G)
και εδώ ο δείκτης 1 αντιστοιχεί σε ακμές μίας διάστασης. Ένα γράφημα είναι k-χρωματιζόμενο αν ο χρωματικός του δείκτης είναι ακριβώς k. Ο χρωματικός δείκτης δεν πρέπει να συγχέεται με τον χρωματικό αριθμό
χ(G)
ή
χ0(G)
, που είναι ο ελάχιστος αριθμός απαιτούμενων χρωμάτων για τον ορθό χρωματισμό κορυφών του G.
Εκτός αν αναφέρεται διαφορετικά όλα τα γραφήματα υποτίθεται ότι είναι απλά,σε αντίθεση με τα πολυγραφήματα στα οποία δύο ή περισσότερα άκρα ενδέχεται να συνδέουν το ίδιο ζευγάρι παραμέτρων και μπορεί να υπάρχουν βρόχοι γύρω από τα άκρα. Σε πολλά προβλήματα στο χρωματισμό ακμών,τα απλά γραφήματα συμπεριφέρονται διαφορετικά από τα πολυγραφήματα και χρειάζεται επιπλέον προσοχή στην επέκταση των θεωρημάτων χρωματισμού ακμών από τα απλά γραφήματα στα πολυγραφήματα.
Συσχέτιση με το ταίριασμα
Ένα ταίριασμα(matching) σε ένα γράφημα G είναι ένα σύνολο ακμών,με την ιδιότητα ότι κάθε κόμβος εμφανίζεται το πολύ σε μια ακμή του. Ένα τέλειο ταίριασμα είναι αυτό στο οποίο κάθε κόμβος εμφανίζεται σε μία μόνο ακμή και ένα ανώτατου ταίριασμα(maximum matching) είναι εκείνο που περιέχει όσο το δυνατόν περισσότερες ακμές.Δηλαδή, ένας σωστός χρωματισμός ακμών είναι το ίδιο πράγμα με τη διαμέριση του γραφήματος σε ασυνεχή ταιριάσματα.
Αν το μέγεθος ενός ανώτατου ταιριάσματος σε ένα δοθέν γράφημα είναι μικρό,τότε θα χρειαστούν πολλά ταιριάσματα ώσπου να καλυφθούν όλα τα άκρα του γραφήματος.Ειδικότερα, με βάση αυτή τη λογική το γράφημα έχει m ακμές συνολικά,και αν το πολύ
β
από αυτά ανήκουν στο ανώτατο ταίριασμα,τότε για κάθε χρωματισμό ακμών του γραφήματος πρέπει να χρησιμοποιηθούν τουλάχιστον
m/β
διαφορετικά χρώματα.Για παράδειγμα,το επίπεδο γράφημα 16-κορυφών που φαίνεται στην εικόνα έχει
m = 24
ακμές.Σε αυτό το γράφημα,δεν υπάρχει τέλειο ταίριασμα; αν η κορυφή του κέντρου αποτελεί κόμβο στο ταίριασμα,οι υπόλοιπες κορυφές που δεν μετέχουν στο ταίριασμα μπορούν μπορούν να ομαδοποιηθούν σε τρια διαφορετικά σύνολα με τέσσερις,πέντε και πέντε κορυφές και τα υποσύνολα με μονό αριθμό κορυφών δεν μπορούν να σχηματίσουν τέλειο ταίριασμα. Ωστόσο,στο γράφημα υπάρχει ανώτατο ταίριασμα με 7 ακμές,έτσι ισχύει
β = 7
. Ως εκ τούτου, ο αριθμός των χρωμάτων που απαιτούνται για το χρωματισμό των ακμών είναι τουλάχιστον 24/7, και δεδομένου ότι ο αριθμός των χρωμάτων θα πρέπει να είναι ακέραιος,είναι τουλάχιστον τέσσερα. Για ένα κανονικό γράφημα βαθμού k στο οποίο δεν υπάρχει τέλειο ταίριασμα,αυτό το κατώτερο όριο μπορεί να χρησιμοποιηθεί για να δείξει ότι απαιτούνται τουλάχιστον
k + 1
χρώματα.Ειδικότερα, αυτό είναι αληθές για ένα κανονικό γράφημα με περιττό αριθμό κορυφών (όπως στα odd complete graphs ). Σ'αυτά τα γραφήματα,σύμφωνα με το handshaking lemma,το  k πρέπει  να είναι ζυγός αριθμός. Ωστόσο,η ανισότητα
δεν ορίζει πλήρως το χρωματικό δείκτη για κάθε κανονικό γράφημα,διότι υπάρχουν κανονικά γραφήματα στα οποία υπάρχει τέλειο ταίριασμα αλλά δεν έχουν k χρωματισμένες ακμές.Για παράδειγμα,το γράφημα Petersen είναι κανονικό,με
m = 15
και
β = 5
ακμές στο τέλειο ταίρασμα αλλά δεν έχει χρωματισμό ακμών με 3 χρώματα.
Θεώρημα του Vizing
χ′(G) ≥ Δ(G)
Δ
διαθέσιμα χρώματα.Σύμφωνα με το θεώρημα του Vizing(που πήρε το όνομά του από τον Vadim G. Vizing ο οποίος το διατύπωσε το 1964) αυτό το όριο χρωμάτων είναι πολύ περιορισμένο: δηλαδή για κάθε γράφημα ο χρωματικός δείκτης των ακμών είναι είτε
Δ(G)
είτε
Δ(G) + 1
.Όταν ισχύει
χ′(G) = Δ(G)
, το G λέγεται γράφημα τάξης 1, ενώ αλλιώς γράφημα τάξης 2.
Κάθε διμερές γράφημα είναι τάξης 1 και σχεδόν όλα τα τυχαία γραφήματα είναι επίσης τάξης 1. . Ωστόσο, η εξακρίβωση για το αν ένα αυθαίρετο γράφημα είναι τάξης 1 πραγματοποιείται με το NP-complete.
Ο απέδειξε ότι  τα επίπεδα γραφήματα με μέγιστο βαθμό από 8 και πάνω είναι τάξης 1 και εικάζοταν ότι το ίδιο ισχύει και για τα επίπεδα γραφήματα με μέγιστο βαθμό 6 ή 7.Παρόλα αυτά,υπάρχουν επίπεδα γραφήματα με μέγιστο βαθμό που κυμαίνεται ανάμεσα στο 2 και το 5, τα οποία είναι γραφήματα τάξης 2. Η εικασία έκτοτε έχει αποδειχθεί για γραφήματα με μέγιστο βαθμό επτά. Τα μη συνεκτικά επίπεδα κυβικά γραφήματα είναι όλα τάξης 1 και αυτό αποτελεί μια ισοδύναμη έκφραση του θεωρήματος των τεσσάρων χρωμάτων.
Κανονικά γραφήματα
Η 1-παραγοντοποίηση ενός k-κανονικού γραφήματος, δηλαδή ο διαμελισμός των ακμών του γραφήματος σε τέλεια ταιριάσματα, είναι το ίδιο με το χρωματισμό k-ακμών του γραφήματος. Αυτό συμβαίνει γιατί, ένα κανονικό γράφημα έχει μια 1-παραγοντοποίηση αν και μόνο εάν είναι πρώτης τάξης. Μία ειδική περίπτωση είναι ο χρωματισμός τριών ακμών ενός κύβου (3-κανονικό) γραφήματος και ονομάζεται Tait χρωματισμός.
Δεν έχουν όλα τα κανονικά γραφήματα 1-παραγοντοποίηση, για παράδειγμα, το γράφημα του Patersen δεν έχει. Γενικότερα τα γραφήματα του Snark ορίζονται ως τα γραφήματα, όπως το γράφημα του Petersen,τα οποία δεν είναι πλήρη, 3-κανονικά, και δεύτερης τάξης.
Σύμφωνα με το θεώρημα του, κάθε διμερές κανονικό γράφημα έχει μία 1-παραγοντοποίηση. Το θεώρημα ορίστηκε νωρίτερα με τον όρο προβολικός σχηματισμός και αποδείχθηκε από τον Ernst Steinitz.
Πολυγραφήματα
Στα πολυγραφήματα, στα οποία πολλαπλές παράλληλες ακμές τέμνονται στην ίδια κορυφή, έχουν διαπιστωθεί συμπεράσματα παρόμοια με αυτά του θεωρήματος Vizing, βέβαια με μικρότερη ισχύ, τα οποία συσχετίζουν το χρωματικό αριθμό των ακμών του
χ′(G)
, το μέγιστο δείκτη
Δ(G)
, και την πολλαπλότητα
μ(G)
, η οποία είναι ο μέγιστος αριθμός ακμών σε κάθε δέσμη παράλληλων ακμών. Με ένα απλό παράδειγμα επαληθεύεται ότι το θεώρημα του Vizing δεν ισχύει για τα πολυγραφήματα: θεωρώντας ένα πολυγράφημα Shannon, δηλαδή ένα πολυγράφημα με 3 κορυφές και 3 δέσμες παράλληλων ακμών
που συνδέουν τα 3 ζεύη κορυφών. Σε αυτό το παράδειγμα ισχύει,
Δ(G) = 2μ(G)
(κάθε κορυφή προσπίπτει μόνο σε δύο από τις τρεις δέσμες παράλληλων ακμών
) αλλά ο χρωματικός αριθμός των ακμών είναι
3μ(G)
(υπάρχουν τρεις
ακμές συνολικά, και οι ακμές είναι παρακείμενες ανα δύο άρα πρέπει να ανατεθεί διαφορετικό χρώμα σε κάθε ακμή). Ένα συμπέρασμα του Shannon(1949), το οποίο ενέπνευσε τον Vizing, δείχνει ότι η δυσκολότερη περίπτωση για κάθε πολυγράφημα είναι:
χ′(G) ≤ (3/2)Δ(G)
. Ακόμη για κάθε πολυγράφημα ισχύει,
χ′(G) ≤ Δ(G) + μ(G)
, κάτι το οποίο περιορίζει το θεώρημα του Vizing στην περίπτωση απλών γραφημάτων (για την οποία
μ(G) = 1
).
Αλγόριθμοι
Επειδή το πρόβλημα ελέγχου αν ένα γράφημα είναι πρώτης τάξης είναι NP-complete, δεν υπάρχει γνωστός polynomial time algorithm για τον χρωματισμό ακμών γραφήματος με τον βέλτιστο αριθμό χρωμάτων. Παρ'όλα αυτά, έχει αναπτυχθεί ένα πλήθος αλγορίθμων το οποίο επιτρέπει τουλάχιστον ένα από τα ακόλουθα κριτήρια:ισχύουν μόνο για ένα υποσύνολο γραφημάτων, ή δεν χρησιμοποιείται πάντα ο βέλτιστος αριθμός χρωμάτων, ή δεν μπορούν πάντα να επιλυθούν σε πολυωνιμικό χρόνο.
Βέλτιστος χρωματισμός ειδικών γραφημάτων
, το βέλτιστο πλήθος χρωμάτων είναι ακριβώς
Δ
. Οι απέδειξαν ότι ο βέλτιστος χρωματισμός ακμών αυτών των γραφημάτων υπολογίζεται από το όριο της σχεδόν γραμμικής σχέσης
O(m log Δ)
, όπουm το πλήθος ακμών του γραφήματος, αλλά, πιο συγκεκριμένα οι αλγόριθμοι περιγράφηκαν από τους και. Ο αλγόριθμος του αρχίζει εισάγοντας το κανονικό γράφημα, χωρίς να υπολογίζει τον βαθμό του ή το μέγεθός του, συγχωνεύει τα ζεύγη των κορυφών που βρίσκονται στην ίδια πλευρά των διμερών γραφημάτων και μετά προσθέτει κάποιες επιπλέον κορυφές και ακμές. έπειτα, αν ο βαθμός είναι περιττός, ο Alon εφηύρε ένα μοναδικό τέλειο ταίριασμα στην σχεδόν γραμμική σχέση, του προσδιόρισε ένα χρώμα, και το απομάκρυνε απ το γράφημα, ώστε ο βαθμός να γίνει άρτιος. Τέλος, ο Alon εφάρμοσε την παρατήρηση , κατά την οποία συγκεντρώνει εναλλασσόμενα υποσύνολα ακμών σε ένα    Euler tour του γραφήματος και τα χωρίζει σε δύο κανονικά υπογραφήματα , για να διασπάσει το πρόβλημα του χρωματισμού ακμών σε δύο μικρότερα υποπροβλήματα, και ο αλγόριθμός του λύνει τα δύο υποπροβλήματα αναδρομικά. Ο συνολικός χρόνος του αλγόριθμου αυτού είναι
O(m log m)
.
Για επίπεδες καμπύλες με μέγιστο βαθμό
Δ ≥ 7
, ο βέλτιστος αριθμός χρωμάτων είναι και πάλι
. Ισχυρότερη είναι η υπόθεση
Δ ≥ 9
, και είναι δυνατό να βρεθεί ο βέλτιστος χρωματισμός ακμών σε γραμμικό χρόνο.
Αλγόριθμοι που χρησιμοποιούν μεγαλύτερο αριθμό χρωμάτων από τον βέλτιστο
Οι και  περιγράφουν πολυωνυμικούς αλγόριθμους για το χρωματισμό οποιουδήποτε γραφήματος με
Δ + 1
χρώματα, συναντώντας το όριο απ το θεώρημα του Vizing.
Για τα πολυγραφήματα, οι  παρουσιάζουν τον ακόλουθο αλγόριθμο, τον οποίο απέδωσαν στον Eli Upfal. Κάνει την εισαγωγή ενός πολυγραφήματος G G Eulerian προσθέτοντας μία νέα κορυφή που συνδέεται με μία ακμή σε κάθε περιττού βαθμού κορυφή, βρίσκει ένα Euler tour, και επιλέγει έναν προσανατολισμό για αυτό. Σχηματίζει ένα διμερές γράφημα H στο οποίο υπάρχουν δύο αντίγραφα κάθε κορυφής του G, ένα σε κάθε πλευρά, με τη μία ακμή μίας κορυφής  u στην αριστερή πλευρά του γραφήματος και μίας κορυφής v στην δεξιά πλευρά, κάθε φορά που ο προσανατολισμός είναι από το u προς το v στο G. Έτσι εφαρμόζεται ο αλγόριθμος χρωματισμού ακμών για το διμερές γράφημα H. Κάθε χρωματική τάξη του H αντιστοιχεί σε μία συλλογή από ακμές του G που σχηματίζουν ένα υπογράφημα βαθμού το πολύ δύο. Αυτό συμβαίνει επειδή, μία ξένη ένωση μονοπατιών και κύκλων, είναι δυνατόν κάθε κλάση χρωμάτων του H να αντιστοιχεί σε τρεις τάξεις χρωμάτων του  G. Τη στιγμή που ο αλγόριθμος οριοθετείται από το χρώμα της ακμής ενός διμερούς γραφήματος
O(m log Δ)
χρησιμοποιούμε τον αλγόριθμο των. Το πλήθος των χρωμάτων που χρησιμοποιεί αυτός ο αλγόριθμος είναι το πολύ, που μοιάζει αλλά δεν είναι ίδιο με το όριο του Shannon. Μπορεί, επίσης, να μετατραπεί σε έναν παράλληλο αλγόριθμο με άμεσο τρόπο. Οι Karloff και Shmoys παρουσιάζουν ένα γραμμικό αλγόριθμο για τον χρωματισμό πολυγραφημάτων μεγίστου βαθμού τρία με τέσσερα χρώματα (συνδυασμός ορίων από τα θεωρήματα Shannon και Vizing) ο οποίος λειτουργεί με παρόμοιο τρόπο. Ο αλγόριθμός τους προσθέτει μία νέα κορυφή για να γίνει το γράφημα σαν του Euler, βρίσκει ένα Euler tour, και επιλέγει εναλλασσόμενα σύνολα από ακμές για να χωρίσει το γράφημα σε δύο υπογραφήματα μεγίστου βαθμού δύο. Τα μονοπάτια ακόμα και οι κύκλοι κάθε υπογραφήματος μπορούν να χρωματιστούν με δύο χρώματα ανά υπογράφημα. Μετά από αυτό, κάθε υπολοιπόμενος κύκλος περιέχει τουλάχιστον μία ακμή η οποία μπορεί να χρωματιστεί με ένα από τα δύο χρώματα του απέναντι υπογραφήματος. Μετακινώντας την ακμή από τον κύκλο αφήνει ένα μονοπάτι, το οποίο μπορεί να χρωματιστεί χρησιμοποιώντας τα δύο χρώματα του αντίστοιχου υπογραφήμτος.
Ένας αλγόριθμος με πλεονεκτικό χρωματισμό, εξετάζει τις ακμές ενός γραφήματος ή πολυγραφήματος μία προς μία, εκχωρεί σε κάθε ακμή το πρώτο διαθέσιμο χρώμα και ίσως το πλήθος των χρωμάτων είναι
, δηλαδή σχεδόν το διπλάσιο του απαραίτητου. Ωστόσο, έχει το πλεονέκτημα ότι μπορεί να χρησιμοποιηθεί στους online αλγόριθμους, ελέγχοντας την είσοδο γραφημάτων που δεν είναι γνωστά εκ των προτέρων. Με αυτόν τον έλεγχο, ο ανταγωνιστικός δείκτης του είναι δύο και αυτός είναι ο βέλτιστος γιατί κανένας άλλος online αλγόριθμος δεν έχει καλύτερα αποτελέσματα. Παρ' όλα αυτά, αν οι ακμές επιλέγονται με τυχαία σειρά, και ο βαθμός του γραφήματος εισόδου είναι τουλάχιστον λογαριθμικός, τότε μπορούν να επιτευχθούν μικρότεροι ανταγωνιστικοί δείκτες.
Κάποιοι συγγραφείς έχουν φτιάξει εικασίες που συνεπάγονται πως ο κλασματικός χρωματικός δείκτης κάθε πολυγραφήματος (υπολογίζεται από πολυώνυμα χρησιμοποιώντας γραμμικό προγραμματισμό) έχει μία χρωματική ένδειξη. Αν αυτές οι εικασίες αληθεύου, είναι δυνατό να υπολογίσουμε ένα νούμερο που ποτέ δεν ξεπερνά αυτή τη χρωματική ένδειξη στην περίπτωση των πολυγραφημάτων, συνδυάζοντας ό,τι είναι γνωστό που το θεώρημα του Vizing για απλά γραφήματα. Αν αποδειχθεί αυτό σε γενικές γραμμές, αυτές οι εικασίες μπορούν να ισχύουν όταν οι χρωματικές ενδείξεις είναι τουλάχιστον, όπως συμβαίνει σε πολυγραφήματα με μεγάλη πολυπλοκότητα.
Ακριβείς αλγόριθμοι
O(1.344n)
, χρησιμοποιώντας μόνο τον πολυωνυμικό χώρο. Παρόλο που το όριο αυτού του χρόνου είναι εκθετικό, είναι αισθητά πιο γρήγορο από την απλή αναζήτηση πάνω σε όλες τις πιθανες αναζητήσεις χρωμάτων για ακμές. Κάθε συνδεδεμένο 3-κανονικό γράφημα με n κορυφές έχει
3-χρωματισμούς ακμών, οι οποίοι μπορούν να αναφερθούν σε χρόνο
O(2n/2)
(πιο αργό από την εύρεση μοναδικού χρώματος). Όπως παρατήρησε ο Greg Kuperberg, το γράφημα ενός πρίσματος με
Με τη εφαρμογή ακριβών αλγορίθμων για χρωματισμό κορυφών στο γράφημα γραμμής του γραφήματος εισαγωγής, είναι δυνατό να βελτιστοποιήσουμε τον χρωματισμό ακμών κάθε γραφήματος με m ακμές, ανεξάρτητα από τον αριθμό των χρωμάτων που απαιτούνται, σε χρόνο
2mmO(1)
και εκθετικό διάστημα, ή
O(2.2461m)
και μόνο πολυωνυμικό διάστημα.
Επειδή ο χρωματισμός ακμών είναι NP-complete ακόμα και για τρία χρώματα, είναι απίθανο να έχουμε σταθερή παράμετρο όταν παραμετρικοποιούμε με βάση το πλήθος των χρωμάτων. Ωστόσο, είναι λογικό να συμβαίνει για άλλες παραμέτρους. Ειδικότερα, οι  απέδειξαν πως για γραφήματα  πλάτους w, ο βέλτιστος χρωματισμός ακμών υπολογίζεται ε χρόνο
O(nw(6w)w(w + 1)/2)
, ένα όριο με εκθετική εξάρτηση από το w, αλλά γραμμική από το πλήθος n των κορυφών του γραφήματος.
Οι διατυπώνουν το πρόβλημα του χρωματισμού ακμών ως ένα ακέραιο πρόγραμμα και περιγράφουν την πρακτική τους χρησιμοποιώντας την λύση ενός ακέραιου προγραμματισμού στο χρώμα των ακμών αυτών. Ωστόσο, δεν παρουσιάζουν καμία ανάλυση πολυπλοκότητας του αλγορίθμου τους.
Πρόσθετες Ιδιότητες
Generalized Petersen 9 2 Hamiltonicity.svg
G(9,2)
k!
πιθανούς συνδυαμούς χρωμάτων. Για
, τα μόνα uniquely k-edge-colorable γραφήματα είναι γραμμές, κύκλοι και άστρα, αλλά για
k = 3
ενδέχεται να είναι uniquely k-edge-colorable και άλλα γραφήματα. Κάθε uniquely 3-edge-colorable γράφημα διαθέτει ακριβώς τρεις Χαμιλτονιανούς κύκλους, που σχηματίζεται διαγράφοντας μία από τις τρεις κλάσεις χρώματος, αλλά υπάρχουν 3-κανονικά γραφήματα πυ διαθέτουν τρεις Χαμιλτονιανούς κύκλους και δεν είναι uniquely 3-colorable, όπως το γενικευμένο γράφημα Πέτερσεν
G(6n + 3, 2)
για
n ≥ 2
. Το μόνο γνωστό μη επίπεδο uniquely 3-colorable γράφημα είναι το γενικευμένο γράφημα Πέτερσεν
και έχει αποδειχθεί ότι δεν υπάρχουν άλλα.
Οι ερεύνησαν τις μη αύξουσες ακολουθίες αριθμών
με την ιδιότητα ότι υπάρχει ένας σωστός χρωματισμός ακμών ενός δεδομένου γραφήματος G με
m1
ακμές για το πρώτο χρώμα,
m2
ακμές για το δεύτερο χρώμα, κλπ. Παρατήρησαν ότι, αν μία ακολουθία P είναι δυνατόν να δημιουργηθεί έτσι, και είναι μεγαλύτερη σε λεξικογραφική σειρά από μια ακολουθία Q με τις ίδιες ιδιότητες, τότε και η Q στηρίζεται στον ίδιο τρόπο δημιουργίας. Γιατί, αν
P > Q
σε λεξικογραφική σειρά, τότε η P μπορεί να μετατραπεί σε Q με μια σειρά βημάτων, κάθε ένα από τα οποία μειώνει έναν από τους αριθμούς
mi
κατά μία μονάδα και αυξάνει έναν επόμενο αριθμό
mj
με
i < j
κατά μία μονάδα. Από την άποψη χρωματισμού ακμών, ξεκινώντας από ένα χρώμα που ενεργοποιεί την P, καθένα από τα ίδια βήματα μπορούν να γίνουν με την εναλλαγή χρωμάτων i και j σε μια Kempe αλυσίδα, την μέγιστη διαδρομή των άκρων που εναλλάσσονται μεταξύ των δύο χρωμάτων. Ειδικότερα, κάθε γράφημα έχει έναν ισότιμο χρωματισμό ακμών, έναν χρωματισμό με το βέλτιστο αριθμό χρωμάτων στα οποίο κάθε δύο κλάσσεις διαφέρουν ως προς το μέγεθος το πολύ μία μονάδα.
<!-- The De Bruijn–Erdős theorem may be used to transfer many edge coloring properties of finite graphs to infinite graphs. For instance, Shannon's and Vizing's theorems relating the degree of a graph to its chromatic index both generalize straightforwardly to infinite graphs.
considers the problem of finding a graph drawing of a given cubic graph with the properties that all of the edges in the drawing have one of three different slopes and that no two edges lie on the same line as each other. If such a drawing exists, then clearly the slopes of the edges may be used as colors in a 3-edge-coloring of the graph. For instance, the drawing of the utility graph
K3,3
as the edges and long diagonals of a regular hexagon represents a 3-edge-coloring of the graph in this way. As Richter shows, a 3-regular simple bipartite graph, with a given Tait coloring, has a drawing of this type that represents the given coloring if and only if the graph is 3-edge-connected. For a non-bipartite graph, the condition is a little more complicated: a given coloring can be represented by a drawing if the bipartite double cover of the graph is 3-edge-connected, and if deleting any monochromatic pair of edges leads to a subgraph that is still non-bipartite. These conditions may all be tested easily in polynomial time; however, the problem of testing whether a 4-edge-colored 4-regular graph has a drawing with edges of four slopes, representing the colors by slopes, is complete for the existential theory of the reals, a complexity class at least as difficult as being NP-complete.
As well as being related to the maximum degree and maximum matching number of a graph, the chromatic index is closely related to the linear arboricity
la(G)
of a graph G, the minimum number of linear forests (disjoint unions of paths) into which the graph's edges may be partitioned. A matching is a special kind of linear forest, and in the other direction, any linear forest can be 2-edge-colored, so for every G it follows that
la(G) ≤ χ′(G) ≤ 2 la(G)
. Akiyama's conjecture states that, from which it would follow more strongly that
2 la(G) − 2 ≤ χ′(G) ≤ 2 la(G)
. For graphs of maximum degree three,
is always exactly two, so in this case the bound
χ′(G) ≤ 2 la(G)
matches the bound given by Vizing's theorem. -->
Άλλοι τύποι για τον χρωματισμό ακμών
Ο Thue number ενός γραφήματος είναι ο αριθμός των χρωμάτων που απαιτούνται σε έναν χρωματισμό ακμών, σε συνδυασμό με την ισχυρότερη απαίτηση ότι σε κάθε διαδρομή, ακόμη και μήκους, τα πρώτο και δεύτερο μισό της διαδρομής σχηματίζουν διαφορετικές αλληλουχίες των χρωμάτων. The arboricity ενός γραφήματος είναι ο ελάχιστος αριθμός των χρωμάτων που απαιτούνται έτσι ώστε τα άκρα του κάθε χρώματος να μην έχουν κύκλους (αντί για το προτότυπο πρόβλημα ακμής χρωματισμού, που δεν έχουμε παρακείμενα ζεύγη ακμών). Δηλαδή είναι ο ελάχιστος αριθμός Unlike the chromatic index, the arboricity of a graph may be computed in polynomial time.
Η Λίστα Χρωματικών Ακμών είναι ένα πρόβλημα στο οποίο δίνεται ένα γράφημα που η κάθε πλευρά του συνδέεται με μια λίστα χρωμάτων, και πρέπει να βρούμε έναν ορθό χρωματισμό κατά τον οποίο το χρώμα κάθε ακμής επιλέγεται από την λίστα χρωμάτων. Ο χρωματικός δείκτης λιστας, ενός γραφήματος G είναι ο μικρότερος αριθμός k με την ιδιότητα ότι, ανεξάρτητα από το πώς επιλέγει κάποιος την λίστα χρωμάτων για τις ακμές, εφ 'όσον κάθε ακμή έχει τουλάχιστον k χρώματα στη λίστα της, ένας χρωματισμός είναι σίγουρο ότι θα πραγματοποιηθεί. Έτσι, ο χρωματικός δείκτης λίστας είναι πάντα τουλάχιστον τόσο μεγάλος όσο ο χρωματικός δείκτης. Η Dinitz εικασία για την ολοκλήρωση της μερικής Λατινικής πλατείας s μπορεί να αναδιατυπωθεί ως την δήλωση ότι λίστα χρωματικού αριθμού ακμών του πλήρες διμερές γράφημα
K n, n
ισούται άκρη χρωματικό αριθμό του, n. επιλυθεί η εικασία αποδεικνύοντας, γενικότερα, ότι σε κάθε διμερές γράφημα το χρωματικό δείκτη και λίστα χρωματική δείκτη είναι ίσες. Η ισότητα μεταξύ του χρωματικού δείκτη και του χρωματικού δείκτη λίστας εικάζεται ότι ισχύει, και ακόμη πιο γενικά, για αυθαίρετα πολυγραφήματα χωρίς αυτοβρόχους.αυτή η υπόθεση παραμένει ανοιχτή.
Πολλές άλλες παραλλαγές, που έχουν ασχοληθεί με τις κορυφές χρωμάτων, έχουν επεκταθεί στον χρωματσμό ακμών. Για παράδειγμα, ο πλήρης χρωματισμός είναι η παραλλαγή του χρωματισμού ακμών σε πλήρη χρωματισμό, ένας πιο σωστός χρωματισμός κατά τον οποίο κάθε ζεύγος χρωμάτων πρέπει να αντιπροσωπεύεται από τουλάχιστον ένα ζεύγος γειτονικών ακμών και στον οποίο ο στόχος είναι να μεγιστοποιηθεί ο συνολικός αριθμός των χρωμάτων Ο ισχυρός χρωματισμός είναι η παραλλαγή του χρωματισμού ακμών σε ισχυρό χρωματισμό, κατά τον οποίο κάθε δύο άκρες με γειτονικά άκρα πρέπει να έχουν διαφορετικά χρώματα. Ο ισχυρός χρωματισμός ακμών έχει εφαρμογές και σε συστήματα κατανομής καναλιού για τα ασύρματα δίκτυα. Ο άκυκλος χρωματισμός είναι παραλλαγή του χρωματισμού ακμών σε άκυκλο χρωματισμό, κατά τον οποίο κάθε δύο κατηγορίες χρωμάτων αποτελούν άκυκλες υποδιαιρέσεις (δηλαδή, ένα δάσος).
Αν ένα 3-κανονικό γράφημα σε μια επιφάνεια είναι 3-πλευρα χρωματισμένο,το διπλό γράφημα του σχηματίζει έναν τριγωνισμός της επιφάνεια η οποία είναι επίσης χρωματισμένο άκρο (παρ' όλου που γενικά δεν) κατά τέτοιον τρόπο ώστε κάθε τρίγωνο να έχει ένα άκρο για κάθε χρώμα. Άλλοι χρωματισμοί και προσανατολισμοί για τους τριγωνισμούς, με άλλους τοπικούς περιορισμούς σχετικά με το πώς τα χρώματα είναι διατεταγμένα στις κορυφές ή επιφάνειες του τριγωνισμού, μπορεί να χρησιμοποιηθούν για να κωδικοποιήσουν διάφορους τύπους γεωμετρικού αντικειμένου. Για παράδειγμα, ορθογώνιες υποδιαιρέσεις (τμήματα μιας υποδιαίρεσης ενός ορθογώνιου σε μικρότερα ορθογώνια, με τρία ορθογώνια να συναντιούνται σε κάθε κορυφή) μπορεί να περιγραφεί συνδυαστικά με μια "κανονική σήμανση», ενός δύο-χρωματισμού των ακμών ενός τριγωνισμού διπλής υποδιαίρεσης, με τον περιορισμό ότι οι άκρες που ενώνονται σε μια κορυφή σχηματίζουν τέσσερις συνεχόμενες υπακολουθίες, μέσα στην κάθε μια τα χρώματα είναι τα ίδια. Αυτή η σήμανση είναι διπλή σε χρωματισμό της ίδιας της ορθογώνιας υποδιαίρεση στην οποία οι κάθετες ακμές έχουν ένα χρώμα και οι οριζόντιες ακμές έχουν το άλλο χρώμα. Παρόμοιοι περιορισμοί για την σειρά με την οποία μπορεί να εμφανιστούν οι χρωματιστές άκρες γύρω από μια κορυφή μπορεί επίσης να χρησιμοποιηθεί για να κωδικοποιήσει την ευθεία γραμμή embeddings του πλέγματος των επίπεδων γραφημάτων και τα τρισδιάστατα πολύεδρα με άξονες παράλληλες πλευρές. Για καθένα από αυτά τα τρία είδη των κανονικών σημάνσεων, το σύνολο των κανινικών σημάνσεων μιας σταθερής μορφής γραφήματος  διανεμητικό lattice, στο οποίο μπορεί να χρησιμοποιηθεί για να κατηγοριοποιήσει γρήγορα όλες τις γεωμετρικές δομές που βασίζονται στην ίδια γραφική παράσταση (όπως όλοι οι άξονες παράλληλων πολύεδρων έχουν τον ίδιο σκελετό) ή να βρει δομές που ικανοποιούν επιπλέον περιορισμούς.
Ένα ντετερμινιστικό πεπερασμένο αυτόματο μπορεί να ερμηνευθεί ως ένα κατευθυνόμενο γράφημα στο οποίο κάθε κορυφή έχει τον ίδιο εξωτερικό βαθμό d, και οι ακμές είναι d -χρωματισμένες με τέτοιο τρόπο ώστε κάθε δύο άκρα με την ίδια κορυφή έχουν διακριτά χρώματα. Το πρόβλημα χρωματισμού δρόμου είναι το πρόβλημα χρωματισμού ακμών ενός κατευθυνόμενου γραφήματος με ομοιόμορφους εξωτερικούς βαθμούς, κατά τέτοιο τρόπο ώστε το αυτόματο που προκύπτει να έχει μία λέξη συγχρονισμού. έλυσε το πρόβλημα χρωματισμού δρόμου, αποδεικνύοντας ότι ένας τέτοιος χρωματισμός μπορεί να βρεθεί κάθε φορά που η συγκεκριμένη γραφική παράσταση είναι άρρηκτα συνδεδεμένη και το απεριοδικό.
Το θεώρημα του Ραμσή αφορά το πρόβλημα k-χρωματισμένων ακμών ενός μεγάλου πλήρους γραφήματος
Kn
έτσι ώστε να αποφευχθεί η δημιουργία μονοχρωματικών πλήρων υποδιαιρέσεων
Ks
Rk(s)
τέτοιος ώστε, όταν
, ένας τέτοιος χρωματισμός να μην είναι δυνατός. Για παράδειγμα,
R2(3) = 6
, δηλαδή όταν οι ακμές του γραφήματος
K6
είναι 2-χρωμες, πάντα θα υπάρχει ένα μονοχρωματικό τρίγωνο.
Εφαρμογές
Ο χρωματισμός ακμών ενός πλήρους γραφήματος μπορεί να χρησιμοποιηθεί για να προγραμματιστεί ένας κυκλικός-robin γύρος σε όσους το δυνατόν λιγότερο γύρους έτσι ώστε κάθε ένας από ένα ζευγάρι αντιπάλων να παίζει σε κάθε γύρο. Σε αυτήν την εφαρμογή οι κορυφές του γραφήματος αντιστοιχούν στους αντιπάλους του τουρνουά,οι ακμές αντιστοιχούν στα παιχνίδια και οι χρωματισμένες ακμές στους γύρους στους οποίους παίζονται τα παιχνίδια.Παρόμοιες τεχνικές χρωματισμού μπορούν επίσης να χρησιμοποιηθούν για να προγραμματίσουν άλλα ομαδικά αθλήματα που δεν είναι μεταξύ δύο παικτών. Για παράδειγμα, στην Εθνική Ομάδα Ποδοσφαίρου,τα ζευγάρια των ομάδων που θα παίξουν μεταξύ τους σε ένα δεδομένο έτος καθορίζονται με βάση τις εγγραφές των ομάδων από το προηγούμενο έτος, και στη συνέχεια ένας αλγόριθμος χρωματισμού ακμών εφαρμόζεται στην γραφική παράσταση που διαμορφώνεται από το σύνολο των ζευγαριών, προκειμένου να αναθέσει παιχνίδια για τα Σαββατοκύριακα.. Για την εφαρμογή αυτή, από το θεώρημα Vizing συνεπάγεται ότι ανεξάρτητα από την ομάδα ζευγαριών που θα επιλεγεί (εφ' όσον δεν υπάρχουν ομάδες που παίζουν μεταξύ τους δύο φορές την ίδια σεζόν), είναι πάντα δυνατό να βρεθεί ένα πρόγραμμα που χρησιμοποιεί το πολύ ένα ακόμη Σαββατοκύριακο από ό,τι τα παιχνίδια ανά ομάδα.
Ο Ανοικτός προγραμματισμός είναι ένα πρόβλημα προγραμματισμού παραγωγικών διαδικασιών, στο οποίο υπάρχει μια σειρά από αντικείμενα που πρόκειται να κατασκευαστούν, κάθε αντικείμενο έχει μια σειρά από εργασίες που πρέπει να εκτελεστούν σε αυτό ( σε οποιαδήποτε σειρά), και κάθε εργασία πρέπει να πραγματοποιείται σε ένα συγκεκριμένο μηχάνημα, αποτρέποντας οποιαδήποτε άλλη εργασία που χρησιμοποιεί το ίδιο μηχάνημα να εκτελείται ταυτόχρονα. Εάν όλες οι εργασίες έχουν το ίδιο μήκος, τότε το πρόβλημα αυτό μπορεί να τυποποιηθεί ως ένα πρόβλημα χρωματισμού ακμών ενός διμερούς πολυγράφου, κατά το οποίο οι κορυφές στην διμερή πλευρά αντιπροσωπεύουν τα αντικείμενα που πρόκειται να κατασκευαστούν, οι κορυφές στην απέναντι από την διμερή πλευρά αντιπροσωπεύουν τα μηχανήματα κατασκευής, οι ακμές αντιπροσωπεύουν τις εργασίες που πρέπει να εκτελεστούν, και τα χρώματα αντιπροσωπεύουν τα χρονικά διάστημα στα οποία μπορεί να πραγματοποιηθεί κάθε εργασία. Από την στιγμή που ο διμερές χρωματισμός ακμών μπορεί να γίνει σε πολυωνυμικό χρόνο, το ίδιο ισχύει και για την παρούσα κλειστή περίπτωση του ανοικτόυ προγραμματισμού.
(Δ + 1)
-άκρες χρωματισμένες, μαζί με μια φάση τελικής επεξεργασίας που αναδιοργανώνει τις ακμές που θα μπορούσαν να αλληλεπιδρούν μεταξύ τους.
Στην επικοινωνία οπτικών ινών, το πρόβλημα διαδρομής χρωματισμού είναι το πρόβλημα της ανάθεσης χρωμάτων (συχνότητες του φωτός) σε ζεύγη κόμβων που θέλουν να επικοινωνούν μεταξύ τους, με τον περιορισμό για τις διαδρομές μέσα από ένα δίκτυο επικοινωνιών οπτικών ινών για κάθε ζεύγος, ότι δεν υπάρχουν δύο διαδρομές που μοιράζονται ένα τμήμα των ινών που χρησιμοποιεί την ίδια συχνότητα, το ένα με τ' άλλο. Διαδρομές που περνούν μέσα από το ίδιο κύκλωμα επικοινωνίας, αλλά όχι μέσα από οποιοδήποτε τμήμα των ινών, επιτρέπεται να χρησιμοποιούν την ίδια συχνότητα. Όταν το δίκτυο επικοινωνιών διατάσσεται ως δίκτυο αστέρι, με ένα μόνο κεντρικό διακόπτη που είναι συνδεδεμένος με χωριστές ίνες σε κάθε ένα από τους κόμβους, τότε το πρόβλημα διαδρομής χρωματισμού μπορεί να μοντελοποιηθεί ακριβώς όπως ένα πρόβλημα χρωματισμού ακμών ενός γραφήματος ή ενός πολυγράφου, στα οποία οι κόμβοι που επικοινωνούν σχηματίζουν τις κορυφές του γραφήματος, τα ζεύγη των κόμβων που επικοινωνούν σχηματίζουν τις ακμές του γραφήματος, και οι συχνότητες που μπορεί να χρησιμοποιηθούν για κάθε ζεύγος σχηματίζουν τα χρώματα του προβλήματος χρωματισμού ακμών. Για τα δίκτυα επικοινωνιών, με μια πιο γενική τοπολογία, οι λύσεις των διαδρομών για τον χρωματισμό των δικτύων αστέρι που ορίζεται από κάθε διακόπτη στο δίκτυο, μπορεί να καταναμηθούν μαζί για να σχηματίσουν μια ενιαία συνολική λύση.
Ανοικτά Προβλήματα
Οι δημιούργησαν μια λίστα από 23 ανοικτά προβλήματα που αφορούν τον χρωματισμό ακμών. Αυτά είναι:
n/3
είναι είτε κλάσης 1 ή περιέχουν έναν υπόγραφο με τον ίδιο βαθμό
Δ
με το αρχικό γράφημα, και με μοναδικό αριθμό kτων κορυφών, έτσι ώστε ο αριθμός των ακμών στον υπόγραφο να είναι μεγαλύτερος από
Δ(k − 1)/2
, και μια παρόμοια θεωρία των Herbert Grötzsch και Paul Seymour σχετικά με τα επίπεδα γραφήματα στη θέση των γραφημάτων υψηλού βαθμού.
n/2
είναι κλάσης 1.
G
είναι ένας
d
-τυπικός πολυγράφος επίπεδος, τότε το
είναι -edge-απατηλός αν και μόνο αν
είναι περίεργο
Πηγές
Κατηγορία:Θεωρία γράφων
Γουότερλου (Σιέρα Λεόνε)
Το Γουότερλου (Waterloo) είναι πόλη στη Δυτική Περιφέρεια της Σιέρα Λεόνε, η πρωτεύουσα της Δυτικής Αγροτικής Επαρχίας. Η πόλη βρίσκεται μόλις περί τα τριάντα χιλιόμετρα ανατολικά της πρωτεύουσας της χώρας Φρίταουν και αποτελεί τη δεύτερη μεγαλύτερη πόλη της Δυτικής Περιφέρειας μετά από αυτή. Σύμφωνα με την απογραφή του 2004 το Γουότερλου είχε 34.079 κατοίκους, ενώ σύμφωνα με εκτίμηση του 2013 οι κάτοικοι έχουν υπερβεί τους 40.000. Η πόλη εντάσσεται στη μητροπολιτική περιοχή του Φρίταουν. Το Γουότερλου αποτελεί μείζονα συγκοινωνιακό κόμβο, όντας επάνω στην οδό που συνδέει την πρωτεύουσα με τις επαρχίες της χώρας.
Το Γουότερλου είναι μία από τις περισσότερο ποικιλόμορφες φυλετικά πόλεις της Σιέρα Λεόνε, καθώς φιλοξενεί πολλές από τις φυλετικές ομάδες της χώρας, με καμιά να μην αποτελεί την πλειοψηφία του πληθυσμού. Οι Κρίο (από το «Κρεολοί») είναι η πολυπληθέστερη ομάδα στην πόλη και η γλώσσα τους μακράν η περισσότερο ομιλούμενη στο Γουότερλου.
Η πόλη έχει το δικό της απευθείας εκλεγόμενο δημοτικό συμβούλιο με επικεφαλής δήμαρχο. Σημερινός δήμαρχος είναι ο Ντένις Ομοτζόγουο Μπράουν.
Ιστορία
Το Γουότερλου ιδρύθηκε το 1819 ως οικισμός για τους απελεύθερους δούλους Αφρικανούς. Ενσωματωμένη στο σύστημα των ενοριών υπό την καθοδήγηση της Εταιρείας Ιεραποστολής της Αγγλικανικής Εκκλησίας (Church Missionary Society, CMS), η πόλη εποικίσθηκε από άνδρες του 2ου και του 4ου Συντάγματος Δυτικών Ινδιών, από την Τζαμάικα και τα Μπαρμπάντος. Συνακόλουθα, πήρε το όνομά της προς τιμή της τελειωτικής νίκης των Βρετανών και των συμμάχων τους επί του Ναπολέοντος στη Μάχη του Βατερλώ (αγγλική προφορά «Γουότερλου»).
Οι πρώτοι έποικοι (που εγκαταστάθηκαν στη σημερινή συνοικία Σότζα Τάουν) επαυξήθηκαν αργότερα με την προσθήκη αρκετών ομάδων απελεύθερων, των οποίων η ενσωμάτωση στη νέα κοινότητα διευκολύνθηκε από την επιμονή του κυβερνήτη Μακάρθυ στην εκπαίδευση και στη θρησκευτική ένταξη. Αγγλικανοί, αλλά και άλλες προτεσταντικές ομολογίες όπως οι Ουεσλεϋανοί, ίδρυσαν εκκλησίες και σχολεία που κάλυπταν τον γρήγορα αυξανόμενο πληθυσμό. Οι Μικτές Επιτροπές στο Φρίταουν, που συστάθηκαν το 1819 κυρίως για να ξαναελευθερώσουν δούλους που είχαν ξανα-αιχμαλωτισθεί, έστελναν συνεχώς τέτοιους απελεύθερους στο Γουότερλου. Αντίθετα με τους αρχικούς πρώην στρατιώτες εποίκους, οι απελεύθεροι είχαν ελάχιστη σε διάρκεια επαφή με τις γλώσσες και τον πολιτισμό των λευκών. Επιχειρώντας να αποκαταστήσουν κάποια σταθερότητα τρόπου ζωής στο νέο περιβάλλον, εγκαταστάθηκαν κατά εθνοτικές ή φυλετικές περιοχές. Ούτως, οι Γιορούμπα εγκαταστάθηκαν στη συνοικία Άκου Τάουν (Aku Town), οι Ίμπο στην Ίμπο Τάουν, κλπ..
Η κοινότητα που δημιουργήθηκε με τον τρόπο αυτόν δημιούργησε θεσμούς κοινωνικής πρόνοιας όσο και μυστικές εταιρείες, όπως οι Ojeh, Geledeh και Akanja, ως μέσα για τη συνέχιση του πολιτισμού των προγόνων των κατοίκων, για την κοινωνική σταθερότητα και την ενίσχυση της οικονομικής ανεξαρτησίας τους.
Σε λιγότερο από μισό αιώνα από την ίδρυσή της, η πόλη ξεπρόβαλε ως ένα σημαντικό οικονομικό κέντρο μεταξύ της πρωτεύουσας και των επαρχιών. Κατά τον 20ό αιώνα το Γουότερλου συνέχισε τον ίδιο ρόλο, ακμάζοντας με την ανάπτυξη πλέον και του εμπορίου. Η οικονομική του ανάπτυξη συνδυαζόμενη με την εγγύτητά του στην πρωτεύουσα έφερε ένα ποικίλο πλήθος ανθρώπων από τις απομονωμένες επαρχίες της χώρας. Η ευημερία της πόλεως διαλύθηκε με το ξέσπασμα του Εμφύλιου Πολέμου τη δεκαετία του 1990, όταν επαναστάτες λεηλάτησαν και κατέστρεψαν σπίτια, σχολεία, ναούς, γραφεία και κρατικές υπηρεσίες, με πολλούς κατοίκους να φεύγουν από την πόλη ως πρόσφυγες.
Γεωγραφία
Το Γουότερλου βρίσκεται σε γεωγραφικές συντεταγμένες πλάτος 8°20΄ Βόρειο και μήκος 13°04΄ Δυτικό, κτισμένο σε μεσοσταθμικό υψόμετρο 40 μέτρα πάνω από την επιφάνεια της θάλασσας. Αποτελεί τη δεύτερη σε πληθυσμό πόλη της Δυτικής Περιφέρειας της Σιέρα Λεόνε, έκτη σε όλη τη χώρα, και σημαντικό συγκοινωνιακό κόμβο εξαιτίας της υπάρξεως της Χερσονήσου της Σιέρα Λεόνε, στο άκρο της οποίας είναι κτισμένη η πρωτεύουσα Φρίταουν.
Οι άνθρωποι
Οι γάμοι μεταξύ των απελεύθερων και του πυρήνα των πρώην στρατιωτών από την Τζαμάικα και τα Μπαρμπάντος εμπλούτισαν τον πολιτισμό του Γουότερλου, δημιουργώντας μια νέα γλώσσα, που εξελίχθηκε στη γλώσσα Κρίο. Η γλώσσα αυτή διατηρεί μία αγγλική βάση, ενώ έχει απορροφήσει παράλληλα γλωσσικά στοιχεία από άλλες ευρωπαϊκές και αφρικανικές γλώσσες και διαλέκτους, γεγονός προφανές σε λέξεις όπως boku (από το γαλλικό beaucoup), encore (ομοίως), otutu, alakpa, joko (από τη γιορούμπα), sabi, pikin (τζαμαϊκανά κρεολικά και πορτογαλικά), και άλλες.
Πηγές
Γουοτερλου
Διελκυστίνδα
Η  διελκυστίνδα  (αγγλ. Tug-of-War) είναι ένα άθλημα που παίζεται μεταξύ δύο ομάδων, οι οποίες τραβούν ένα σχοινί προσπαθώντας η μία να τραβήξει την άλλη προς το μέρος της. Η διελκυστίνδα στους Ολυμπιακούς Αγώνες διεξαγόταν από το 1900 ως το 1920, ενώ συμπεριλήφθηκε και στους Β΄ Διεθνείς Ολυμπιακούς Αγώνες του 1906 στην Αθήνα, στη λεγόμενη μεσοολυμπιάδα. Αρχικά ήταν ενταγμένη στο πρόγραμμα των αγωνισμάτων στίβου αλλά αργότερα λογιζόταν ως ανεξάρτητο άθλημα, αναγνωρισμένο από τη Δ.Ο.Ε.
Ιστορικά στοιχεία
Η διελκυστίνδα έχει αρχαίες ρίζες και η καταγωγή της είναι αβέβαιη. Η φήμη της χάνεται στα βάθη των αιώνων. Στην αρχαία Ελλάδα χρονολογείται από τον 5ο αιώνα π.Χ. Αναφέρεται ανάμεσα στα αγωνίσματα δύναμης που ασκούνταν οι νέοι για να βελτιώνουν τη φυσική τους κατάσταση και να αποκτήσουν ρώμη. Αναφέρεται σε πολλές περιοχές του πλανήτη, όπως: αρχαία Αίγυπτος, Ρώμη, Κίνα, Ινδία (από το 12ο αιώνα μ.Χ.), Μιανμάρ, ακόμα και στη Νέα Γουινέα. Στα χρόνια του μεσαίωνα υπάρχουν αναφορές για αγώνες με σχοινιά στην Ευρώπη, στη Γερμανία και στη Σκανδιναβία. Μετά το 1500 διεξάγονταν δημοφιλή τουρνουά στη Γαλλία και στη Μεγάλη Βρετανία. Μετά το 1800 αναφέρονται και αγώνες ανάμεσα σε ναύτες με βάρκες. Η αγγλική ονομασία του αθλήματος προήλθε από τη φράση «tug of war», που σημαίνει στην κυριολεξία, τον καθοριστικό αγώνα που θα κρίνει το αποτέλεσμα μιας αναμέτρησης. Τη μονομαχία από την οποία που θα κριθεί το αποτέλεσμα μιας μάχης. Μόλις το 19ο αιώνα δίνεται το όνομα αυτό στο άθλημα της διελκυστίνδας.
Κανονισμοί
Οι δυο ομάδες (ανδρικές ή γυναικείες) αποτελούνται από οκτώ άτομα και πρέπει το συνολικό σωματικό βάρος των αθλητών της μιας ομάδας να είναι το ίδιο με της αντιπάλου. Χρησιμοποιείται σχοινί από κάνναβη με ελάχιστο μήκος 33,5 και περιφέρεια ( όχι διάμετρο ) μεταξύ 100 έως 125 χιλιοστών. Σε κάθε ομάδα υπάρχουν τρεις αθλητές-κλειδιά, που είναι: ο αρχηγός, ο πρώτος στη σειρά και ο τελευταίος που τυλίγει (μια φορά) την άκρη του σχοινιού γύρω από τη μέση του και αποκαλείται άγκυρα (anchor).
Στην έναρξη του αγώνα το κέντρο του σχοινιού βρίσκεται ακριβώς πάνω από το σημείο εκκίνησης. Νικήτρια αναδεικνύεται η ομάδα που θα τραβήξει το σχοινί κατά τέσσερα μέτρα προς το μέρος της.
Διάδοση
Η διελκυστίνδα συμπεριλήφθηκε σε πέντε ολυμπιάδες: 1900, 1904, 1908, 1912 και 1920 καθώς και στη μεσοολυμπιάδα του 1906. Συχνά εθεωρείτο ως παιχνίδι διασκέδασης και όχι άθλημα. Οι κανονισμοί δεν είχαν ακόμα σταθεροποιηθεί και οι ομάδες δημιουργούνταν ευκαιριακά από τους δυνατότερους αθλητές κάθε χώρας, όπως: αρσιβαρίστες, ρίπτες, παλαιστές, ανεξαρτήτως βάρους. Υπήρξαν και μικτές ομάδες από αθλητές διαφόρων κρατών.
Επίσης, δεν είχε σταθεροποιηθεί ο αριθμός των μελών κάθε ομάδας. Το 1900 πήραν μέρος μόνο δύο ομάδες των έξι αθλητών, μια μικτή Δανών-Σουηδών που νίκησε και μια Γαλλική. Το 1904 μετείχαν έξι ομάδες των πέντε αθλητών: τέσσερις αμερικανικές, μια βρετανική και η ελληνική με τους: Γεωργαντά, Κακούση, Δημητρακόπουλο, Γεωργόπουλο και Μέταλο. Το 1906 στην Αθήνα καθιερώνονται οι οκταμελείς ομάδες και μετείχαν η Γερμανία, η Ελλάδα με τους Τσίτα, Βέλλα, Τριβουλίδη, Β. Ψάχο, Γ. Ψάχο, Κ. Λάζαρο, Σπ. Λάζαρο και Παπαχρήστου και η Σουηδία. Το 1908 μετείχαν πέντε: τρεις βρετανικές, μια σουηδική και μια από τις ΗΠΑ. Το 1912 πήραν μέρος μόνο η σουηδική και η βρετανική ομάδα. Τέλος, το 1920 μετείχαν πέντε χώρες.
Στις μέρες μας το άθλημα της διελκυστίνδας «καλλιεργείται» σε 54 κράτη, οι ομοσπονδίες των οποίων είναι μέλη της TWIF. Διοργανώνονται παγκόσμια πρωταθλήματα ανδρών και γυναικών, σε ανοιχτό γήπεδο και κλειστού χώρου. Στην Ελλάδα το άθλημα δεν είναι ιδιαίτερα δημοφιλές.
Αγαύη η σιζαλανή
Το σιζάλ, με τη βοτανική ονομασία Αγαύη η σιζαλανή (Agave sisalana), είναι ένα είδος αγαύης που προέρχεται από το νότιο Μεξικό, αλλά καλλιεργείται ευρέως, καθώς εγκλιματίστηκε σε πολλές άλλες χώρες. Παράγει μια σκληρή ίνα που χρησιμοποιείται για την παραγωγή διαφόρων προϊόντων. Ο όρος σιζάλ, δύναται να αναφέρεται είτε στη κοινή ονομασία του φυτού ή της ίνας, αναλόγως του θέματος. Μερικές φορές αναφέρεται ως «κάνναβη σιζάλ», επειδή για αιώνες η κάνναβη ήταν μια σημαντική πηγή για την παραγωγή ίνας, καθώς και άλλες πηγές ίνας, έλαβαν αυτό το όνομα.
Το σιζάλ χρησιμοποιείται παραδοσιακά για σχοινί και σπάγκους και έχει πολλές άλλες χρήσεις, όπως: χαρτί, ύφασμα, ταπετσαρίες τοίχων, χαλιά και πίνακες βελών (dartboards).
Άλλες ονομασίες
Οι Έλληνες στην Ανατολική Αφρική αποκαλούν το φυτό ως «σκοινί ή σχοινί» και αντιστοίχως τη φυτεία, ως «σκοινόκτημα ή σχοινόκτημα».
Ταξινομική
Η προέλευση της αγαύης της σιζαλανής είναι αβέβαιη. Παραδοσιακά, θεωρήθηκε ότι ήταν ιθαγενές της χερσονήσου Γιουκατάν, αλλά δεν υπάρχουν αρχεία των εκεί βοτανικών συλλογών. Είχαν αρχικά αποσταλεί από τον ισπανικό αποικιακό λιμένα του Sisal στο Γιουκατάν (απ' όπου και το όνομα). Οι φυτείες στο Γιουκατάν, τώρα καλλιεργούν τη «Χένεκεν» ("Agave fourcroydes").
Ο Howard Scott Gentry υπέθεσε μια προέλευση από την Τσιάπας (Chiapas), λόγω της δύναμης της παραδοσιακής τοπικής χρήσης. Αποδεικτικά στοιχεία της εγχώριας βιομηχανίας σε ένα εξοχικό σπίτι εκεί, τα προτείνει ως την αρχική θέση των ενδιαιτημάτων, πιθανόν ως διασταύρωση της Agave angustifolia και της Agave kewensis. Τα είδη έχουν πλέον εγκλιματιστεί σε άλλα μέρη του Μεξικού, καθώς και στην Ισπανία, Λιβύη, Μαρόκο, Κανάρια Νησιά, Πράσινο Ακρωτήριο, πολλά μέρη της Αφρικής, Μαδαγασκάρη, Ρεϋνιόν, Σεϋχέλλες, Κίνα, τα νησιά Ρίου Κίου, την Ινδία, Πακιστάν, Νεπάλ, Μιανμάρ, Καμπότζη, Ταϊλάνδη, νησιά του Σολομώντα, Κουίνσλαντ, Πολυνησία, Μικρονησία, Φίτζι, Χαβάη, Φλόριντα, Κεντρική Αμερική, Εκουαδόρ και Δυτικές Ινδίες.
Περιγραφή του φυτού
Τα φυτά σιζάλ, Agave sisalana, αποτελούνται από μια βοτανική ροζέτα (rosette) με φύλλα σχήματος σπαθιού, περίπου 1,5-2 μέτρα (04.09 - 06.06 πόδια) ψηλά. Τα νεαρά φύλλα μπορεί να έχουν μερικά λεπτά δόντια κατά μήκος των πλευρών τους, αλλά αυτά χάνονται καθώς ωριμάζουν τα φύλλα.
Το φυτό σιζάλ έχει διάρκεια ζωής 7-10 έτη και συνήθως παράγει 200-250 φύλλα εμπορικής χρήσης. Κάθε φύλλο περιέχει κατά μέσο όρο περίπου 1.000 ίνες. Οι ίνες αντιπροσωπεύουν μόνο το 4% του βάρους του φυτού. Το σιζάλ θεωρείται ένα φυτό των τροπικών και υποτροπικών περιοχών, καθώς η παραγωγή ωφελείται από την ηλιοφάνεια και όταν οι θερμοκρασίες είναι πάνω από 25 βαθμούς Κελσίου.
Στα σχοινοκτήματα, η μέση ετησία απόδοση είναι 1½-2 τόνους ανά εκτάριο. Η δε τιμή του σχοινιού εξαρτάται από την παγκόσμια ζήτηση, όπως και οι τιμές των άλλων καταναλωτικών αγαθών. Ενδεικτικά, αναφέρεται ότι η τιμή ενός τόνου το 1923 ήταν 25£, το 1929 ήταν 32£, ενώ με την έναρξη του Β΄ Παγκόσμιου Πολέμου και επειδή το σχοινί ήταν στρατηγικό υλικό, το 1941 και το 1942 (λόγω του πολέμου) παρέμεινε εσκεμμένα σε χαμηλή τιμή, ήτοι μόλις 20£/τόνος. Μόλις όμως τελείωσε ο πόλεμος, η τιμή του άρχισε μια σταδιακά ανοδική πορεία, για να φθάσει το 1951 τις 166£/τόνος και τον Μάρτιο του 1951 τις 215£/τόνος.
Καλλιέργεια
Τον 19ο αιώνα, η καλλιέργεια σιζάλ εξαπλώθηκε στη Φλόριντα, στα νησιά της Καραϊβικής, στη Βραζιλία καθώς και σε χώρες της Αφρικής κυρίως στην Τανζανία και στην Κένυα και την Ασία.
Οι πρώτες εμπορικές φυτείες στη Βραζιλία έγιναν στα τέλη του 1930 και οι πρώτες εξαγωγές ινών σιζάλ από εκεί έγιναν το 1948. Δεν ήταν μέχρι τη δεκαετία του 1960 που η βραζιλιάνικη παραγωγή επιταχύνθηκε και εγκαταστάθηκε το πρώτο από τα πολλά κλωστήρια. Σήμερα η Βραζιλία είναι ο κύριος παγκόσμιος παραγωγός του σιζάλ. Υπάρχουν τόσο θετικές όσο και αρνητικές περιβαλλοντικές επιπτώσεις από την καλλιέργεια του σιζάλ.