MiDigraph

Mathematische Grundbegriffe:

Ein Digraph d = (V (G), A(G)) besteht aus zwei endlichen Mengen: V(G), der nichtleeren Knotenmenge, die als Knoten von D bezeichnet werden und der möglicherweise leeren Bogenmenge A (G) , die als Bögen oder als gerichtete Kanten oder nur Kanten von D bezeichnet werden, so daß jedem Bogen a in A ein geordnetes Knotenpaar (u,v) zugeordnet ist.

zurück

Wenn a ein Bogen in dem Digraphen D ist, zu dem das geordnete Knotenpaar (u,v) gehört, dann sagt man, daß a u mit v verbindet. Dabei wird u als Anfangsknoten von a und v als Endknoten von a bezeichnet. Die Richtung des Bogens wird durch eine Pfeilspitze gekennzeichnet.

zurück

Es ist möglich, einen Knoten mit sich selbst durch einen Bogen zu verbinden - eine derartiger Bogen wird als Schlinge bezeichnet.

zurück

Eine Bogenfolge in einem Digraphen ist eine endliche Folge W = voe1v1e2v2...vk-1ekvk, deren Glieder abwechselnd Knoten und Bögen sind.

zurück

Wenn zwei (oder mehrere) Bögen von G denselben Anfangs- und Endknoten haben, werden diese Bögen dann parallel genannt.

zurück

Der Eingangsgrad id(v) von v ist die Anzahl der Bögen von D, deren Kopf v ist, d.h. die Anzahl der Bögen, die "auf v zugehen". Der Ausgangsgrad od(v) ist die Anzahl der Bögen von D, deren Schwanz v ist, d.h. die Anzahl der Bögen, die "von v wegführen".

zurück