(wie Reihen- und Parallelschaltungen in der Elektrotechnik)
Def:
SP ist Menge von markierte Graphen (s, G, t)
mit
V s t V.
- wenn G nur die Kante s - t ist, dann
(s, G, t) SP
-
SP ist die kleinste Menge, die abgeschlossen ist
unter den Operationen:
- (Reihenschaltung)
(s1, G1, t1) . (s2, G2, t2) = (s1, G', t2)
mit
G' = G1 G2 mit t1 = s2
- (Parallelschaltung)
(s1, G1, t1) + (s2, G2, t2) = (s1, G', t1)
mit
G' = G1 G2 mit s1 = s2 und t1 = t2
Satz:
(s, G, t) SP tw(G)2.
Johannes Waldmann
2005-01-25