Information Technology Reference
In-Depth Information
Betrachten wir einige Beispiele. In den folgenden referenzierten Abbildungen
werden die Mengen
X
und
Y
hell- bzw. mittelgrau schattiert sein, während die Men-
ge
Z
dunkelgrau dargestellt wird.
X
Z
=
A
C
F
H
E
J
B
D
G
Y
Abbildung 23.15: Knoten
E
blockiert den einzigen Pfad von
A
nach
D
:
A
G
D
| .
Beispiel 23.5
In Abbildung 23.15 sind X und Y jeweils einelementig und Z ist leer. Da es
sich um einen Baum handelt, ist nur ein Pfad zu überprüfen:
A
C
E
D
•
CistseriellerKnotenimPfadundnichtinZ.Daherblockierternicht.
•
EistkonvergierenderKnotenimPfadundnichtinZ.EbensosindseineNachfolgerF,
H, G und J nicht in Z. Folglich blockiert E.
Die Existenz eines blockierenden Knotens ist ausreichend für die Blockade eines Pfades. Folg-
lich gilt
A
G
D
| .
X
A
C
F
H
Z
E
J
B
D
G
Y
Abbildung 23.16: Da
E
Z
wird der Pfad von
A
nach
D
aktiv:
A
G
D
|
E
.
Beispiel 23.6
Im Gegensatz zu Beispiel 23.5 enthält nun die Menge Z den Knoten E. Ab-
bildung 23.16 zeigt die Situation. Wieder ist im Baum nur der folgende Pfad zu überprüfen:
A
C
E
D
