ΣΤΑΜΑΤΗΣ ΝΙΚΟΛΑΟΣ 3680

ΚΑΡΒΟΥΝΗΣ ΓΕΩΡΓΙΟΣ 3510

Τι είναι τα μητροειδή ;

¶Η θεωρία των μητροειδών είναι ένα παράδειγμα ενός μέρους των μαθηματικών που γεννήθηκε από την αφαίρεση. ¶Ο τρόπος που η θεωρία αυτή αυξήθηκε (βάζοντας μαζί ξεχωριστές ιδέες από διαφορετικούς τομείς των μαθηματικών) είναι ένα καλό παράδειγμα της διαδικασίας για το πώς ο κλάδος των μαθηματικών αναπτύσσεται. ¶Υπάρχουν πολλά παραδείγματα από μητροειδή: ¶δυαδικά μητροειδή, εγκάρσια μητροειδή, γραφικά μητροειδή, μητροειδή ακαμψίας, κανονικά μητροειδή, και Κ-συνδεμένα μητροειδή.

¶

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

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

1. Το κενό σύνολο είναι στο Ι.
2. Εάν το Χ είναι στο Ι, κατόπιν κάθε υποσύνολο του Χ είναι επίσης στο Ι
3. Εάν το Χ και το Υ είναι ανάμεσα στο Ι, και |X| είναι μεγαλύτερα από |Y|, κατόπιν υπάρχει κάποιο στοιχείο χ του X/Υ έτσι ώστε Y(ένωση){ χ} είναι επίσης στο Ι.

Το Ε καλείται επίγειο σύνολο του Μ, και το καθορισμένο υποσύνολο Ι είναι η συλλογή των ανεξάρτητων υποσυνόλων του Ε. Εκείνα τα υποσύνολα του Ε που δεν είναι στο Ι καλούνται εξαρτώμενα. Επίσης, είναι ίδιο να γραφτεί το καθορισμένο υποσύνολο Y(ένωση){x} ως Y(ένωση)x, ρίχνοντας τα υποστηρίγματα. Μερικές από τις θεωρίες των μητροειδών ήρθαν ως αποτέλεσμα της μελέτης των διανυσμάτων και των διανυσματικών διαστημάτων

Μερικά παραδείγματα μητροειδών.

Παρακάτω θα δώσουμε τρία βασικά παραδείγματα των μητροειδών,

Παράδειγμα1. Ορίζουμε το Ε να είναι ένα πεπερασμένο σύνολο διανυσμάτων από ένα διανυσματικό διάστημα, και ορίζουμε το Ι να είναι το σύνολο γραμμικά ανεξάρτητων υποσυνόλων των διανυσμάτων του Ε. Κατόπιν M=(E, Ι) είναι μητροειδή. Αυτό καλείται και vectorial μητροειδή. Μερικά από τα αξιώματα των μητροειδών εφαρμόζονται σε μια πεπερασμένη συλλογή των διανυσμάτων για κάποιο διανυσματικό διάστημα, που παίρνει "τον ανεξάρτητο" στο μέσο "γραμμικά ανεξάρτητο". Το τρίτο των αξιωμάτων απλά δηλώνει ότι το υποδιάστημα που παράγεται από το Υ (δηλ., το μικρότερο ανεξάρτητο σύνολο)δεν μπορεί να περιέχει όλο το Χ ( το μεγαλύτερο ανεξάρτητο σύνολο).

Παράδειγμα 2. Ορίζουμε το ρ και το ν να είναι μη αρνητικοί ακέραιοι αριθμοί με το ρ όχι μεγαλύτερο από το ν. Ορίζουμε το Ε να είναι ένα ν - στοιχείο συνόλου, καθώς και το Ι να είναι η συλλογή όλων των υποσυνόλων του Ε, μεγέθους ρ ή μικρότερου . Κατόπιν είναι εύκολο να φανεί ότι το M=(E,Ι) είναι ένα μητροειδή. Αυτό καλείται ομοιόμορφο μητροειδή τάξης ρ του στοιχείου ν, U(ρ,ν)

