IMT02

Ein graph G mit n Knoten erfüllt die Dirac-Bedingung, wenn \(δ(G) \ge \frac{n}{2}\) gilt.

\(δ(G)\) bezeichnet dabei den Minimalgrad, also den kleinsten Grad eines Knotens im Graphen G.

Es gilt: Erfüllt ein einfaacher Graph G mit \(n\ge 3\) Knoten die Dirac Bedinung, so ist G ein Haamiltonscher Graph.

• Ein zusammenhängender Graph der keinen geschlossenen Kantenzug enthält.
• Ein Baum hat weder Schlingen noch Mehrfachkanten. Zwischen zwei Knoten gibt es in Bäumen nur einen möglichen Kantenzug.
• Jeder Baum mit n Knoten hat genau n-1 Kanten.
• Hat ein Baum einen Knoten mit dem Grad k, so hat er mindestens k Blätter.
• Das Hinzufügen einer neuen Kante erstellt einen geschlossenen Kantenzug.
• Alle Kanten eines Baums sind Brücken.

Ein Graph der aus mehreren nicht zusammenhängenden Bäumen besteht.

Knoten eines Baumes mit dem Knotengrad 1

Ein Baum mit einem hervorgehobenen Knoten, der Wurzel.

Es gibt nach unten Kinder, nach oben Elternknoten sowie auf der gleichen Ebene Brüder.

Knoten in Richtung Wurzel werden als Vorgängen, von der Wurzel weg aks Nachfolger bezeichnet.

Gibt an wieviele Kinder ein Knoten maximal haben darf.

Bei einer graphischen Darstellung kann höchstens ausgelesen werden welche Ordnung der Baum mindestens hat.

• Tiefe: Die Länge eines Kantenzugs zur Wurzel.
• Niveaus: Knoten mit gleicher Tiefe werden in Niveaus zusammengefasst.
• Höhe: Gibt an wie weit der am weitestens entfernte Knoten von der Wurzel entfernt ist.
• Aufgefüllter Wurzelbaum: Alle inneren Knoten haben die höchst mögliche Anzahl an Kindern.
• Vollständiger Wurzelbaum: Hat auf jedem Niveau die höchst mögliche Anzahl an Kindern.

Ein Wurzelbaum der Ordnung 2. Knoten können maximal ein rechtes und ein linkes Kind haben.

Durchlaufen eines Baumes, es gibt drei mögliche Reihenfolgen: Preorder-, Postorder- und Inorder-Reihenfolge.

Zuerst wird die Wurzel besucht, anschließend rekursiv der linke Teilbaum des gerade besuchten Knotens, danach der rechte Teilbaum.

-> lineare Ordnung, bei der die Elternknoten vor den Kindern besucht werden.

Ein Knoten wird nach seinem linken und rechten Teilbaum besucht. Es wird mit dem Knoten ganz unten links begonnen, die Wurzel wird als letztes besucht.

->Lineare Ordnung bei der die die Elternknoten jeweils nach ihren Kindern besucht werden.

Der Knoten wird zwischen dem Durchlaufen seines linken und dem rechten Teilbaums besucht. Begonnen wird mit dem Knoten der ganz links liegt, die Wurzel wird ungefähr in der Mitte besucht, der Knoten ganz rechts wird als letztes besucht.

->lineare Ordnung bei der der Elternknoten zwischen seinen Kindern eingeordnet wird.

!Ausschließlich für Binärbäume anwendbar!

Ein Binärbaum, bei dem jeder Knoten einen Schlüssel aufweist, für die gilt:

• Jeder Schlüssel im linken Teilbaum ist kleiner als der Schlüssel im Knoten
• Jeder Schlüssel im rechten Teilbaum ist größer als der Schlüssel im Knoten.

Ein Schlüssel kennzeichnet Daten, die in einem Baum abgelegt werden sollen und ermöglicht es, dass diese Daten schnell wieder gefunden werden, da eine bestimmte Struktur bei der Speicherung verwendet wird

Ein Baum der alle Knoten eines Graphen enthält. Ein Graph enthält mindestens einen aufspannenden Baum, maximal jedoch \(n^n-2\) aufspannende Bäume.

Diese können durch herausnehmen von Kanten aus geschlossenen Kantenzügen, als destruktiv gefunden werden, oder durch aneinander hängen einzelner Kanten, bis alle Knoten an dem Baum hängen und es keinen geschlossenen Kantenzug gibt. Zwei mögliche Algorithmen zum Auffinden von aufspannenden Bäumen sind die Breitensuche und die Tiefensuche.

Der Algorithmus geht von einem Knoten alle möglichen Kantenzüge mit Länge 1 ab. Von den neu erreichten Knoten werden anschließend wieder alle Kantenzüge der Länge 1 zu noch unerreichten Knoten gewählt. Dies wird fortgesetzt bis es keine unerreichten Knoten mehr und ein aufspannender Baum gefunden ist.

Es wird versucht vom Startknoten aus einen möglichst langen Kantenzug zu finden, der möglichst tief in den Baum hinein führt. Wenn der Kantenzug nicht mehr verlängert werden kann, kehrt der Algorithmus bis zu dem Knoten zurück, von dem ein bislang unerreichter Knoten erreicht werden kann. Dies geschieht solange bis jede weitere Kante nurnoch geschlossene Kantenzüge erzeugen würde und jeder Knoten mit dem Baum verbunden ist. Anschließend terminiert der Algorithmus und ein aufspannender Baum ist gefunden.

