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

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

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

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

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

Στη θεωρία γράφων, ένας μη κατευθυνόμενος γράφος *G* έχει δύο είδη πινάκων προσπτώσεων: τους προσανατολισμένους και τους μη προσανατολισμένους.
Ο  **πίνακας προσπτώσεων** (ή **μη προσανατολισμένος πίνακας προσπτώσεων**) του *G* είναι ένας *p* &times; *q* πίνακας (b_{ij}), όπου *p* και *q* είναι οι αριθμοί των κορυφών και των ακμών αντίστοιχα , έτσι ώστε b_{ij} = 1 αν η κορυφή v_i και η ακμή x_j είναι προσπίπτουσες  και 0 σε αντίθετη περίπτωση. 

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


Ο **πίνακας προσπτώσεων** ενός κατευθυνόμενου γράφου *D* είναι ένας *p* &times; *q* πίνακας [b_{ij}] όπου *p* και *q* είναι ο αριθμός των κορυφών και των ακμών αντίστοιχα, έτσι ώστε b_{ij} = -1 αν η ακμή x_j ξεκινάει από την κορυφή v_i, 1 αν καταλήγει στην κορυφή v_i και 0 διαφορετικά.  Πολλοί συγγραφείς χρησιμοποιούν αντίθετο κανόνα προσήμου.

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

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

:
A(L(G)) = B(G)^{T}B(G) - 2I_q\ 


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

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

:
M(G) M(G)^{T}. 


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

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

### Πολυγράφοι

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

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

## Δομές προσπτώσεων

Ο **πίνακας προσπτώσεων** μιας δομής προσπτώσεων *C* είναι ένας *p* &times; *q* πίνακας [b_{ij}], όπου *p* και *q* είναι ο αριθμός των  **σημείων** και των **γραμμών** αντίστοιχα, έτσι ώστε b_{ij} = 1 αν το σημείο p_i και η γραμμή L_j είναι προσπίπτοντα και 0 διαφορετικά. Σε αυτήν την περίπτωση ο πίνακας προσπτώσεων είναι επίσης πίνακας γειτνίασης του γραφήματος Λέβι της δομής. Δεδομένου ότι  υπάρχει ένας υπεργράφος για κάθε γράφημα Λέβι και *αντίστροφα*, ο πίνακας προσπτώσεων μιας δομής προσπτώσεων περιγράφει έναν υπεργράφο..

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

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

### Σχεδιασμοί κατά Μπλοκ

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

## Αναφορές
*.
* 
* 

## Παραπομπές


 


Κατηγορία:Θεωρία γράφων