Ελάσσων γράφος

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

Η θεωρία των ελασσόνων γραφημάτων ξεκίνησε με το θεώρημα του Βάγκνερ σύμφωνα με το οποίο ένα γράφημα είναι επίπεδο αν και μόνο αν οι ελάσσονες του δεν περιλαμβάνουν το πλήρες Κ5 γράφημα ούτε το πλήρες διμερές γράφημα K3,3. Το θεώρημα Robertson-Seymour συνεπάγεται ότι ένας ανάλογος απαγορευμένος ελάσσων χαρακτηρισμός υπάρχει για κάθε ιδιότητα των γραφημάτων που διατηρούνται με διαγραφές και συγχωνεύσεις κουφών . Για κάθε σταθερό γράφημα H, είναι δυνατόν να ελεγχθεί αν Η είναι έλασσον ενός γραφήματος εισόδου G σε πολυωνυμικό χρόνο μαζί με τον απαγορευμένο ελάσσονα χαρακτηρισμό βάση του οποίου κάθε γράφημα ιδιότητας το οποίο δημιουργείται από διαγραφές και συγχωνεύσεις μπορεί να αναγνωριστεί σε πολυωνυμικό χρόνο.

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

Ορισμοί[Επεξεργασία | επεξεργασία κώδικα]

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

Τα ελάσσονα γραφήματα μελετώνται συχνά στο πιο γενικό πλαίσιο των πινακοειδων ελασσόνων. Σε αυτά τα πλαίσια, συχνά υποθέτουμε πως όλα τα γραφήματα ειναι συνδεδεμένα, με self-loops και πολλαπλές ακμές (δηλαδή είναι multigraphs και όχι απλά γραφήματα): Η συγχώνευση ενός loop και η διαγραφή μίας ακμής δεν είναι επιτρεπτές πράξεις. Αυτή η οπτική γωνία έχει το πλεονέκτημα του ότι αφήνουν το rank του γραφήματος αμετάβλητο και η συγχώνευση ακμών μειώνει πάντα το rank κατά 1 βαθμό.

Σε άλλες περιπτώσεις (όπως στην μελέτη των pseudoforests) είναι πιο λογικό να επιτραπεί η διαγραφή των ακμών, και να επιτραπούν τα μη-συνδεόμενα γραφήματα, αλλά να απαγορευθούν τα multigraphs. Σε αυτή την παραλλαγή της θεωρίας ελασσόνων γραφημάτων, ένα γράφημα πάντα απλοποιείται μετά από οποιαδήποτε συγχώνευση ακμών, ώστε να εξαλειφθούν τα self-loops και οι πολλαπλές ακμές.

Παράδειγμα[Επεξεργασία | επεξεργασία κώδικα]

Στο ακόλουθο παράδειγμα,το γράφημα Η είναι ελάσσον του γραφήματος G:

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

Σημαντικά Αποτελέσματα και Εικασίες[Επεξεργασία | επεξεργασία κώδικα]

Είναι εύκολο να βεβαιωθείτε ότι η σχέση ελάσσονος γραφήματος δημιουργεί ένα διατεταγμένο ζεύγος στις ισομορφικές τάξεις των μη κατευθηνόμενων γραφημάτων: είναι μεταβατική (ένα ελάσσον ενός ελασσόνος του G είναι ελάσσον του G), και G και Η μπορούν να είναι μόνο μεταξύ τους ελάσσονα αν είναι ισομορφικοί επειδή κάθε μη τετριμμένη ελάσσονα πράξη αφαιρεί ακμές ή κορυφές. Ένα αποτέλεσμα από τον Neil Robertson και ο Paul Seymour δηλώνει ότι αυτό το διατεταγμένο ζεύγος είναι στην πραγματικότητα ένα well-quasi-ordering (wqo): αν δίνεται μια μη πεπερασμένη λίστα G1, G2, ... πεπερασμένων γραφήματα, τότε υπάρχουν πάντα δύο δείκτες i <j, ώστε Gi να ειναι ελάσσων του Gj. Ένας άλλος ισοδύναμος τρόπος δήλωσης αυτού είναι ότι οποιοδήποτε σύνολο γραφημάτων μπορεί να έχει μόνο έναν πεπερασμένο αριθμό ελάχιστων στοιχείων υπό την ελάσσονα διάταξη. Αυτό το αποτέλεσμα αποτέλεσε απόδειξη μιας παλαιότερης εικασίας γνωστή ως εικασία του Βάγκνερ, εκ του Klaus Wagner: Ο Wagner την είχε διατυπώσει καιρό νωρίτερα, αλλά η εικασία δημοσιεύτηκε το 1970.