Baum, dessen Gesamtgewicht minimal ist.

Die Suche nach einem minimal aufspannenden Baum. Dieser kann mithilfe des Algorithmus von Kruskal gefunden werden.

Bei diesem Algorithmus werden stets zunächst die Kanten gesetzt welche am günstigsten sind und keinen geschlossenen Kantenzug erzeugen. Ist eine Kante zwar als nächstgünstige an der Reihe, würde jedoch einen geschlossenen Kantenzug erzeugen, so wird sie gestrichen und nicht verwendet. Der Algorithmus terminiert sobald alle Knoten einen Kantenzug zueinander haben.

Zeilen werden zu Spalten & Spalten werden zu Zeilen

Aus einer MxN Matrix wird eine NxM Matrix

m x 1 -Matrix, als eine mit genau einer Spalte.

Werden mit kleinem Buchstaben mit darüber stehendem Pfeil gekennzeichnet.

1 x n -Matrix, also mit genau einer Zeile.

Entsteht als Transposition eines Spaltenvektors und wird entsprechend mit kleinem Buchstaben mit drüberstehendem Pfeil und dem Transpositions-t gekennzeichnet.

m x n-Matrix deren Elemente alle gleich null sind wird als 0 bezeichnet. Entsprechend gibt es auch Nullvektoren.

Diejeniger Diagonale eine m x n-Matrix, deren Elemente mit dem gleichen Zeilen- und Spaltenindex gebildet werden.

Für m < n sind dies a₁₁... a_mm, für m > n sind es a₁₁ ... a_nn.

Eine Matrix bei der alle Elemente außerhalb der Hauptdiagonale gleich Null sind, bei der also gilt d_ij = 0 für alle i != j

(Die Nullmatrix ist eine spezielle Diagonalmatrix.)

Jede Diagonalmatrix ist sowohl eine obere als auch eine untere Dreiecksmatrix.

eine m x n-Matrix, deren Elemente oberhalb oder unterhalb der Hauptdiagonale alle gleich null sind.

Es gibt eine obere (rechte, alle Elemente unterhalb gleich null / a_ij = 0 für alle i > j),

oder eine untere (linke, alle Elemente oberhalb gleich null a_ij = 0 für alle i < j) Dreiecksmatrix.

Matrizen die nur in der Umgebung der Hauptdiagonale Elemente ungleich null besitzen.

Eine Matrix von der Ordnung n x n, oder anders formuliert eine m x n-Matrix bei der gilt m = n.

Zeilen- und Spaltenzahl sind identisch, die Hauptdiagonale verläuft von der linken oberen zur rechten unteren Ecke.

 EIne Diagonalmatrix, deren HAuptdiagonalelemente alle gleich 1 sind. Die n x n-Einheitsmatrix wird mit E bezeichnet und auch Einheitsmatrix n-ter Ordnung genannt. Ihre Vektoren nennt man Einheitsvektoren.

Sie werden elementweise addiert / subtrahiert und müssen gleichförmig sein.

c_ij = a_ij + b_ij

• Kommutativgesetz: A + B = B + A
• Assoziativgesetz: A + (B + C) = (A + B) + C
• DIe Nullmatrix ist das neutrale Element bei Matrixaddition/ -subtraktion: A + 0 = 0 + A = A
• A - A = 0

Diese ist gegeben falls A = A^T ist. Ist A = -A^T ist die quadratische Matrix scchiefsymmetrisch. (Eine schiefsymmetrische Matrix darf daher in der Hauptdiagonae nur Nullen haben.

Jede beliebige Matrix A kann als Summe einer symmetrischen Matrix B und einer schiefsymmetrischen Matrix C als A = B + C dargestellt werden.

B ergibt sich aus: \(B = 1/2 * (A+A^T)\)B = 1/2 * (A + A^T)\(B = 1/2 * (A + A^T)\)

C aus: 1/2 * (A - A^T)

DIe Multiplikation einer Matrix mit einem Skalar. Jedes Element der Matrix muss hierfür mit dem Skalar multipliziert werden. Das neutrale Element im Bezug auf die Skalarmultiplikation ist die 1.

• Asssoziativgesetz: (a * b) *A = a * (b * A)
• Distributivgesetz: (a + b) * A = a * A + b * A

Die Gesetze gelten für alle m x n-Matrizen und beliebiige Skalare.

Multiplikation eines Zeilenvektors a^T mit einem Spaltenvektor b. Das Ergebnis ist eine reelle Zahl.

Es gilt: a₁b₁+a₂b₂+ ... + a_nb_n

_{Voraussetzung ist dass die Vektoren aus gleich vielen Elementen bestehen.}

• a^T * a >= 0. Aus a^T * a = 0 folgt das a der Nullvektor ist.
• 0^T * a = 0
• Kommutativgesetz: a^T * b = b^T * a
• Homogenität: (skalar * a^T) * b = skalar * (a^T * b)
• Distributivgesetz: (a^T + b^T) * c = a^T * c + b^T * c

• (A^T)^T = A
• (A + B)^T = A^T + B^T
• (skalar * A)^T = skalar * A^T
• (A * B)^T = B^T * A^T
• E^T = E