Παράδειγμα 3. Λαμβάνοντας υπόψη μια γραφική παράσταση Γ, ορίζουμε το Ε να είναι το σύνολο όλων των ακρών του Ε, και ορίζουμε το Ι να είναι τα υποσύνολα του Ε του οποίου τα υπογραφήματα δεν περιέχουν κανένα πολύγωνο (κανένα υποσύνολο του Ε δεν είναι μια συλλογή των ακρών από ένα πολύγωνο). Κατόπιν M=(E,Ι) είναι μητροειδή , που καλείται γραφικό μητροειδή Μ(G). Δεν είναι εύκολο να δειχθεί ότι το Ι ικανοποιεί πραγματικά τα τρία αξιώματα που δίνονται στον ορισμό

Κυκλώματα, βάσεις, τάξη, περάτωση

ΟΡΙΣΜΟΙ :

Τα κυκλώματα είναι ελάχιστα εξαρτώμενα σύνολα. Ένα κύκλωμα ενός στοιχείου είναι ένας βρόχος.
Οι βάσεις είναι μέγιστα ανεξάρτητα σύνολα.
Η τάξη ενός υποσυνόλου Χ του Ε, έδειξε το ρ (X), είναι το μέγεθος του μεγαλύτερου ανεξάρτητου συνόλου του Ε που περιλαμβάνεται μέσα στο Χ.
Η περάτωση ενός υποσυνόλου Χ του Ε, έδειξε το cl (X), είναι το ίδιο το σύνολο Χ- ένωση όλα τα στοιχεία του Ε που μπορούν να προστεθούν στο Χ χωρίς αύξηση της τάξης.

Θα επιθυμούσαμε να είμαστε σε θέση να καθορίσουμε τα μητροειδή ακριβώς από την άποψη του συνόλου κυκλωμάτων και να μην κάνουμε οποιαδήποτε αναφορά σε οποιαδήποτε ανεξάρτητα σύνολα ή κάτι παρεμφερή. Μοναδικός από αυτούς τους ορισμούς που δίνεται για τα κυκλώματα είναι ο ακόλουθος.

Λαμβάνοντας υπόψη ένα υποσύνολο Ε και μια συλλογή των υποσυνόλων του C, το σύνολο C είναι μια συλλογή των κυκλωμάτων για μητροειδή εάν και μόνο εάν το C είναι τέτοιο που:

1. Το κενό σύνολο δεν είναι το C

Λαμβάνοντας υπόψη οποιαδήποτε δύο στοιχεία C1 και C2 του C , και οποιοδήποτε χ μέσα σε C1(intersect)C2, υπάρχει σύνολο C3 μέσα στο [ C1(ένωση)C2] / χ που είναι στο C επίσης.

Παράδειγμα Κυκλώματος :

¶Το παρακάτω διάγραμμα είναι μια γραφική παράσταση. ¶Για τους σκοπούς του καθορισμού των μητροειδών από τις γραφικές παραστάσεις θεωρούμε -επιτρέπουμε σε ένα σημείο στο οποίο τέμνονται δύο γραμμές να ενωθούν μεταξύ τους και έτσι να σχηματίσουν ένα βρόχο. ¶Τέτοιες γραφικές παραστάσεις καλούνται συνδεμένες. ¶Το παράδειγμα που παρουσιάζεται εδώ ονομάζει τα σημεία στα οποία σχηματίζεται βρόχος με γράμματα και τις άκρες με αριθμούς. ¶Αυτή η γραφική παράσταση έχει 6 σημεία στα οποία σχηματίζεται ένας βρόχος και 10 άκρες. ¶

Εάν κάποιος αρχίζει από ένα σημείο στη γραφική παράστασή στο οποίο σχηματίζεται βρόχος, στη συνέχεια κινείται κατά μήκος των αχρησιμοποίητων ακρών και επιστρέφει στο αρχικό σημείο, δηλαδή έχει 'σχηματίσει' ένα κύκλωμα. ¶Στην παραπάνω γραφική παράσταση παραδείγματα κυκλωμάτων είναι: ¶u, v, s, u ¶και v (μέσω της άκρης 1), w, v (μέσω της άκρης 2). Θεωρήσουμε ότι δύο κυκλώματα είναι το ίδιο πράγμα εάν γραφούν με την αντίστροφη κυκλική φορά. Υπάρχουν πολλοί τρόποι να γράψουμε το ίδιο κύκλωμα, αν και είναι λίγο διαφορετικοί. ¶Κατά συνέπεια, s, w, x, t, s και w, x, t, s, w και w, s, t, x, w είναι όλα διαφορετικές σημειώσεις για το ίδιο κύκλωμα. ¶

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

Πόσες άκρες μπορεί να έχει μια συνδεδεμένη γραφική παράσταση με n σημεία στα οποία σχηματίζονται βρόχοι; ¶Η απάντηση είναι (n-1) άκρες. ¶