Κατά τη διάρκεια της απόδειξης τους, ο Seymour και ο Robertson αποδεικνύουν επίσης, το θεώρημα γραφικής δομής στο οποίο καθορίζουν, για κάθε σταθερό γράφημα H, την δομή του κάθε γραφήματος που δεν έχει το Η ως ελάσσον. Η διατύπωση του θεωρήματος είναι μακρά και περίπλοκη , αλλά εν συντομία δείχνει ότι ένα τέτοιο γράφημα πρέπει να έχει τη δομή ενός clique-sum των μικρότερων γραφημάτων που έχουν τροποποιηθεί μερικώς από γραφήματα ενσωματωμένα σε επιφάνειες οριοθετημένων γενών. Έτσι, η θεωρία τους θεσπίζει θεμελιώδεις συνδέσεις μεταξύ των ελασσόνων γραφημάτων και της τοπολογικής ενσωμάτωσης των γραφημάτων.

Για κάθε γράφημα H, τα απλά μη-ελάσσονα Η γραφήματα πρέπει να είναι διεσπαρμένα, πράγμα που σημαίνει ότι ο αριθμός των ακμών είναι μικρότερος από κάποιο σταθερο πολλαπλάσιο του αριθμού των κορυφών. Πιο συγκεκριμένα, αν Η έχει h κορυφές, τότε ένα απλό μη ελάσσον n-γωνο γραφημα h μπορεί να έχει το πολύ Ο(nh(sqrt(logh))) άκρα, και μερικα Kh-μη ελάσσονα γραφήματα έχουν τουλάχιστον τόσες ακμές. Έτσι, αν Η έχει h κορυφές, τότε τα μη-ελάσσονα Η γραφήματα έχουν μέσο βαθμό Ο(nh(sqrt(logh)))και επιπλέον εκφυλισμό Ο(nh(sqrt(logh))). Επιπροσθέτως, τα Η μη-ελασσονα γραφήματα έχουν ένα θεώρημα διαχωρισμού παρόμοιο με το θεώρημα επίπεδου διαχωρισμού για επίπεδα γραφήματα: για οποιοδήποτε σταθερό Η γραφημα, και κάθε n-κορυφών Η μη ελάσσονος γραφήματος G, είναι δυνατό να βρεθεί ένα υποσύνολο Ο(sqrt(n)) κορυφών των οποίων η απομάκρυνση χωρίζει G σε δύο (ενδεχομένως αποσυνδεδεμένα) υπογράφήματα με το πολύ 2n / 3 κορυφές ανά υπογράφημα. Ακόμα ισχυρότερη η πρόταση αυτή, για οποιοδήποτε σταθερό Η γράφημα,Η μη-ελάσσονα γραφήματα έχουν treewidth Ο(sqrt(n))

Η εικασία Hadwiger στη θεωρία γραφημάτων προτείνει ότι εάν ένα γράφημα G δεν περιέχει ένα ελάσσον ισομορφισμό στο πλήρες γράφημα για k κορυφές, τότε το G μπορει να χρωματιστεί με k - 1 χρώματα. Η περίπτωση k = 5 είναι μια επαναδιατύπωση του θεωρήματος τεσσάρων χρώματος. Η εικασία Hadwiger έχει αποδειχθεί για k ≤ 6, αλλά όχι στη γενική περίπτωση. Bollobás, Catlin & Erdős (1980) το αποκαλούν «ένα από τα βαθύτερα άλυτα προβλήματα στη θεωρία γραφημάτων». Ένα άλλο αποτέλεσμα που αφορα το θεώρημα των τεσσάρων χρωμάτων σε ελάσσον γράφημα είναι το θεώρημα snark που διατυπώθηκε από Robertson, Sanders, Seymour, και Thomas, το οποίο αποτελεί ενίσχυση του θεωρήματος τεσσάρων χρωμάτων που εικάστηκε από την WT Tutte και ότι κάθε μη-γεφυρωμένο 3-κανονικό γράφημα που απαιτεί τέσσερα χρώματα για ένα χρωματισμό άκρου πρέπει να έχει το γράφημα Petersen ως ελάσσον γράφημα.

Πηγές[Επεξεργασία | επεξεργασία κώδικα]

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]

http://mathworld.wolfram.com/GraphMinor.html