×

zbMATH — the first resource for mathematics

The theory of regular graphs. (Die Theorie der regulären Graphen.) (German) JFM 23.0115.03
Die vorliegende Arbeit ist bemerkenswert insofern sie mit Erfolg versucht, neuere Principien der Invariantentheorie, die sich an die Theorie der diophantischen Gleichungen anlehnen, auf rein anschaulichem Wege klarzulegen und weiterzuführen. Der Verf. ist dabei nach eigener Angabe durch einen regen Briefwechsel mit Hrn. Sylvester sehr gefördert worden.
D. Hilbert stützt sich bei seinem ersten “Endlichkeitsbeweise” [Math. Ann. 33, 223–226 (1889; JFM 20.0110.01)] auf einen Gordan’schen Satz, wonach sich bei gegebenem \(n\) eine endliche Anzahl von “Grundproducten” \[ (x_1-x_2)^\alpha (x_1-x_3)^\beta (x_2-x_3)^\gamma \dots (x_{n-1}-x_n)^\varepsilon \] bilden lässt, sodass alle anderen Producte derselben Form aus jenen durch Multiplication zusammensetzbar sind. Der Verf. stellt sich die Aufgabe, diese Grundproducte für verschiedene Werte von \(n\) wirklich zu bilden.
Man repräsentire jedes \(x\) durch einen Punkt der Ebene, jeden Factor \(x_i-x_k\) durch eine beliebige Verbindungslinie zwischen \(x_i\) und \(x_k\); beispielsweise entspricht dann dem Producte \[ (x_1-x_2)^2(x_3-x_4)^2 (x_1-x_3)(x_2-x_4)(x_1-x_4)(x_2-x_3) \] ein Viereck mit seinen Diagonalen, von dem aber zwei Gegenseiten doppelt ausgezogen sind.
Da die in Rede stehenden Ausdrücke in jedem \(x\) von gleichem Grade \(\alpha\) (nämlich dem Grade der entsprechenden Invariante) sind, so laufen in jedem Punkte unserer \(n\)-Ecke gleichviel Linien zusammen, daher die Bezeichnung: “Regulärer Graph \(G_x^n\)”.
Es kommt des weiteren wesentlich darauf an, ob ein Graph primitiv ist oder nicht; im letzteren Falle kann er durch Ueberlagerung mehrerer Graphs derselben Ordnung, aber von niedrigerem Grade entstanden gedacht werden.
Die Hauptaufgabe ist demnach die Bestimmung aller primitiven Graphs.
Hier zeigt sich nun ein merkwürdiger Unterschied, je nachdem der Grad gerade oder ungerade ist.
Bei geradem Grade giebt es nur Grundfactoren ersten oder zweiten Grades. Bei ungeradem Grade dagegen können die Grundfactoren für ein genügend grosses \(n\) bis zu einem beliebigen Grade ansteigen; der einfachste ist hier vom dritten Grade für \(n = 10\).
Zur Ableitung solcher Sätze bedarf es jedoch einer grossen Reihe von Hülfssätzen: es ist zu untersuchen, falls ein Graph auf verschiedene Weisen zerlegbar ist, wie diese Zerlegungen mit einander verknüpft sind, wie sie sich in einander überführen lassen, u. s. f. Eine besondere Bedeutung hat der Begriff zweier gepaarten Graphs (gerader Ordnung). Von diesen entsteht der eine aus dem anderen, indem zwei Linien \(ab\) und \(cd\) entfernt und dafür durch zwei andere \(ac\) und \(bd\) (resp. \(ad\) und \(bc\)) ersetzt werden.
Die Natur der benutzten Methoden bringt es mit sich, dass eine weitere Auseinandersetzung hier zwecklos sein würde; es sei nochmals auf die geistreiche Arbeit selbst verwiesen.

MSC:
05C99 Graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Mein Beweis war ursprünglich nicht ganz so einfach wie jetzt; die Verbesserung verdanke ich dem Hrn. DirektorBing.
[2] Dass dieses möglich ist, beweist man leicht, indem man bei kleinen Änderungen der Curven bewerkstelligen kann, dass diese sich nicht schneiden.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.