Πίνακας προσπτώσεων

Στα μαθηματικά, ο πίνακας προσπτώσεων είναι ένας πίνακας που δείχνει τη σχέση ανάμεσα σε δύο κλάσεις αντικειμένων. Αν η πρώτη κλάση αντικειμένων είναι η X και η δεύτερη η Y, ο πίνακας έχει μια γραμμή για κάθε στοιχείο του της κλάσης Χ και μια στήλη για κάθε στοιχείο της κλάσης Y. Το στοιχείο της γραμμής x και της στήλης y ισούται με 1 αν x και y σχετίζονται και με 0 αν δε σχετίζονται. Υπάρχουν παραλλαγές, βλ. παρακάτω.

Θεωρία Γράφων

Πίνακες προσπτώσεων χρησιμοποιούνται κατά κύριο λόγο στη θεωρία γράφων.
Μη κατευθυνόμενοι και κατευθυνόμενοι γράφοι

Μη κατευθυνόμενος γράφος

Στη θεωρία γράφων, ένας μη κατευθυνόμενος γράφος G έχει δύο είδη πινάκων προσπτώσεων: τους προσανατολισμένους και τους μη προσανατολισμένους. Ο πίνακας προσπτώσεων (ή μη προσανατολισμένος πίνακας προσπτώσεων) του G είναι ένας \( {\displaystyle (b_{ij})} \), όπου p και q είναι οι αριθμοί των κορυφών και των ακμών αντίστοιχα , έτσι ώστε \( {\displaystyle b_{ij}=1} \) αν η κορυφή \( v_{i} \) και η ακμή \( {\displaystyle x_{j}} \) είναι προσπίπτουσες και 0 σε αντίθετη περίπτωση.

Για παράδειγμα, ο πίνακας προσπτώσεων του μη κατευθυνόμενου γράφου που φαίνεται στα δεξιά είναι ένας πίνακας που έχει 4 γραμμές (που αντιστοιχούν στις τέσσερις κορυφές, 1-4) και τέσσερις στήλες (που αντιστοιχούν στις τέσσερις ακμές, e1-e4):

\( {\displaystyle {\begin{pmatrix}1&1&1&0\\1&0&0&0\\0&1&0&1\\0&0&1&1\\\end{pmatrix}}} \)

Ο πίνακας προσπτώσεων ενός κατευθυνόμενου γράφου D είναι ένας \({\displaystyle [b_{ij}]} \) όπου p και q είναι ο αριθμός των κορυφών και των ακμών αντίστοιχα, έτσι ώστε \( {\displaystyle b_{ij}=-1} \) αν η ακμή \( {\displaystyle x_{j}} \) ξεκινάει από την κορυφή \( v_{i} \), 1 αν καταλήγει στην κορυφή \( v_{i} \) και 0 διαφορετικά. Πολλοί συγγραφείς χρησιμοποιούν αντίθετο κανόνα προσήμου.

Ο προσανατολισμένος πίνακας προσπτώσεων ενός μη κατευθυνόμενου γράφου G είναι ο πίνακας προσπτώσεων, με την έννοια των κατευθυνόμενων γράφων, οποιουδήποτε προσανατολισμού του G. Δηλαδή στη στήλη της ακμής e, υπάρχει +1 στη γραμμή που αντιστοιχεί στη μία κορυφή της e και −1 στη γραμμή που αντιστοιχεί στην άλλη κορυφή της e, και όλες οι άλλες γραμμές έχουν μηδενικά. Όλοι οι προσανατολισμένοι πίνακες προσπτώσεων του G διαφέρουν μόνο στο πρόσημο των στοιχείων κάποιων στηλών. Σε πολλές περιπτώσεις αυτή είναι μια ασήμαντη διαφορά, έτσι κάποιος μπορεί να μιλήσει για τον προσανατολισμένο πίνακα προσπτώσεων, παρόλο που κάτι τέτοιο τεχνικά είναι λανθασμένο.

Ο προσανατολισμένος ή μη προσνατολισμένος πίνακας προσπτώσεων ενός γράφου G σχετίζεται με τον πίνακα γειτνίασης του γραφήματος γραμμής του L(G) σύμφωνα με το ακόλουθο θεώρημα:

\( {\displaystyle A(L(G))=B(G)^{T}B(G)-2I_{q}\ } {\displaystyle A(L(G))=B(G)^{T}B(G)-2I_{q}\ } \)

όπου \( {\displaystyle A(L(G))} \) είναι ο πίνακας γειτνίασης του γραφήματος γραμμής του G, B(G) είναι ο πίνακας προσπτώσεων και \( {\displaystyle I_{q}} \) είναι ο μοναδιαίος πίνακας διάστασης q.

