Über trennende Knotenpunkte in Graphen (nebst Anwendungen auf De\-terminanten und Matrizen). (Q559373)

\textit{Artikulation} nennt Verf. - von \textit{Sainte Laguës} Definition nur formal abweichend - einen Knotenpunkt \(A\) eines endlichen oder unendlichen Graphen \(G\) (der hier immer ohne Schlingen vorausgesetzt wird), wenn \(G\) zwei Kanten \(AP, AQ\) von der Eigenschaft besitzt, daß\ jeder \(P\) und \(Q\) verbindende Weg von \(G\) auch \(A\) enthält. Durch die Artikulationen wird \(G\) in Bestandteile - ``Glieder'' - zerlegt derart, daß\ je zwei Kanten eines Gliedes in wenigstens einem dem Glied angehörenden Kreis liegen, Kanten verschiedener Glieder aber keinem Kreis von \(G\) angehören. Zwei Glieder haben höchstens einen Knotenpunkt, eine Artikulation, gemeinsam. In \(\S 1\) gibt Verf. eine ausführliche Darstellung des Aufbaus eines Graphen durch Artikulationen und Glieder, die ein Analogon der Theorie der zyklische Elemente und der cut-points der stetigen Kurven ist. In \(\S 2\) werden dann allgemeiner trennende Knotenpunktsysteme in Graphen untersucht: \(G\) sei ein (echter oder unechter) Teilgraph eines Graphen \(H, \varPi \) die Menge der Knotenpunkte des Graphen \(G, \varPi '\) eine Teilmenge von \(\varPi, \varPi _1\) und \(\varPi _2\) Teilmengen der Menge der Knotenpunkte von \(H\). \(\varPi _1\) und \(\varPi _2\) werden ``in \(G\) durch \(\varPi '\) getrennt'', wenn jeder in \(G\) verlaufende Weg, der einen Punkt von \(\varPi _1\) mit einem Punkt von \(\varPi _2\) verbindet (\(\varPi _1\varPi 2\)-Weg), wenigstens einen Punkt von \(\varPi '\) enthält. Verf. beweist: Ist \(\varPi _1+\varPi _2=\varPi \), \(\varPi _1\cdot \varPi _2=0\) und können \(\varPi _1\) und \(\varPi _2\) nicht durch weniger als \(n\) Punkte voneinander getrennt werden, so gibt es in \(G\) \(n\) Kanten, die paarweise keinen Endpunkt gemeinsam haben. Für paare Graphen bedeutet das: Die (endliche) Minimalzahl \(m\) der Knotenpunkte \(P_1,P_2,\dots,P_m\) von der Eigenschaft, daß\ jede Kante von \(G\) in einem \(P_{\mu }\) endet, ist gleich der Maximalzahl der Kanten, die paarweise keinen gemeinsamen Endpunkt besitzen. Hieraus ergibt sich leicht der bekannte Satz (Verf., 1916; F. d. M. 46; 146-167, 1451-1452) daß\ jeder endliche reguläre paare Graph einen Faktor ersten Grades enthält. Wählt man in einem paaren Graphen die Mengen \(\varPi _1=(P_1,P_2,\dots,P_n)\) und \(\varPi _2=(Q_1,Q_2,\dots,Q_n)\) \((P_i\neq Q_k)\) so, daß\ jede Kante ein \(P_i\) mit einem \(Q_k\) verbindet, und ist der Graph \(G^{*}\) derjenigen Kanten von \(G\), die in wenigstens einem Faktor ersten Grades enthalten sind, nicht zusammenhängend, so kann man bei passendem \(r (0<r<n)\) eine Menge von \(r\) Punkten aus \(\varPi _1\) und dazu \(n-r\) Punkte aus \(\varPi _2\) so auswählen, daß\ zwei der ausgewählten Punkte niemals Endpunkte derselben Kante sind. Diese Sätze, die mit elementaren Hilfsmitteln der Graphentheorie bewiesen werden, lassen interessante Anwendungen zu. In \(\S 4\) gibt Verf. einen Beweis des \textit{Menger}schen ``\(n\)-Kettensatzes'' (Zur allgemeinen Kurventheorie (1927; F. d. M. 53, 561 (JFM 53.0561.*)) sowie Kurventheorie (Leipzig 1932; F. d. M. 58), S.221-228) für endliche Graphen: Wenn die zueinander fremden Knotenpunktmengen \(\varPi _1, \varPi _2\) von \(G\) nicht durch weniger als \(n\) Knotenpunkte getrennt werden können, so gibt es in \(G\) \(n\) paarweise fremde \(\varPi _1\varPi _2\)-Wege. Der Satz gilt auch für unendliche Graphen bei endlichem \(n\); dafür teilt Verf. einen Beweis von \textit{Erdös} mit. - \(\S 3\) enthält Anwendungen auf die Determinantentheorie. Sie ergeben sich aus den obigen Sätzen, wenn man jeder Zeile und jeder Spalte einer Matrix \((a_{ik})\) einen Knotenpunkt zuordnet und der \(i\)-ten Zeile entsprechenden Knotenpunkt mit dem der \(k\)-ten Spalte entsprechenden durch eine Kante verbindet, wenn \(a_{ik}\neq 0\). So ergeben sich folgende Sätze: Verschwinden alle Entwicklungsglieder aller Unterdeterminanten \(n\)-ten Grades einer Matrix von \(p\) Zeilen und \(q\) Spalten \((n\leqq p, n\leqq q)\), so verschwinden für ein \(r\) \((1\leqq r\leqq p)\) alle Elemente, die gewisse \(r\) Zeilen mit gewissen \((p+q-n+1)-r\) Spalten gemeinsam haben. Für \(p=q=n\) ist das ein Satz von \textit{Frobenius} (1917; F. d. M. 46, 144 (JFM 46.0144.*)). Die Minimalzahl der Reihen (Zeilen und Spalten), die zusammen alle nicht verschwindenden Elemente der Matrix enthalten, ist gleich der Maximalzahl der nicht verschwindenden Elemente, die paarweise verschiedenen Zeilen und verschiedenen Spalten angehören. (Vgl. hierzu eine in ungarischer Sprache erschienene Arbeit des Verf., Graphen und Matrizen, Mat. és Fiz. Lapok 38 (1931), 116-119; F. d. M. \(57_{\text{II}}\).) Ebenfalls einen Satz von \textit{Frobenius} (a. a. O. sowie 1912; F. d. M. 43, 204 (JFM 43.0204.*)-205; vgl. auch Verf., 1915; F. d. M. 45, 1240 (JFM 45.1240.*)) verallgemeinert der Satz: Faßt man in einer Determinante \(n\)-ten Grades \(D\) die nicht verschwindenden Elemente als unabhängige Veränderliche auf und bildet man aus den Entwicklungsgliedern von \(D\) eine lineare ganze Funktion mit nicht verschwindenden Koeffizienten, so ist diese Funktion als Polynom der Elemente von \(D\) nur dann reduzibel, wenn für ein \(r\) \((1\leqq r\leqq n-1)\) alle Elemente von \(D\) verschwinden, die gewisse \(r\) Zeilen mit gewissen \(n-r\) Spalten gemeinsam haben. (III 2.)