Η 'ιδέα' ενός μητροειδούς που κατασκευάζεται από μια γραφική παράσταση (γνωστή ως γραφικά μητροειδή) αρχίζει με το σύνολο ακρών της γραφικής παράστασης μαζί με τα υποσύνολα των ακρών τα οποία διαμορφώνουν τα κυκλώματα των γραφικών παραστάσεων (συμπεριλαμβανομένων των κυκλωμάτων που είναι βρόχοι). ¶

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

¶

Εδώ είναι ένας κατάλογος των κυκλωμάτων για τη γραφική παράσταση στο σχήμα 1: ¶(10), (3,4,5), (1,2), (2,5,6), (1,5,6), (3,4,6,2), (6,9,8,7), (3,4,9,8,7,2), (2,5,9,8,7), (1,5,9,8,7), και (3,4,6,1). ¶Υπάρχουν 11 κυκλώματα. ¶

¶Μπορούμε να προσπαθήσουμε να ‘αφαιρέσουμε’ τις ιδιότητες των κυκλωμάτων σε μια γραφική παράσταση με τον ίδιο τρόπο που ‘αφαιρέσαμε’ τις ιδιότητες του να είναι ανεξάρτητα σε ένα διανυσματικό διάστημα. ¶Υποθέστε ότι έχουμε μια συλλογή από υποσύνολα C σε ένα σύνολο Ε που 'υπακούει' στους κανόνες: ¶

¶1) Το μηδενικό σύνολο είναι στο C. ¶

¶2) εάν C1 και C2 είναι μέλη του C όπου C1C2 ,τότε C1 = C2. ¶

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

¶3) υποθέστε ότι C1 και C2 είναι ευδιάκριτα υποσύνολα του C, και Ε είναι μέλος C1C2 , τότε υπάρχει ένα μέλος C3 στο C τέτοιο ώστε:

¶C3(C1C2)-Ε

O κανόνας 3 δείχνει την ιδιότητα των κυκλωμάτων που λέει ότι όταν δύο κυκλώματα έχουν μια άκρη e κοινή, κάποιος μπορεί να δημιουργήσει ένα νέο κύκλωμα από τις άκρες των δύο κυκλωμάτων που δεν χρησιμοποιεί την άκρη Ε.

¶Έχοντας το σύνολο των ακρών E μιας γραφικής παράστασης G, το σύνολο των κυκλωμάτων του G είναι το κύκλωμα-σύνολο C ενός μητροειδούς. ¶Αυτό το μητροειδές είναι γνωστό ως κυκλικό μητροειδές.

¶

¶Τώρα μπορεί να μην είναι εύκολο να φανούν οι συνδέσεις μεταξύ της ‘αφαίρεσης’ της ανεξαρτησίας για ένα διανυσματικό διάστημα και αυτής των κυκλωμάτων για μια γραφική παράσταση, αλλά μπορούν να φανούν με τη χρησιμοποίηση μερικών ορισμών. ¶Δεδομένου ότι στο ανεξάρτητο σύνολο τα ειδικά υποσύνολα του Ε που είναι μέσα στο Ι καλούνται ανεξάρτητα, φαίνεται φυσικό ότι ένα υποσύνολο του Ε που δεν είναι μέσα στο Ι να είναι εξαρτώμενο. ¶Εκείνα τα σύνολα μέσα στο Ι που είναι μέγιστα, δηλαδή εάν κάποιος προσθέσει οποιοδήποτε στοιχείο του Ε σε αυτά, τότε αυτά δεν είναι πλέον στο Ι , καλούνται βάσεις. ¶Κάποιος μπορεί να αποδείξει ότι σε οποιοδήποτε μητροειδές όλες οι βάσεις έχουν τον ίδιο αριθμό στοιχείων, ακριβώς όπως ισχύει για τις βάσεις ενός διανυσματικού διαστήματος. ¶Εάν τα μέγιστα ανεξάρτητα σύνολα παρουσιάζουν μεγάλο ενδιαφέρον, τι γίνεται με τα ελάχιστα εξαρτώμενα σύνολα; Θα καθορίσουμε αυτά τα σύνολα, που είναι ελάχιστα εξαρτώμενα, και τα οποία συμπεριφέρονται ως κυκλώματα! ¶Σημειώνουμε ότι μόλις διευκρινιστούν τα ανεξάρτητα σύνολα ενός μητροειδούς, τα κυκλώματα καθορίζονται αυτόματα, και αντιθέτως. ¶Τώρα χρησιμοποιώντας τους κανόνες της ανεξαρτησίας 1 - 3, μπορεί να αποδειχθεί ότι το σύνολο κυκλωμάτων που μόλις καθορίστηκε υπακούει τους κανόνες των κυκλωμάτων 1 - 3.

