×

Some unique separation theorems for graphs. (English) JFM 61.1346.01

\(G\) sei ein zusammenhängender Streckenkomplex ohne Schleifen, in dem zwei Ecken durch höchstens eine Strecke verbunden sind. Unter einem Teilkomplex \(H\) von \(G\) ist ein Streckenkomplex zu verstehen, der aus einer Teilmenge der Menge der Ecken von \(G\) und allen denjenigen Kanten von \(G\) besteht, deren beide Endpunkte der Eckenteilmenge angehören; \(G-H\) ist derjenige Komplex, der übrig bleibt, wenn man aus \(G\) alle Ecken von \(H\) und alle Kanten, die mindestens einen Endpunkt in \(H\) haben, wegläßt. \(G\) und \(H\) seien zusammenhängend. Die “durch H bestimmte Zerlegung von G” (in Zeichen \(H\times G\)) besteht dann aus folgenden “Komponenten”: Sind \(F_1,\dots,F_m\) die größten zusammenhängenden Bestandteile von \(G-H\), so sind die Teilkomplexe \(H+F_\mu\) (\(\mu=1,\dots,m\)) die Komponenten von \(H\times G\).
Für die Untersuchung der Struktur von Streckenkomplexen ist es wichtig, Klassen von Teilkomplexen \(H\) mit folgender Eigenschaft auszuzeichnen: Treibt man die Zerlegung von \(G\) vermittels der Teilkomplexe der ausgezeichneten Klasse so weit wie möglich, so gelangt man, unabhängig von der Auswahl der Teilkomplexe und der Reihenfolge der sukzessiven Zerlegungen, zu einer bis auf Isomorphie der Komponenten eindeutig bestimmten Zerlegung von \(G\). Der einfachste Fall, in dem die ausgezeichnete Klasse von den nur aus einem Eckpunkt bestehenden Komplexen gebildet wird, ist von H. Whitney (Trans. Amer. math. Soc. 34 (1932), 339-362; F. d. M. 58\(_{\text{I}}\), 608-609) behandelt worden. Verf. geht hier einen Schritt weiter; er untersucht die Zerlegung durch “geodätische Ketten”. Dabei ist eine Kette ein doppelpunktfreier Streckenzug (der sich auch auf eine einzige Ecke reduzieren kann), und das Wort “geodätisch” bedeutet, daß die Endpunkte des Streckenzuges in \(G\) nicht durch einen Streckenzug von geringerer Streckenzahl verbunden werden können.
Es gelingt dem Verf., einen Eindeutigkeitssatz für die vollständige Zerlegung eines Streckenkomplexes durch geodätische Ketten zu beweisen. Dem Beweis liegt der folgende Prozeß der “alternierenden Zerlegung” zugrunde: \(B\) und \(C\) seien zwei geodätische Ketten in \(G\). Man bildet zuerst \(B\times G\). Dann wird auf jeder Komponente \(L\) von \(B\times G\) der zu \(L\) gehörende Teil von \(C\) nötigenfalls durch Hinzufügen von Teilen von \(B\) in eine gewisse zu \(L\) gehörende geodätische Kette \(C_L\) abgeändert und \(L\) durch \(C_L\) zerlegt; auf die so entstehenden Komponenten \(M\) wendet man wieder die Zerlegung durch \(B\), d. h. durch eine aus dem in \(M\) gelegenen Bestandteil von \(B\) und nötigenfalls gewissen Teilen von \(C\) gebildete geodätische Kette \(B_M\), an usw., bis sich nichts Neues mehr ergibt. Wenn man von gewissen unwesentlichen Komponenten absieht, ist das Ergebnis dieses Prozesses unabhängig davon, ob man mit \(B\times G\) oder mit \(C\times G\) beginnt.
Außerdem wird gezeigt, daß die Zerlegung eines Graphen durch einen Teilgraphen ein geeignetes Hilfsmittel zum Auffinden einer Basis der Zyklen des Graphen ist.
PDFBibTeX XMLCite
Full Text: DOI