Term
| Was ist eine Adjazenzmatrix? |
|
Definition
| Eine Adjazenzmatrix (manchmal auch Nachbarschaftsmatrix) eines Graphen ist eine Matrix, die speichert welche Knoten des Graphen durch eine Kante verbunden sind. Sie besitzt für jeden Knoten eine Zeile und eine Spalte, woraus sich für n Knoten eine [image]-Matrix ergibt. Ein Eintrag in der i-ten Zeile und j-ten Spalte gibt hierbei an, ob eine Kante von dem i-ten zu dem j-ten Knoten führt. Steht an dieser Stelle eine 0, ist keine Kante vorhanden – eine 1 gibt an, dass eine Kante existiert[1], siehe Abbildung rechts. |
|
|
Term
| Was ist eine Inzidenzmatrix? |
|
Definition
| Eine Inzidenzmatrix (auch Knoten-Kanten-Matrix) eines Graphen ist eine Matrix, welche die Beziehungen der Knoten und Kanten des Graphen speichert. Besitzt der Graph [image] Knoten und [image] Kanten ist seine Inzidenzmatrix eine [image]-Matrix. Der Eintrag in der i-ten Spalte und j-ten Zeile gibt an, ob die i-te Kante den j-ten Knoten enthält. Steht an dieser Stelle eine 1, ist eine Inzidenzbeziehung gegeben, bei einer 0 liegt keine Inzidenz vor. Es wird davon ausgegangen, dass die Knoten von 1 bis n und die Kanten von 1 bis m durchnummeriert sind. |
|
|
Term
|
Definition
f heißt surjektiv, wenn jedes Element von M das Bild eines Elements aus D
ist, kurz: f(D) = M. |
|
|
Term
|
Definition
heißt injektiv, wenn verschiedene Elemente von D auf verschiedene Elemente
von f(D) abgebildet werden, kurz:
x1 = x2 ⇒ f(x1) = f(x2) f¨ur alle x1, x2 ∈ D. |
|
|
Term
|
Definition
f heißt bijektiv, oder eins-zu-eins Abbildung, wenn f sowohl injektiv als
auch surjektiv ist. |
|
|
Term
| Formel für additives Inverses bzw. Negatives von Zm (Restklasse) |
|
Definition
Definition 3.11 Zu e ∈ Zm ist das Negative oder additive Inverse jene Zahl
d ∈ Zm, f¨ur die
e + d = 0(modm) |
|
|
Term
| Formel des Inklusion Exklusions Prinzip |
|
Definition
Satz 7.10 (Inklusions-Exklusions-Prinzip) F¨ur zwei beliebige endliche Mengen
A und B ist die Anzahl der Elemente ihrer Vereinigungsmenge gleich
|A ∪ B| = |A| + |B| − |A ∩ B|. |
|
|
Term
| Formel k-Permutation aus einer Menge mit n Elementen |
|
Definition
P(n, k) = n · (n − 1) · (n − 2) · · · (n − k + 1) =
n! /((n − k)!)
. |
|
|
Term
| Formel bei n-Permutation aus n Elementen |
|
Definition
| P(n, n) = n · (n − 1) · (n − 2) · · · 2 ·1 = n! |
|
|
Term
| Wie nennt man eine Auswahl von k-Elementen aus n Elementen ohne Beachtung der Reihenfolge? |
|
Definition
| Kombination oder eine ungeordnete Auswahl |
|
|