Δυαδικότητα

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

Παράδειγμα Δυαδικότητας στην θεωρία των μητροειδών.

Έστω ας πάρουμε ένα μητροειδή Μ, και ορίζουμε το β να είναι η συλλογή βάσεών (μια βάση είναι ένα μέγιστο ανεξάρτητο υποσύνολο του συνόλου Ε) τέτοια ώστε β* = {E\B | B in B}. Το σύνολο β * είναι ένα σύνολο βάσεων μητροειδών , που χρησιμοποιεί το ίδιο έδαφος συνόλου όπως το Μ. Αυτό το μητροειδή καλείται διπλό μητροειδή του Μ, και είναι δείγμα του Μ *.

Αντιπροσωπευτικότητα

Λέμε ότι ένα μητροειδές Μ είναι αντιπροσωπεύσιμο πέρα από έναν πεδίο F εάν υπάρχει κάποιο διανυσματικό διάστημα V άνω του F, με κάποιο πεπερασμένο υποσύνολο Ε των διανυσμάτων του V, έτσι ώστε το M να είναι ισομορφικό vectorial μητροειδή του συνόλου Ε. (Έτσι μπορούμε να σκεφτούμε το Μ είναι αποτελούμενο από μια δέσμη των διανυσμάτων σε κάποιο διανυσματικό διάστημα πέρα από τον πεδίο F.) Το μητροειδές που είναι αντιπροσωπεύσιμο άνω των GF (2) ονομάζεται "δυαδικό", και άνω των GF (3) "τριαδικό".

Παρακάτω αναφέρονται μερικά εκπληκτικά και σημαντικά αποτελέσματα για την αντιπροσωπευτικότητα.

1. Το μητροειδή GF(2) είναι αντιπροσωπεύσιμο εάν δεν έχει κανένα U(2, 4)- ανήλικο.

2. Το μητροειδή GF(3) είναι αντιπροσωπεύσιμο εάν δεν έχει κανένα ανήλικο ισομορφικό U(2, 5), U(3, 5)

Αυτό το είδος του θεωρήματος, που απαριθμεί όλους τους απαγορευμένους ανηλίκους που συνδέονται με έναν ειδικό τομέα, καλείται αποκλεισμένος δευτερεύον χαρακτηρισμός.

ΑΝΕΞΑΡΤΗΤΑ ΣΥΝΟΛΑ

¶Ένα σύνολο διανυσμάτων (ή σημείων) I είναι ανεξάρτητη εάν κάποιο από αυτά δεν μπορεί να έχει ένα τουλάχιστον διάνυσμα (σημείο) στο σύνολο I ως γραμμικό συνδυασμό των άλλων σημείων στο Ι. Ένα σύνολο ανεξάρτητων σημείων, στα οποία κάποιο από αυτά δεν μπορεί να προσθέσει κάποιο επιπλέον διάνυσμα (σημείο) και ακόμα να έχει ένα ανεξάρτητο σύνολο καλείται σύνολο βάσης σημείων. ¶Μια βάση (για ένα πεπερασμένο διαστατικό διανυσματικό διάστημα) είναι ένα μέγιστο ανεξάρτητο σύνολο διανυσμάτων. ¶

¶;E;E;EEFF’Ε’Έστω ότι το I είναι ένα σύνολο ανεξάρτητων αντικειμένων. ¶Παρακάτω είναι οι κανόνες στους οποίους θέλουμε το σύνολο I να υπακούει: ¶

¶1) το σύνολο I δεν είναι κενό. ¶

¶2) κάθε υποσύνολο από ένα τμήμα του I είναι επίσης τμήμα του Ι.

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

¶3) εάν το Χ και το Υ είναι στο Ι όπου το Χ έχει ένα περισσότερο στοιχείο από το Υ, κάποιος μπορεί να βρεί ένα στοιχείο x στο Χ που δεν είναι στο Υ.

