IMT02
Mathematik für Wirtschaftsinformatiker 2
Mathematik für Wirtschaftsinformatiker 2
-
- 1 / 121
-
Lernkarten
Berechnungs der Inversen einer Matrix?
Mithilfe einer Variation des Gauß-Algorithmus:
Matrix mit Einheitsmatrix auf der rechten Seite bilden, mithilfe der erlaubten Operationen so umformen, dass auf der linken Seite die Einheitsmatrix entsteht. Die rechte Seite zeigt nun die Inverse Matrix.
Wenn während der Umformung eine Nullzeile in der linken Seite entsteht besitzt diese keine Inverse Matrix.
Elemente eines ungerichteten Graphen?
- Kanten ( E, edges) / Bögen
- Knoten (V, vertices) / Ecken
Einfacher Graph?
Ein Graph ohne Mehrfachkanten oder Schlingen
Endlicher Graph?
Graph mit einer endlichen Anzahl von Knoten und Kanten.
Formale Definition eines ungerichteten Graphen?
Der ungerichtete Graph G = (V,E) ist ein Paar der endlichen Knotenmenge V = { 1,...,n} mit der endlichen Kantenmenge E = {e1,...,em}. V ist dabei nicht die leere Menge, d.h. es gibt mindesten einen Knoten. Desweiteren ist eine Inzidenzabbildung Φ gegeben, die jeder Kante e ∈ E eine Menge mit einem Knoten e -> {i} (Schlinge) oder zwei Knoten, es -> {i,j}, i, j ∈ V zuordnet.
Da der Graph ungerichtet ist, ist die Reihenfolge der Knoten in der Inzidenzabbildung egal.
isolierter Knoten?
Ein Knoten der nicht mit anderen verbunden ist.
Nicht zusammenhängender Graph?
Ein Graph der aus mehreren Teilen besteht.
benachbarte Knoten?
Knoten (i, j) die über eine Kante (e) miteinander verbunden sind. (adjazente Knoten)
e ist inzident zu i, j
Eine Schlinge macht einen Knoten zu seinem eigenen Nachbarn.
Knotengrad?
(auch Valenz genannt und als δ(v) bezeichnet)
gibt die Anzahl der in v zusammenlaufenden Kanten an.
Was gilt für einen Graphen?
- Die Summe aller Knotengrade eines Graphen ist stets gerade. (Handschlaglemma)
- In jedem Graphen ist die Summe aller Knotengrade doppelt so groß wie die Summe der Kanten.
- In jedem einfachen Graphen gibt es mindestens zwei Knoten, die den gleichen Grad haben.
Isomorpher Graph?
Zwei Graphen sind isomorph, wenn der eine Graph durch Umzeichung des anderen Graphen zu erhalten ist. Hierfür drüfen die Knoten beliebig verschoben und die Kanten gebogen, gedehnt oder zusammengezogen werden.
Formaler gilt: Seien G1 = (V1,E1) und G2 = (V2,E2) zwei Graphen ohne Mehrfachkanten. Die Graphen heißen isomorph, wenn es eine bijektive Abbildung θ : V1 -> V2 gibt, sodass {i, j] ∈ E1 <-> { θ(i), θ(j)} ∈ E2 für alle i, j ∈ V1 gilt. D.h. jeder Kante {i, j} in G1 die Kante {θ(i), θ(j)} in G2 und umgekehrt.
Regulärer Graph?
Ein Graph in dem jeder Knoten den gleichen Grad hat. (z.B. der Petersen Graph), zusätzlich kann auch der Grad angegeben werden. Dann sagt man Graph regulär vom Grad g.
Planarer Graph?
Ein Graph ist planar oder plättbar, wenn er eine isomorphe Darstellung besitzt die kreuzungsfrei in der Ebene gezeichnet werden kann. Zu den durch den Graphen geteilten Flächen gehört auch die unbegrenzte Flächen außen.
Eulersche Formel?
(Anzahl der Knoten) - (Anzahl der Kanten) + (Anzahl der Flächen) = 2
Diese Formel gilt für jeden planaren Graphen.
Teilgraph?
Ein Teilgraph besteht G2 besteht ausschließlichen aus Elementen (Kanten und Knoten) eines Graphen G1.
Adjazenmatrix?
Darstellung eines Graphen durch eine Matrix.
Besonderheiten einer Adjazenmatrix sind:
- Die Adjazenmatrix eines ungerichteten Graphen ist immer symmetrisch, weil eine Kante immer sowohl rein- als auch rausgehend zu werten ist.
- G ist dann ein einfacher Graphe wenn alle Element der Hauptdiagonale gleich null sind.
- DIe Summe des i-ten Zeilenvektors gibt den Knotengrad des Knoten i an.
- Die Summe aller Elemente der Adjazenmatrix ist gleich der doppelten Kantenzahl.
- Bei zwei isomorphen Graphen ergibt sich bei entsprechender Nummerierung der Knoten zweimal die gleiche Adjazenmatrix.
Gerichteter Graph?
Wird auch als Digraph bezeichnet, ist ein Graph in dem jede Kante eine Richtung / Orientierung hat.
Bei der Inzidenzabbildung ist es nun wichtige die korrekte Reihenfolge der Knoten anzugeben, um tatsächlich eine Inzidenzabbildung des Digraphen zu erstellen. Φ -> (i,j) Es handelt sich also um ein Knotepaar, nicht wie zuvor eine Knotenmenge.
Bei einem Digraphen haben die Knoten jeweils einen Eingangs- und einen Ausgangsgrad, entsprechend ist die Adjazenmatrix eines Digraphen nicht mehr symmetrisch.
Gegenteil paralleler Kanten? (Knoten mit demselben Starknoten und demselben Endknoten)
Antiparallel, bzw gegenläufige Kanten
e1 = (i,j); e2 = (i,j) parallel
e3 = (i,j); e2 = (j,i) gegenläufig / antiparallel
Schatten von D?
DIe Darstellung eines Digraphen als ungerichteter Graph, indem gegenläufige Kanten durch eine ungerichtete Kante getauscht werden und mit den übrig verbleibenden gerichteten Kanten ebenso verfahren wird.
Umgekehrt kann aus einem Ungerichteten Graph ein Digraph erstellt werden, indem jede Kante durch zwei gegenläufige Kanten ersetzt wird.
Besonderheiten der Adjazenmatrix eines Digraphen?
Sie muss nicht zwangsläufig symmetrisch sein.
Die Summe des Zeilenvektors gibt den Ausgangsgrad, die Summe des Spaltenvektors den Eingangsgrad des entsprechenden Knoten.
Isomorphie von Digraphen?
Bei der Isomorphie von Digraphen ist zusätzlich bedeutsam, dass die Richtung der Kanten übereinstimmt.
Gewichteter Graph?
In diesem wird jeder Kante ein Gewicht zugeordnet und sie können sowohl ungerichtet als auch gerichtet sein.
Gewichtsfunktion c?
Kostenfunktion oder Bewertungsfunktion, definiert als c: E -> |R mit c({i,j}) = cij im ungerichteten, bzw. c((i,j)) = cij im Digraph.
Gewichtsmatrix?
Eine Matrix in die die Gewichte der Kanten eingetragen werden.
Die Hauptdiagonale besteht aus nullen. Sind Knoten nicht benachbart verwendet man ein "∞". Bei benachbarten Knoten wird in die Matrix das Gewicht der verbindenden Kante eingetragen.
In einem ungerichteten Graphen ist die Gewichtsmatrix symmetrisch, bei einem Digraphen muss dies nicht der Fall sein.
Algorithmus von Dijkstra?
Kann in einem gewichteten einfachen Digraphen mit nichtnegativen Gewichten die kürzesten Wege von einem Startknoten zu allen anderen Knoten bestimmen.
Kantenzug?
Folge von inzidenten Knoten und den zugehörigen aneinder stoßenden Kanten.
Formal definiert: Sei G = (V, E) ein Graph mit der Knotenmenge V = {v1, v2, ... vn}, n > 1 und der Kantenmenge E = { e1, e2, ..., em}, dann heißt eine endliche Folge (v1, e1, v2,e2, v3, ..., es-1, vs) mit ϕ(ek) = {vk, vk+1} bi einem ungerichteten Graphen, bzw ϕ(ek) = (vk, vk+1) bei einem gerichteten Graphen, Kantenzug.
Falls wwieder an den Ausgangsknoten zurückgekehrt wird handelt es sich um einen geschlossenen Kantenzug, andernfalls ist er offen. Die Anzahl der durchlaufenen Knoten gibt die Länge des Kantenzugs an.
Wann heißt ein Digrapg zusammenhängend?
Wenn sein zugrunde liegender ungerichteter Graph, der Schatten DS, zusammenhängend ist. Dies heißt jedoch nicht das zwei über einen gerichteten Kantenzug innerhalb des Digraphen erreicht werden können.
Stark zusammenhängender Digraph?
Ein Digraph ist genau dann stark zusammenhängend wenn zu je zwei Knoten u und v aus der Knotenmenge V ein gerichteter Kantenzug von u nach v und v nach u existiert.
Eigenschafen eines Kantenzug um ein Eulerscher Kreis zu sein?
- Es sind keine doppelten Kanten enthalten.
- Der Kantenzug enthält alle Kanten des Graphen.
- Anfang und Ende des Kantenzugs stimmen überein, er ist also geschlossen.
Der Graph ist ein Eulerscher Graph wenn alle diese Bedingungen erfüllt sind.
Eigenschaften eines Eulersche Wegs?
Ein Kantenzug ist dann ein Eulerscher Weg, wenn:
- Der Kantenzug keine Kante doppelt enthält.
- Der Kantenzug sämtliche Kanten des Graphen enthält.
Im Gegensatz zum Eulerschen Kreis muss hierbei nicht zum Ausgangsknoten zurückgekehrt werden.
Wann ist ein zusammenhängender Graph eulersch?
Wenn der Grad eines jeden Knoten gerade ist.
Wann existiert in einem zusammenhängenden Graphen ein Eulerscher Weg?
Es existiert genau dann ein Eulerscher Weg, wenn der Graph genau 2 oder keinen Knoten mit ungeradem Grad enthält.
Falls 2 existieren sind diese Start und Endpunkt der eulerschen Weges des Graphen.
Lösung bei nicht Vorhandensein eines eulerschen Weges/Kreises?
In jedem zusammenhängenden Graphen gibt es einen geschlossenen Kantenzug der jede Kante genau zwei mal enthält.
Bedingung für Eulersche Kreise / Wege bei gerichteten Graphen?
Eulerscher Kreis:
Ein Digraph ist genau dann eulersch, wenn er stark zusammenhängend ist und es für jeden Knoten gilt, daass der Eingangsgrad gleich dem Ausgangsgrad ist.
Algorithmus von Hierholzer?
Dieser dient zum Auffinden eines Eulerschen Kreises in einem Eulerschen Graphen.
Es wird zunächst ein geschlossener Kantenzug erstellt. Sollte dieser noch keine Eulerscher Kreis sein werden von einem Knoten mit unbesuchten Kanten ausgehend solange neue geschlossene Kantenzüge erstellt bis alle Kanten besucht wurden. Anschließend können aller gefundenen geschlossenen Kantenzüge zu einem Eulerschen Kreis zusammengefasst werden.
Briefträgerproblem?
Kantenorientierte Toureprobleme in gewichteten Graphen
-> Es müssen alle Kanten genutzt werden, und ein möglichst geringes Gesamtgewicht des Kantenzug erreicht werden.
Optimale Lösung des Briefträgerproblems?
Der Eulersche Kreis, weil dieser wie gefordert jede Kante einmal enthält, aber keine zusätzlichen.
Ist dies nicht möglich wird mithilfe des Algorithmus von Dijkstra die kürzeste Verbindung zwischen Knoten mit ungerade Graden ermittelt und die Kanten welche auf dieser Verbindung liegen werden verdoppelt. Ist dies mit allen ungeraden Knoten geschehen ist der Graph nun ein eulerscher Graph und der Eulersche Kreis ist die optimale Lössung des Problems.
Weggraph Pn?
Graph mit n-1 Kanten, zwei Knoten mit Grad 1, alle anderen mit Grad 2. Eine Linie.
Kreisgraph Cn?
Knotenzahl = Kantenzahl. Alle Knotengrade = 2. Knoten sind in einem Kreis miteinander verbunden.
Sterngraph Sn?
Ein zentraler Knoten der mit allen anderen durch eine Kante verbunde. ist. Er hat n-1 Kanten.