Ο πίνακας Κίρχοφ υπολογίζεται από τον προσανατολισμένο πίνακα γειτνίασης με χρήση του τύπου:

\( {\displaystyle M(G)M(G)^{T}.} \)

Προσημασμένοι και δικατευθυνόµενοι γράφοι

Ο πίνακας προσπτώσεων ενός προσημασμένου γράφου είναι μια γενίκευση του προσανατολισμένου πίνακα προσπτώσεων. Είναι ο πίνακας προσπτώσεων οποιουδήποτε δικατευθυνόμενου γράφου που δημιουργεί τον προσανατολισμό του προσημασμένου γράφου. Η στήλη μιας θετικής ακμής έχει a +1 στη γραμμή που αντιστοιχεί στη μια άκρη της ακμής και a −1 στη γραμμή που αντιστοιχεί στην άλλη άκρη, όπως και σε ακμή μη προσημασμένου γράφου. Η στήλη μιας αρνητικής ακμής έχει είτε a +1 ή a −1 και στις δύο γραμμές.
Πολυγράφοι

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

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

Ο πίνακας προσπτώσεων μιας δομής προσπτώσεων C είναι ένας p × q πίνακας [ b i j ] {\displaystyle [b_{ij}]} {\displaystyle [b_{ij}]}, όπου p και q είναι ο αριθμός των σημείων και των γραμμών αντίστοιχα, έτσι ώστε b i j = 1 {\displaystyle b_{ij}=1} {\displaystyle b_{ij}=1} αν το σημείο p i {\displaystyle p_{i}} {\displaystyle p_{i}} και η γραμμή L j {\displaystyle L_{j}} {\displaystyle L_{j}} είναι προσπίπτοντα και 0 διαφορετικά. Σε αυτήν την περίπτωση ο πίνακας προσπτώσεων είναι επίσης πίνακας γειτνίασης του γραφήματος Λέβι της δομής. Δεδομένου ότι υπάρχει ένας υπεργράφος για κάθε γράφημα Λέβι και αντίστροφα, ο πίνακας προσπτώσεων μιας δομής προσπτώσεων περιγράφει έναν υπεργράφο..

Πεπερασμένες γεωμετρίες

Μια περίπτωση τέτοιων δομών είναι η πεπερασμένη γεωμετρία. Για παράδειγμα, σε ένα πεπερασμένο επίπεδο, X είναι το σύνολο των σημέιων και Y είναι το σύνολο των γραμμών. Σε μια πεπερασμένη γεωμετρία περισσότερων διαστάσεων, X θα μπορούσε να είναι το σύνολο των σημείων και Y θα μπορούσε να είναι το σύνολο των υποχώρων διάστασης D - 1 όπου D η διάσταση του Y ή X θα μπορούσε να είναι το σύνολο όλων των υποχώρων μιας διάστασης d και Y το σύνολο όλων των υποχώρων μιας άλλης διάστασης e.
Σχεδιασμοί κατά Μπλοκ

Ένα άλλο παράδειγμα τέτοιας δομής είναι ένας σχεδιασμός κατά μπλοκ. Σε αυτήν την περίπτωση, X είναι είνα πεπερασμένο σύνολο "σημείων" και Y είναι μια κλάση υποσυνόλων του X, που ονομάζονται "μπλοκς" και τα οποία υπόκεινται σε κανόνες που εξαρτώνται από τον τύπο του σχεδιασμού. Ο πίνακας προσπτώσεων είναι ένα σημαντικό εργαλείο στη θεωρία των σχεδιασμών κατά μπλοκ. Για παράδειγμα, χρησιμοποιείται για να αποδείξει το θεμελιώδες θεώρημα των συμμετρικών 2-σχεδιασμών, ότι δηλαδή ο αριθμός των μπλοκς ισούται με τον αριθμό των σημείων.

Αναφορές

Diestel, Reinhard (2005), Graph Theory, Graduate Texts in Mathematics, 173 (3rd έκδοση), Springer-Verlag, ISBN 3-540-26183-4.
Coxeter|Coxeter, H.S.M. Regular Polytopes, (3rd edition, 1973), Dover edition, ISBN 0-486-61480-8 (Section 9.2 Incidence matrices, pp. 166–171)
Jonathan L Gross, Jay Yellen, Graph Theory and its applications, second edition, 2006 (p 97, Incidence Matrices for unidrect graphs; p 98, incidence matrices for digraphs)