IMT02
Mathematik für Wirtschaftsinformatiker 2
Mathematik für Wirtschaftsinformatiker 2
-
- 1 / 121
-
Lernkarten
Radgraph Wn?
Kombination aus Kreisgraph und Sterngraph. Kreisgraph mit zentralem Knoten, wobei alle Knoten des Kreises eine Kante mit dem zentralen Knoten haben.
Vollständiger Graph Kn?
Ein ungerichteter einfacher Graph mit n Knoten, wobei von Knoten zu jedem anderen Knote eine Kante existiert.
Besonderheiten der vollständigen Graphen?
- Alle vollständigen Graphen Kn sind eulersch für alle ungeraden n.
- Alle Kn mit n > 6 haben K5 als Teilgraph.
- K3 = C3
- K4 ist isomorph zu W4
Anzahl an Kanten in einem vollständigeen Graphen?
\(\frac {n*(n-1)} {2}\)
Bipartiter Graph?
Ein graph ist bipartit wenn sich seine Knotenmenge in zwei disjunkte, nichtleere Teilmengen M und N aufteilen lässt, sodass es nur Kanten zwischen Knoten aus M und Knoten aus N, aber keine Kanten innerhalb der Mengen M und N.
Der Graph muss nicht zusammenhängend sein.
Er muss mindestens zwei Knoten haben und darf keine Schlingen haben.
Wie nennt man die Knotenteilmengen eine bipartiten Graphen?
Bipartitionen
Welche Graphen sind bipartit?
- Alle Kreisgraphen mit gerader Knotenzahl.
- Ein Graph ist genau dann bipartit, wenn er keinen geschlossenen Kantenzug mit ungerader Länge enthält.
Vollständig bipartiter Graph?
Ein einfacher bipartiter Graph, in dem alle möglichen Kanten vorhanden sind.
Die Kantenanzahl eines vollständig bipartiten Graphen lässt sich wie folgt berechnen:
\(|M| = m; |N| = n\)
\(m * n = Kantenanzahl\)
Ein vollständig bipartiter Graph ist eulersch, wenn sowohl m als auch n gerade sind.
Alle Sterngraphen sind vollständig bipartite Graphen.
Satz von Kuratowski?
Ein Graph G ist genau dann planar, wenn G keinen Teilgraphen G' enthält, sodass K5 oder K3,3 ein Minor von G' ist.
Minor?
Ein Graph G1 wird Minor des Graphen G2 genannt, falls G1 isomorph zu einem durch Knotenverschmelzung entstandenen Teilgraphen von G2 ist.
Hamiltonscher Kreis?
Ein geschlossener Kantenzug, der jeden Knoten eines Graphen genau einmal enthält.
Er geht durch jeden Knoten, braucht aber nicht zwangsläufig jede Kante.
Hamiltonscher Graph?
Ein Graph der einen Hamiltonschen Kreis enthält.
Hamiltonscher Weg?
Ein Kantenzug der jeder Knoten genau einmal enthält, aber nicht geschlossen ist.
Semi-Hamiltonscher-Graph?
Ein Graph der einen Hamiltonschen-Weg enthält.
Besondere Graphen im Bezug auf Euler & Hamilton
- Weggraphen sind nicht eulersch und nicht hamiltonsch.
- Kreisgraphen sind eulersch und hamiltonsch
- Sterngraphen sind nicht eulersch und nicht hamiltonsch
- Radgraphen (n > 3) sind nicht eulersch aber hamiltonsch
- Vollständige Graphen sind für ungerade n eulersch, für gerade n nicht eulersch und für n > 2 hamiltonsch
- Das Haus der Nikolaus ist nicht eulersch, aber hamiltonsch.
Eigenschaften eines Hamiltonschen Graphen?
- Er ist zusammenhängend
- Es gibt einen isomorphen Graphen, sodass alle Knoten auf einer Kreislinie liegen, die nicht benötigten Kanten sind Diagonalen oder evtl. Schlingen.
- Er lässt sich nicht durch einen Schnitt in zwei Teile teilen.
- Werden aus einem Hamiltonschen Graphen n Knoten entfernt und mit ihnen alle zugehörigen Kanten, so zerfällt er in höchstens n zusammenhängende Teilgraphen.
Brücke?
Eine Kante durch deren entfernen der Graph in zwei Teilgraphen zerfällt.
Obergrenze für die Anzahl an Hamiltonschen Kreisen?
Ein einfacher Graph mit n Knoten hat höchstens \(\frac{(n-1)}{2}\)Hamiltonsche Kreise.
Besonderheiten bei bipartiten hamiltonschen Graphen?
Darf keine ungerade Anzahl an Knoten haben und beide Knotenmengen müssen gleichmächtig sein.
Vorgehensweise um in einem Hamiltonschen Graphen einen Hamiltonschen Kreis zu zeichnen?
- Wenn ein Knoten passiert wird, werden alle nicht benutzten Kanten gestrichen.
- In diese Weise darf kein Knoten entstehen der den Grad 1 hat.
- Es dürfen desweiteren keine Teilgraphen abgespalten werden, die mit dem übrigen Graphen nicht zusammenhängen.
Ore-Bedingung?
Ein Graph G mit n Knoteen erfüllt die Ore Bedingung, wenn für alle Paare {u, v} nichtadjazenter Knoten u und v in G gilt: \(δ(u) + δ(v) \ge n\)
\(δ(v)\) bezeichnet den Grad eines Knoten v
Ein Graph der keine nicht adjazenten Knoten besitzt erfüllt die Ore-Bediungung.
Es gilt: Erfüllt ein einfacher Graph G mit \(n \ge 3\) Knoten die Ore Bedingung, so ist G ein Hamiltonscher Graph.
Dirac-Bedingung?
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.
Baum?
- 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.
Waldgraph?
Ein Graph der aus mehreren nicht zusammenhängenden Bäumen besteht.
Blatt?
Knoten eines Baumes mit dem Knotengrad 1
Wurzelbaum?
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.
Ordnung eines Wurzelbaums?
Gibt an wieviele Kinder ein Knoten maximal haben darf.
Bei einer graphischen Darstellung kann höchstens ausgelesen werden welche Ordnung der Baum mindestens hat.
Besondere Begriffe im Bezug auf Wurzelbäume?
- 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.
Binärbaum?
Ein Wurzelbaum der Ordnung 2. Knoten können maximal ein rechtes und ein linkes Kind haben.
Traversierung?
Durchlaufen eines Baumes, es gibt drei mögliche Reihenfolgen: Preorder-, Postorder- und Inorder-Reihenfolge.
Preorder-Reihenfolge ( Hauptreihenfolge?)
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.
Postorder-Reihenfolge (Nebenreihenfolge)?
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.
Inorder-Reihenfolge (symmetrische Reihenfolge)?
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!
Binärer Suchbaum?
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.
Schlüssel (Binärbaum)?
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
Aufspannender Baum?
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.
Breitensuche?
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.
Tiefensuche?
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.
minimal aufspannender Baum?
Baum, dessen Gesamtgewicht minimal ist.
Problem der günstigsten Verbindung
Die Suche nach einem minimal aufspannenden Baum. Dieser kann mithilfe des Algorithmus von Kruskal gefunden werden.
