Graph

Graph G(V, E) - Graph, welcher aus der Knoten- und Kantenmenge V und E besteht.
Knoten v - Element aus V, der Menge der Knoten (v V)
Kante e - Element aus E, der Menge der Kanten (e E)

ungerichteter Graph

E { {i,j} : i V, j V, i j }

gerichteter Graph

E { (i,j) : i V, j V }

Nachbarschaft

G = (V, E): gerichteter Graph.
Zwei Knoten i, j V heien benachbart, wenn eine Kante
zwischen ihnen verluft, also (i, j) E oder (j, i) E.
Schleife : Eine Kante (i, i) mit identischem Ausgangs- und Endknoten

Grad

GradG(v) = |{e(i, j) E : v = i v = j}|
Da jede Kante genau zwei Knoten verbindet ist die Summe aller
Knotengrade = 2|E|(Anzahl der Kanten)

Eingangsgrad

GradIN(v) = |{e(i, j) V : v = j}|

Ausgangsgrad

GradOUT(v) = |{e(i, j) V : v = i}|

Darstellung

Abstrakt

Sei G1(V1, E1)
V1 = {a, b, c, d}
E1 = { (a,b), (a,c), (a,d), (b,b), (b,c), (d,b), (d,c) }

graphisch

Adjazenzliste

Adjazenzmatrix

Weg

Weg in G ist ein Tupel (v0, v1, ..., vk), so dass fr alle i mit 0 i < k gilt:
(vi, vi+1) E fr gerichtete Graphen
{vi, vi+1} E fr ungerichtete Graphen
Das Tupel (v0, v1, ..., vk) wird dann ein Weg von v0 nach vk
genannt. k ist die Lnge des Weges. k gibt also an, wie viele Kanten auf dem Weg durchlaufen werden.

einfach

kein Knoten kommt mehr als einmal in dem Weg vor
Kreis heit einfach, wenn keine Kante mehrfach durchlaufen wird und ( abgesehen von Start- und Endknoten ) kein Knoten mehr als einmal in dem Weg vorkommt

azyklisch

Ein Graph heit azyklisch, falls er keinen einfachen Kreis enthlt.

zusammenhngend

ungerichteter Graph
G ist zusammenhngend, wenn fr alle Knoten v, w V gilt: Es
gibt einen Weg von v nach w.

stark zusammenhngend

gerichteter Graph
G ist stark zusammenhngend, wenn fr alle Knoten v, w V gilt: Es gibt einen Weg von v nach w.

Hamilton

Weg

Ein Weg W = (v0, ..., vk) ist ein Hamilton-Weg wenn jeder Knoten aus V genau einmal in W vorkommt

Kreis

Ein Weg W = (v0, ..., vk) ist ein Hamilton-Kreis wenn k > 1 und v0 = vk und (v0, ..., vk-1) ein Hamilton-Weg ist

Euler

ungerichteter Graph

Weg

Ein Weg W = (v0, ..., vk) ist ein Euler-Weg wenn W jede Kante aus E genau einmal durchluft. D.h. fr jedes e E genau ein

i {0, ..., k1} gibt, so dass e = {vi, vi+1}

Kreis

Ein Weg W = (v0, ..., vk) ist ein Euler-Kreis wenn W ein Euler-Weg ist und v0 = vk.

isomorph

Zwei Graphen G1= (V1, E1) und G2= (V2, E2) heien isomorph, wenn sie sich hchstens in der Bezeichnung ihrer Knoten
unterscheiden, ansonsten aber die selbe Struktur haben.

bijektive Funktion

f: V1V2 existieren, mit den Eigenschaften:
falls G1 und G2 gerichtete Graphen sind:
(u, v) E1 (f(u), f(v)) E2
falls G1 und G2 ungerichtete Graphen sind:
{u, v} E1 {f(u), f(v)} E2

planar

wenn sich in der graphischen Darstellung keine zwei Kanten berkreuzen

gewichtet

eine Funktion, welche jeder Kante in G eine reelle Zahl (das Gewicht) zuordnet.
d: E

Bume

ungerichteter Baum B

B ist ein ungerichteter, zusammenhngender Graph G = (V, E), der keinen einfachen Kreis enthlt.
Es existiert genau ein einfacher Weg, der die Knoten x und y
verbindet.

Spannbume