Mathematische Grundlagen

Graph

 English version  aufwärts

Knoten und Kanten

Definition:  Ein (gerichteter) Graph ist ein Paar G = (V, E), hierbei ist V eine endliche Menge von Knoten und E enthalten in V × V eine Relation auf V, die Menge der Kanten.

In der grafischen Darstellung des Graphen werden die Knoten als Punkte oder Kreise gezeichnet, die Kanten als Pfeile, wobei ein Pfeil vom Knoten u Element V zum Knoten v Element V zeigt, wenn (u, vElement E.

Beispiel:  G = (V, E)   mit   V = {0, 1, 2, 3, 4}   und
E = {(0,1), (0,2), (3,0), (2,0), (1,2)}

Bild 1: Darstellung des Graphen G
Bild 1: Darstellung des Graphen G

Definition:  Sei G = (V, E) ein Graph und (u, vElement E eine Kante von Knoten u nach Knoten v. Dann ist v direkter Nachfolger von u und u direkter Vorgänger von v.

Der Ausgangsgrad o(u) eines Knotens u ist gleich der Anzahl seiner direkten Nachfolger, d.h.

o(u)  =  | { w |  (u, wElement E } |.

Der Eingangsgrad i(u) eines Knotens u ist gleich der Anzahl seiner direkten Vorgänger, d.h.

 i(u)  =   | { v |  (v, uElement E } |.

Ein Knoten u heißt isoliert wenn  o(u) = i(u) = 0  gilt.

Eine Kante (u, u) von einem Knoten u zu sich selbst heißt Schlinge.

Beispiel:  In G ist Knoten 0 direkter Nachfolger von Knoten 3; Knoten 2 hat den Ausgangsgrad 1 und den Eingangsgrad 2. Knoten 4 ist isoliert. G hat keine Schlingen.

Pfad

Definition:  Ein Pfad (oder Kantenzug) in einem Graphen ist eine endliche Folge von Kanten

p  =  (u0, v0) ... (um-1, vm-1)

mit   m Element natürliche Zahlen0   und   vi-1 = ui   für alle   i Element {1, ..., m-1}.

Hierbei ist m die Länge des Pfades. Wir identifizieren Kanten und Pfade der Länge 1. Der Pfad der Länge 0 heißt der leere Pfad, wir bezeichnen ihn mit λ. Der Knoten u0 heißt Anfangs­knoten von p, der Knoten vm-1 heißt Endknoten. Alle anderen Knoten von p heißen innere Knoten.

Beispiel:  Pfade in obigem Graphen G sind

p1 = (3,0) (0,2) (2,0) (0,2)

p2 = (0,1) (1,2) (2,0)

p3 = (3,0)

p4 = (3,0) (0,1) (1,2) (2,0)

Der Pfad p1 hat die Länge 4, der Pfad p3 hat die Länge 1. Im Pfad p2 ist der Knoten 0 zugleich Anfangs- und Endknoten. In p4 ist Knoten 0 sowohl innerer Knoten als auch Endknoten.

Definition:  Sei  p = (u0, v0) ... (um-1, vm-1)  ein Pfad in einem Graphen G.

p heißt einfach, wenn er keine Kante mehrfach durchläuft, d.h. wenn alle (ui, vi) paarweise verschieden sind (i = 0, ..., m-1).

p heißt Zyklus, wenn er geschlossen ist, d.h. wenn  vm-1 = u0  gilt.

p heißt Weg, wenn er keinen Knoten mehrfach durchläuft, d.h. wenn alle ui unter­einander und alle vj unter­einander paarweise verschieden sind (i, j = 0, ..., m-1).

p heißt Kreis, wenn er ein Weg ist und geschlossen ist, d.h. ein Zyklus ist.

Beispiel:  Der Pfad p1 aus dem vorigen Beispiel ist kein einfacher Pfad, weil er die Kante (0,2) zweimal enthält. Der Pfad p4 ist ein einfacher Pfad, aber kein Weg, weil er den Knoten 0 mehrmals durchläuft. Der Pfad p2 ist ein Zyklus und sogar ein Kreis.

Der leere Pfad λ ist einfach und ist auch ein Weg, aber kein Zyklus und kein Kreis. Er hat keinen Anfangs- und keinen Endknoten und keine inneren Knoten.

 

Satz:  Sei G = (V, E) ein Graph mit n Knoten, d.h. |V| = n. Dann hat jeder Weg in G höchstens die Länge n.

Beweis:  Sei   p = (u0, v0) ... (um-1, vm-1)   ein Pfad der Länge m > n. Dann können nicht alle ui verschieden sein, da es nur n Knoten gibt. Also ist p kein Weg.

Satz:  Wenn es in G einen Pfad von u nach v gibt, dann gibt es auch einen Weg von u nach v.

Beweis:  Sei   p = (u0, v0) ... (um-1, vm-1)   ein Pfad von u nach v. Aus p wird wie folgt ein Weg konstruiert:

Solange p kein Weg ist wiederhole:

  1. Suche einen Knoten w, der in p zweimal vorkommt, d.h.
    • w = ui und w = vj mit ikleiner gleichj;
  2. Streiche das Stück von ui nach vj in p, d.h. setze
    • p  =  (u0, v0) ... (ui-1, vi-1) (uj+1, vj+1) ... (um-1, vm-1);

Im folgenden Bild 2 ist ein Pfad dargestellt, der einen Knoten ui = vj zweimal durchläuft. Indem die Schleife von ui nach vj entfernt wird, entsteht ein Weg.

Bild 2: Pfad, der einen Knoten zweimal durchläuft
Bild 2: Pfad, der einen Knoten zweimal durchläuft

Baum

Definition:  Ein gerichteter Graph T = (V, E) ist ein Baum, wenn

Definition:  Sei T ein Baum. Ein Knoten b heißt Blatt, wenn er keine Nachfolger hat; alle anderen Knoten heißen innere Knoten des Baumes.

Die Tiefe d(v) eines Knotens v ist die Länge des Weges von der Wurzel r nach v. Die Tiefe d(T) des Baumes ist die maximale Tiefe der Knoten.

Definition:  Ein Baum T ist ein binärer Baum, wenn jeder Knoten einen Ausgangsgrad von höchstens 2 hat.

Definition:  Ein binärer Baum T heißt fast vollständig, wenn

Vollständiger binärer Baum
Bild 3: Fast vollständiger binärer Baum mit 12 Knoten

Bei einem fast voll­ständigen binären Baum darf also die unterste Schicht unvoll­ständig sein (Bild 3).

Satz:  Ein voll­ständiger oder ein fast voll­ständiger binärer Baum T mit n Knoten hat eine Tiefe von

d(T))  =  int(log2(n)).

In der Informatik werden Bäume falsch herum gezeichnet: die Wurzel ist oben, die Blätter sind unten. Die Pfeilspitzen an den Kanten werden dann weggelassen; die Kanten sind immer von oben nach unten gerichtet (Bild 3).

Ungerichteter Graph

Ein ungerichteter Graph lässt sich als Spezialfall eines gerichteten Graphen auf­fassendeneen, nämlich als ein gerichteter Graph, bei dem die Kanten stets in beide Richtungen verlaufen. Dann können in der grafischen Darstellung die Pfeilspitzen auch weggelassen werden (Bild 4).

Definition:  Ein gerichteter Graph G = (V, E) ist ein ungerichteter Graph, wenn seine Kanten­relation E symmetrisch ist, d.h. wenn gilt:

E = E -1.

Ein Graph ist also ungerichtet, wenn für alle Kanten (u, v) gilt: (v, u) ist ebenfalls Kante.

Bild 4: Ungerichteter Graph
Bild 4: Ungerichteter Graph

Zwei Knoten, die durch eine Kante verbunden sind, werden als benachbart bezeichnet. Die Anzahl der zu einem Knoten u benachbarten Knoten ist der Grad des Knotens u.

Definition:  Sei G = (V, E) ein ungerichteter Graph ohne Schlingen.

G heißt zusammen­hängend, wenn es in G von jedem Knoten u zu jedem anderen Knoten v mindestens einen Weg gibt.

G heißt kreisfrei, wenn es in G von jedem Knoten u zu jedem anderen Knoten v höchstens einen Weg gibt.

G ist ein Baum, wenn G zusammen­hängend und kreisfrei ist, d.h. wenn es in G von jedem Knoten u zu jedem anderen Knoten v genau einen Weg gibt.

Bild 5: Ungerichteter Baum
Bild 5: Ungerichteter Baum

Ein ungerichteter Baum hat keine definierte Wurzel. Jeder Knoten kann die Rolle der Wurzel annehmen.

Definition:  Sei G = (V, E) ein ungerichteter Graph ohne Schlingen.

G heißt vollständig, wenn jeder Knoten mit jedem anderen Knoten durch eine Kante verbunden ist.

Bild 6: Vollständiger Graph mit 5 Knoten
Bild 6: Vollständiger Graph mit 5 Knoten

Ein voll­ständiger Graph mit n Knoten hat n·(n-1)/2, also Θ(n2) ungerichtete Kanten.

Definition:  Sei G = (V, E) ein ungerichteter Graph. Ein Graph G' = (V', E') heißt Teilgraph von G, wenn er aus gewissen Knoten von G und Kanten von G zwischen diesen Knoten besteht und wenn er ungerichtet ist, d.h. wenn gilt

V' enthalten in V,

E' enthalten in E Durchschnitt V' × V'     und

E' = E' -1 .

Markierte Graphen

Definition:  Sei G = (V, E) ein Graph und A eine Menge. Eine Abbildung

w : V Pfeil nach rechts A,

die jedem Knoten v Element V ein Element w(vElement A zuordnet, heißt Knoten­markierung.

Definition:  Sei G = (V, E) ein (gerichteter) Graph und A eine Menge. Eine Abbildung

w : E Pfeil nach rechts A,

die jeder Kante e Element E ein Element w(eElement A zuordnet, heißt Kanten­markierung.

Ist auf der Menge A eine Verknüpfung • definiert und bildet die Menge A mit dieser Verknüpfung ein Monoid (A, •, 1) mit neutralem Element 1, so lässt sich die Markierung der Kanten zu einer Markierung der Pfade in folgender Weise erweitern:

w(λ) = 1   und

w(pe) = w(p)•w(e)

für alle Pfade p und alle Kanten e. Hierbei bezeichnet λ den Pfad der Länge 0.

Beispiel:  Sei A = natürliche Zahlen0. Als Kanten­markierung w wählen wir die Abbildung, die jeder Kante des Graphen die Zahl 1 zuordnet. Die Menge natürliche Zahlen0 bildet mit der Operation + und dem neutralen Element 0 ein Monoid. Daher lässt sich die Markierung der Kanten zu einer Markierung der Pfade erweitern:

w(λ) = 0   und

w(pe) = w(p) + w(e)

für alle Pfade p und alle Kanten e.

Somit wird in diesem Beispiel jedem Pfad p durch die Markierung w(p) seine Länge zugeordnet.

Aufgaben

Aufgabe 1:  Sei T = (V, E) ein gerichteter Graph. Beweisen Sie unter Benutzung der oben angegebenen Definition für einen (gerichteten) Baum:

T ist ein Baum genau dann, wenn es einen Knoten w Element V gibt, von dem aus zu allen anderen Knoten aus V jeweils genau ein Pfad hinführt.

 

Weiter mit:   [Gruppe]   [Literatur]   oder   up

 

homeH.W. Lang   Fachhochschule Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 29.01.1998   Updated: 25.04.2015
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot:

Web- und Softwaretechnologie

Ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien...

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Und ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten IT-Sicherheit, Mobile Computing und Human-Computer Interaction...

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

Medieninformatik Medieninformatik

Informations- und Kommunikationstechnologie

Wirtschaftsinformatik