Modell Teil 2

Reihenfolge der Endpunkte egal —> (u,v) = (v,u)

Gleicher Endpunkt (u,u)

• im ungerichteten Fall zwei Knoten durch mehr als eine Kante verbunden

• im gerichteten Fall mind. zwei Kanten den gleichen Vorgänger und Nachfolger

ein Graph ohne Schlingen und kein Multigraph

• ungerichteter Fall —> zwischen unterschiedlichen Knoten existiert immer eine Kante

• gerichteter Graph —> zwischen unterschiedlichen Knoten eine Kante in jede Richtung

• Jeder Kante wird ein Gewicht zugeordnet

• Wenn mind. eine Kante einen neg. Wert hat —> neg. gewichteter Graph

• Aufteilung der Knotenmenge in V1 und V2

• Jede Kante hat genau einen Endpunkt in V1 und V2

Jeder Knoten aus V1 mit jeden Knoten aus V2 verbunden

Färbungsalgorithmus

Abbruchbedingung

???

Handlungsabfolgen, z.B Schleife bis Stoppkriterium

Landau Notation —> O(n), n ist linear (n), polynominiell (z.B. n^2) oder exponentiell (2^n)

• Für gewichtete Graphen G = (V,E,w), kein Multigraph

• Für alle Knotenpaar (u,v) ∉ E, sei w(u,v) = ∞

• Adjaszenzmatrix von G: = w(1,1) w(1,2) w(1,n)

  w(2,1) w(2,2) w(2,n)

  w(n,1) w(n,2) w(n,n)

• Grad ∂(v) ist die Anzahl der Kanten, die v als Endknoten haben (ungerichteter Graph)

• ∂(v) = ∂⁺(v) + ∂⁻(v) , ∂⁺(v) = Anzahl ausgehender Kanten und ∂⁻(v) = Anzahl eingehender Kanten

• ∂⁺⁻(v) = ∂⁺(v) - ∂⁻(v) , ∂⁺(v) Differenz ausgehender und eingehender Kanten eines Knotens

Eine endliche Folge von Knoten, bei der jeweils zwei aufeinander folgende Knoten Nachbarn (Vorgänger / Nachfolger) sind

Kantenzug, bei dem alle Knoten verschieden sind (Ausnahme sind Anfangs- und Endknoten)

Kantenzug mit identischen Anfangs- und Endknoten

Zwischen jedem Knoten existiert ein Weg (ungerichteter Graph)

ungerichtetes Pendant zusammenhängend (gerichteter Graph)

Zwischen jedem Knotenpaar existiert ein Weg (gerichteter Graph)

L(u,v)≤dG(u,v) (A*-Algorithmus)

Ein gerichteter Graph G(V,E) mit nicht negativen Kantengewichten und einer zweiten Kantengewichtung c, die jeder Kante einen nicht negativen Wert zuordnet. Dann muss eine Quelle s & eine Senke t gegeben sein.