Information Technology Reference
In-Depth Information
Analog werden sog.
maximal spannende Bäume
(engl.
maximum spanning trees
)de-
finiert: Die Summe der Kantengewichte muss in diesem Fall maximal sein. Algorith-
men zur Bestimmung von maximal bzw. minimal spannenden Bäumen sind u. a.:
• K
RUSKAL
-Algorithmus [Kruskal 1956]
• P
RIM
-Algorithmus [Prim 1957]
Im Folgenden werden Begriffe für gerichtete Graphen vorgestellt.
Definition 23.24 (Elternknoten, Kindknoten, Familie)
Sei G
=(
V
,
E
)
ein gerichteter
Graph und A
VeinKnoten.DieMengeder
Elternknoten
5
von A ist definiert als:
pa(
A
)={
B
V
|
B
A
E
}
Analog ist die Menge der
Kindknoten
von A festgelegt:
ch(
A
)={
B
V
|
A
B
E
}
Die
Familie
des Knotens A besteht aus A selbst und seinen Elternknoten:
fa(
A
)={
A
}pa(
A
)
Definition 23.25 (Azyklischer, gerichteter Graph (DAG))
Ein gerichteter Graph G
=
(
V
,
E
)
wird
azyklisch
genannt, wenn für jeden Pfad X
1
···
X
k
in G gilt:
X
k
X
1
/
E
Definition 23.26 (Vorfahren, Nachfahren, Nicht-Nachfahren)
Sei G
=(
V
,
E
)
ein ge-
richteter, azyklischer Graph
6
und A
VeinKnoten.DieMengeder
Vo r f ah r en
von A ist
definiert als:
ancs
(
A
)={
B
V
|
:
B
G
A
}
Für die Menge der
Nachfahren
von A gilt:
G
descs
(
A
)={
B
V
|
:
A
B
}
Die Menge der
Nicht-Nachfahren
des Knotens A lautet:
non-descs
(
A
)=
V
\{
A
}\
descs
(
A
)
Beispiel 23.1
Der linke Teil von Abbildung 23.3 zeigt einen gerichteten, azyklischen Gra-
phen (DAG) zusammen mit den Eltern, Kindern und der Familie des Knotens F. Die fol-
gende Definition führt drei weitere „Verwandtschaftsbeziehungen“ ein: Der rechte Teil von
Abbildung 23.3 zeigt einen DAG zusammen mit den Nachfahren, den Vorfahren und den
Nicht-Nachfahren des Knotens F. Tabelle 23.2 zeigt zusätzlich die Vor-, Nach- und Nicht-
Nachfahren aller Knoten des Graphen aus Abbildung 23.3.
Ist eine Anordnung, die jedem Buchstaben der Knotenbeschriftung die Position im
Alphabet zuordnet (
(
A
)=
1, . . . ,
(
G
)=
7
), so ist eine topologische Ordnung.
5
Wir verzichten darauf , graphenspezifische Funkt ionen (wie in diesem Fal l pa() und ch())nochmit
dem entsprechenden Graphen zu indizieren, auf dem sie operieren, da in diesem Buch in allen Fällen
jeweils nur ein Graph zur Diskussion steht.
6
Im Gegensatz zu Definition 23.24 fordern wir hier Azyklizität, da sonst Knoten Vor- oder Nachfahren
ihrer selbst sein könnten.