¶Σημειώνουμε ότι τα ανεξάρτητα σύνολα σε ένα διανυσματικό διάστημα έχουν αυτήν την ιδιότητα της ιδιοκτησίας. ¶Εδώ έχουμε μερικούς κανόνες που αφαιρούν την έννοια της ανεξαρτησίας. ¶

¶Ένα μητροειδές τώρα αποτελείται από ένα πεπερασμένο σύνολο Ε και τα υποσύνολα του Ε που ικανοποιούν τον κανόνα 1 μέσω του κανόνα 3.

¶Παράδειγμα: ¶

¶Έστω η μήτρα Α = ¶

¶Αριθμήστε τις στήλες με τους αριθμούς 1, 2, 3, και 4, και αφήστε το Ε να είναι το σύνολο από τους αριθμούς των ετικετών των στηλών. ¶Εξετάζουμε τα ακόλουθα υποσύνολα του Ε: ¶

¶Μπορούμε να δούμε ότι αυτή η συλλογή των συνόλων μπορεί να λειτουργήσει όπως το ανεξάρτητο σύνολο I για ένα μητροειδές στο σύνολο Ε, με την επαλήθευση από τα αξιώματα (κανόνες) που έχουμε γράψει παραπάνω.

¶Ο τρόπος με τον οποίο η παραπάνω συλλογή των συνόλων μπορεί να προκύψει είναι να ελεγχθεί ποιο από τα σύνολα των στηλών της μήτρας Α είναι γραμμικά ανεξάρτητα. ¶Αυτός ο τύπος των μητροειδών καλείται συχνά διανυσματικό μητροειδές της μήτρας Α. Επειδή μία ενιαία στήλη διαφορετική από το μηδέν είναι γραμμικά ανεξάρτητη, σε αυτό το παράδειγμα οποιοδήποτε ζευγάρι από τις στήλες που αριθμούνται 1, 2, ή 3 (οι διαφορετικές από το μηδέν στήλες) είναι επίσης ανεξάρτητο. ¶Σημειώνουμε ότι οι πρώτες τρεις στήλες δεν είναι γραμμικά ανεξάρτητες. ¶Ένας θεωρητικός (αλλά όχι υπολογιστικά ελκυστικός) τρόπος για να πούμε εάν κάποιο σύνολο στηλών Κ (καμία από τις οποίες δεν αποτελείται από μηδενικά) από μια k μήτρα είναι γραμμικά ανεξάρτητο είναι να υπολογιστεί ο καθοριστικός παράγοντας των σχετικών στηλών. ¶Εάν αυτός ο καθοριστικός παράγοντας είναι διαφορετικός από το μηδέν, οι στήλες είναι ανεξάρτητες ¶διαφορετικά, είναι εξαρτώμενες. Επίσης, παρατηρούμε ότι όταν κάποιος αναφέρεται στη γραμμική ανεξαρτησία, θα πρέπει να διευκρινίσει έναν τομέα των στοιχείων. ¶Δύο γνωστά παραδείγματα των τομέων είναι οι λογικοί αριθμοί και οι πραγματικοί αριθμοί. ¶Στην περίπτωσή μας μπορούμε, στην ουσία, να χρησιμοποιήσουμε οποιοδήποτε τομέα. ¶Ειδικότερα, μπορούμε να σκεφτούμε τις στήλες της μήτρας Α για να έχουμε εφαρμογή από τον τομέα και των δύο στοιχείων. ¶Όπως έχουμε είδη προαναφέρει, ένα μητροειδές που προκύπτει ως διανυσματικό μητροειδές για μια μήτρα σύμφωνα με τον τομέα 2 στοιχείων, είναι γνωστό ως δυαδικό μητροειδές. ¶Ο W.T. Tutte καθόρισε το 1958 ακριβώς ποια μητροειδή προκύπτουν κατ' αυτό τον τρόπο.

Παρακάτω παρατίθεται το θεώρημα, το οποίο ανακαλύφθηκε από τον Tutte το 1965:

Το μητροειδή είναι αντιπροσωπεύσιμο πέρα από κάθε πεδίο εάν είναι αντιπροσωπεύσιμο άνω των GF (2) και πέρα από κάποιο πεδίο του χαρακτηριστικού εκτός από δύο.

Μητροειδή όπως σε αυτό το θεώρημα καλείται κανονικό

Εφαρμογές μητροειδών

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

