Eine Beziehung zwischen den Weg-Kreis-Systemen in einem gerichteten Graphen und den Unterdeterminanten seiner charakteristischen Matrix

✍ Scribed by Peter Heinrich

• Publisher: John Wiley and Sons
• Year: 1979
• Tongue: English
• Weight: 686 KB
• Volume: 93
• Category: Article
• ISSN: 0025-584X
• DOI: 10.1002/mana.19790930102

✦ Synopsis

In &eser Arbeit werden die Unterdeterminanten der charakteristischen Matrix eines gerichteten Graphen G mit n Knoten betrachtet, und es wird versucht, die Koeffizienten dieser Unterdeterminanten durch gewisse Eigenschaften von G zu charakterisieren, ahnlich, wie dies von SACHS und anderen Autoren fiir die Koeffizienten des charakteristischen Polynoms eines Graphen oder in [I] fur die (n -1)-reihigen Unterdeterminanten geschehen ist. Dabei kann das angegebene Problem vollstandig gelost werden.

Alle im folgenden betrachteten Graphen seien endlich und gerichtet. 1st

Kantenmenge von G bedeuten. Unter einem Weg bzw. Kreis von G verstehen wir eine offene bzw. geschlossene orientierte doppelpunktfreie Kantenfolge von G. Wie ublich wird die Anzahl der Kanten einer Kantenfolge von G ihre Lange genannt. Ein Weg kann die Lange 0 haben (trivialer Weg), Kreise haben stets eine Lange 5 1. Unter einem Teilgraphen T = (V,, E,) von G verstehen wir einen Graphen mit V o V , E , 5 E und der Eigenschaft : 1st K eine Kante aus E,, die vom Knoten a zum Knoten 71 fiihrt, so sind a, bE V,. Ein Teilgraph T = ( Yo, E,) heiBt ein Untergraph von G (oder der von V o erzeugte Untergraph von G ) genau dann, wenn jede Kante von G, die Knoten aus V , verbindet, auch in E, vorkommt. Es seien nun wi, . . . , w, Wege einer Lange 2 I und k l , . . . , k, Kreise von G ;

dabei sol] r + s z 1 sein.

Definition 1. Sind wi, . . . , w,, h i , . . . , k8 paarweise knotenfremd, so heifit der von wl, . . . , w,, k l , . . . , k, gebildete Teilgraph W von G ein Weg-Kreis-Xystern von G.

Ein Weg-Kreis-System von G mit s = 0 bzw. r = 0 nennen wir auch ein Wegbzw. Kreis-System von G. Unter der Lange von W versteht man die Summe der Langen der Komponenten von W .

Sei S die Menge der Anfangsknoten und 2 die Menge der Endknoten aller Wege des Weg-Kreis-Systems W ; offenbar ist IS1 = 1 2 1 = r und SflZ=0. 1st r s l , so sind S und 2 nichtleer, und wir nennen W dann auch ein Weg-Kreis-System v o n S n a c h Z i n G . SeiCT=(V,E) mit V = { 1 , 2 , . . . , n ) ( n z l ) undA=(aij) die