¶Εξετάστε μία συλλογή από δουλειές που πρέπει να 'γεμίσουν' από μία συλλογή εργαζομένων. ¶Για κάθε δουλειά υπάρχει ένας κατάλογος εργαζομένων (των οποίων τα ονόματα είναι 1,2,...,7) με το ποιοι είναι κατάλληλοι για να εκτελέσουν μία εργασία. ¶Το πρόβλημα είναι να διοριστεί ένας καταρτισμένος εργαζόμενος σε κάθε εργασία. ¶Εδώ είναι ένα συγκεκριμένο παράδειγμα, όπου σε κάθε εργαζόμενο μπορεί να οριστεί μια εργασία για την οποία είναι κατάλληλος: ¶

¶J1 =

¶J2 =

¶J3 =

¶J4 =

¶J5 =

¶J6 =

¶J7 =

¶Αυτό το ιδιαίτερο πρόβλημα μπορεί να απαντηθεί από ένα θεώρημα του βρετανικού μαθηματικού Philip Hall.

¶Το θεώρημα του Philip Hall δηλώνει ότι για μια συλλογή των υποσυνόλων ενός πεπερασμένου συνόλου, είναι δυνατό να επιλεχτεί ένα στοιχείο από κάθε ένα από αυτά τα σύνολα, έτσι ώστε τα επιλεγμένα στοιχεία να είναι ευδιάκριτα εάν και μόνο εάν η ένωση οποιουδήποτε κ από τα σύνολα να έχει τουλάχιστον κ στοιχεία. ¶

¶Τα επιλεγμένα στοιχεία αναφέρονται μερικές φορές ως σύστημα των ευδιάκριτων αντιπροσώπων (SDR). ¶Στο θεώρημα του Philip Hall παρουσιάζονται τα εγκάρσια μητροειδή. ¶Ήταν ο Richard Rado που κατάφερε να αποδείξει το σημαντικότατο ρόλο που παίζει η θεωρία του Philip Hall στα μητροειδή. ¶Αυτό έχει οδηγήσει στη δημιουργία υποτομέων μέσα στα μητροειδή για τη μελέτη των εγκάρσιων μητροειδών. ¶

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

¶Μια άλλη εφαρμογή των ιδεών σχετικά με τα μητροειδή παρέχεται από το ακόλουθο παράδειγμα. ¶

Υποθέστε ότι η παρακάτω γραφική παράσταση με τα βάρη που συνδέονται στις άκρες δίνει το κόστος της παροχής ενός ιδιαίτερου τύπου ασύρματης επικοινωνίας μεταξύ του Α, του Β, του C, του D, και Ε. Το κόστος, του να είναι δυνατόν να σταλθεί ένα μήνυμα μεταξύ δύο περιοχών που βρίσκονται “στα σημεία τέλους της άκρης”, δίνεται από το βάρος που ορίζεται σε εκείνη την άκρη. ¶

¶Το γεγονός ότι κάθε ζευγάρι σημείων στα οποία σχηματίζονται βρόχοι σε αυτήν την γραφική παράσταση συνδέεται ( πράγμα το οποίο δεν είναι απαραίτητο), οφείλεται στο ότι τα σημεία αυτά συνδέονται έμμεσα και μπορούν να αναμεταδώσουν τα μηνύματα μεταξύ τους. ¶Κατά συνέπεια, εάν υπάρχουν συνδέσεις από το B στο C και από το C στο E, κατόπιν ένα μήνυμα μπορεί να σταλεί από το B στο E ακόμα κι αν η άκρη BE δεν είναι μέρος του συστήματος. Εδώ τίθεται ένα ερώτημα: ¶Ποιες άκρες θα έπρεπε να τοποθετηθούν στο δίκτυο έτσι ώστε τα μηνύματα να μπορούν να σταλούν μεταξύ οποιουδήποτε ζευγαριού των 5 'περιοχών' και έτσι ώστε το κόστος για την παροχή υπηρεσιών να είναι ελάχιστο; ¶Αυτό που χρειάζεται είναι να βρεθεί ένα ελάχιστου βάρους εκτεινόμενο δέντρο για τη συγκεκριμένη γραφική παράσταση. ¶

Στον αμερικανό μαθηματικό Joseph Kruskal οφείλεται η εύρεση μιας πολύ κομψής λύσης σε αυτό το πρόβλημα. ¶ Ο αλγόριθμος Kruskal- Boruvka είναι ένας 'άπληστος' αλγόριθμος σύμφωνα με τον οποίο σε κάθε στάδιο παίρνεται η καλύτερη δυνατή απόφαση. ¶Εδώ είναι η διαδικασία. ¶Ταξινομήστε τα βάρη των ακρών από το μικρότερο στο μεγαλύτερο.¶ Σε κάθε στάδιο επιλέξτε αυτή την άκρη που είναι η φτηνότερη (οι δεσμοί μπορούν να σπάσουν αυθαίρετα), η οποία λαμβανόταν μαζί με τις προηγούμενες επιλεγμένες άκρες, αλλά δεν δημιουργεί ένα κύκλωμα. ¶

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

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

Διανυσματικά διαστήματα και γραφικές παραστάσεις

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

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

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

¶Τα παρακάτω είναι μερικά στοιχεία της θεωρίας των διανυσματικών διαστημάτων. ¶Έ#στωΈΕΕδψ Έστω ένα σύστημα όπου η αρχή του είναι το σημείο (0, 0) και οι συντεταγμένες των σημείων στα κεφάλια των διανυσμάτων είναι (a, b) και (c, d). Έτσι προκύπτει ότι το ποσό (a, b) και (c, d) είναι (a + c, b + d). ¶Κάποιος επίσης μπορεί να κάνει πολλαπλασιασμό των σημείων (πραγματικοί αριθμοί διαφορετικοί από το μηδέν). ¶Κατά συνέπεια (ra, rb) αντιπροσωπεύει ένα διάνυσμα που έχει την ίδια κατεύθυνση με το διάνυσμα (a,b) αλλά είναι r φορές μεγαλύτερο. ¶Για παράδειγμα όταν το r είναι 1/2, το διάνυσμα θα είναι το μισό από το αρχικό. ¶Όταν το r είναι αρνητικό, η κατεύθυνση του διανύσματος αντιστρέφεται αλλά το μήκος του είναι r φορές το αρχικό. ¶Έχουμε τα βασικά στοιχεία της άλγεβρας των σημείων, τα οποία μπορούν να θεωρηθούν ως διανύσματα. ¶Καθορίστε ένα ζευγάρι των ειδικών διανυσμάτων i (= (1, 0)) και j (= (0, 1)). ¶Τα {i, j} καλούνται βάση. ¶Οποιοδήποτε διάνυσμα (a, b) μπορεί να γραφτεί ως ai + bj, δηλαδή ως γραμμικός συνδυασμός των δύο διανυσμάτων i και j. ¶

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

¶x -2y + 4z = 0 (1). ¶

¶Αυτή η εξίσωση, όπως οποιαδήποτε εξίσωση της μορφής

¶ax + by + cz = 0 (2)

¶καθορίζει ένα αντικείμενο στο 3-διάστημα που περνά από το σημείο (0, 0, 0). ¶Η γεωμετρία του 3-διαστήματος είναι τέτοια που δύο διαφορετικά αντικείμενα είναι είτε παράλληλα είτε οι προεκτάσεις των διευθύνσεων τους τέμνονται. ¶Όταν δύο αντικείμενα έχουν ένα κοινό σημείο, πρέπει να έχουν και μία κοινή γραμμή. ¶Εδώ είναι ένα παράδειγμα ενός συστήματος των γραμμικών εξισώσεων στο 4-διαστατικό (πραγματικό) χώρο, όπου κάθε μια από τις οποίες περνά από το σημείο (0, 0, 0, 0):

¶x-2y+3z-5w = 0

¶x+3y-z+2w = 0

¶x-2y+2z-W = 0

¶2x+y+3z+w = 0

¶Τα συστήματα των εξισώσεων αυτού του είδους, τα οποία ισούνται με 0 (=μηδέν), είναι γνωστά ως ομοιογενή συστήματα των εξισώσεων.¶ ¶Οι λύσεις των συστημάτων των ομοιογενών γραμμικών εξισώσεων έχουν δύο πολύ σημαντικές ιδιότητες: ¶Οποιοδήποτε πολλαπλάσιο αυτής της λύσης είναι ακόμα μια λύση και το άθροισμα οποιωνδήποτε δύο λύσεων είναι μια λύση. ¶Παραδείγματος χάριν, x=2, y=5 και z=2 αποτελούν λύση της (1), όπως και τα x=4, y=10, και z=4, τα οποία προέκυψαν από τον πολλαπλασιασμό της πρώτης λύσης με το 2. Επίσης από το άθροισμα των δύο λύσεων x=2, y=5, z=2, και x=6, y=1, z=-1 ¶προκύπτουν τα x=8, y=6, και z=1 τα οποία είναι επίσης μια λύση.

Σημείωση :το ίδιο πράγμα δεν ισχύει για μια ανομοιογενή γραμμική εξίσωση. ¶Παραδείγματος χάριν, x=4, y=0, και x=0, y=2 είναι και οι δύο λύσεις στην εξίσωση x + 2y = 4, αλλά ούτε το ποσό x=4, y=2 ούτε κλιμακωτό πολλαπλάσιο x=12, y=0 δεν είναι μια λύση. ¶

¶Αυτά είναι απλά παραδείγματα που επεξηγούν τις κοινές ιδιότητες στα διανύσματα και τις λύσεις στις ομοιογενείς γραμμικές εξισώσεις: ¶προσθέτοντας ή πολλαπλασιάζοντας. ¶Κατά συνέπεια οι λύσεις των ομοιογενών συστημάτων των γραμμικών αλγεβρικών εξισώσεων έχουν το ίδιο είδος δομής με το αλγεβρικό σύστημα για τα διανύσματα που συζητήθηκαν παραπάνω. ¶

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

Αυτό το διάγραμμα έχει

σχεδιαστεί για να

παρουσιάσει το σύστημα

των δρόμων ανάμεσα στα

χωριά σε ένα νησί.

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

Mητροειδή Πολύτοπα.

Στους γεωμετρικούς όρους μητροειδή Coxeter μπορεί να οριστεί ως μητροειδή πολύτοπο . Ένα παράδειγμα είναι το επόμενο.

Τι είναι τα μητροειδή πολύτοπα; Στην παραπάνω εικόνα το Μ είναι ένα 3-διάστατό κυρτό πολύτοπο και το s είναι ο καθρέφτης της συμμετρίας της άκρης ΑΒ, έτσι ώστε η αντανάκλαση στο s να ανταλλάσσει τα σημεία Α και Β. Ένα πολύτοπο Μ (γενικά, ν - διαστάσεων) είναι μητροειδές πολύτοπο εάν όλες οι αντανακλάσεις στους καθρέφτες των συμμετριών όλων των ακρών του Μ παράγουν μια πεπερασμένη ομάδα. Στο παράδειγμά μας οι συμμετρίες των ακρών του Μ είναι συμμετρίες του κύβου C. Αλλά ένας κύβος έχει πολλές (συγκεκριμένα, 48) συμμετρίες, έτσι το Μ είναι μητροειδή πολύτοπο.

Μερικά ακόμα παραδείγματα για τα μητροειδή πολύτοπα.

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

Και ένα ακόμη μη-παράδειγμα για τα μητροειδή πολύτοπα : Στο παρακάτω παραλληλόγραμμο ABCD , το προϊόν t = rs των αντανακλάσεων στους καθρέφτες των συμμετριών των πλευρών AB και το CD είναι μια παράλληλη μετάφραση, και η ομάδα που παράγεται από το r και το s είναι άπειρη. Ως εκ τούτου ABCD δεν είναι μητροειδή πολύτοπο.

Ένας ΠΟΛΥ στοιχειώδης ορισμός.

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

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

Εάν καταλήξουμε σε πεπερασμένο σύστημα καθρεφτών, λέμε ότι το Μ είναι μητροειδή πολύτοπο.

Συμμετρικές μήτρες και συμπλεκτικά μητροειδή.

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

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

Κατόπιν κωδικοποιούμε κάθε σύνολο δεικτών ως 0,1 - διάνυσμα, έτσι ώστε {1,3} να αντιστοιχεί σε 101 και ερχόμαστε στον ακόλουθο πίνακα. Στον πίνακα θα συμπεριλάβουμε και τον "κενό ανήλικο" χωρίς τις σειρές και στήλες.

Σύνολα που αντιστοιχούν στους διαφορετικούς από το μηδέν ανηλίκους	0,1 - διάνυσμα
{1,2}
110
{2,3}
011
{1,3}	101
{1,2,3}	111
το κενό σύνολο	000

Τώρα σχεδιάζουμε τα 0,1 - διανύσματα στο ισότιμο σύστημα. Διαμορφώνουν το σύνολο te από μητροειδή πολύτοπα:

Εάν αρχίζουμε με μια λοξή συμμετρική μήτρα, όπως για παράδειγμα, με την επόμενη

ερχόμαστε σε ένα διαφορετικό είδος μητροειδών πολύτοπων: