mit n binaren Relationen seien im folgenden als Graphen vom Rang n bezeichnet. I m Falle symmetrischer ri h e a t @ ungerichtet (entgegengerichtete Kanten der gleichen Relation werden identifiziert). Fur n = 1 sprechen wir von einfachen Craph,en. Unter einer Komponente von @ verstehen wir einen maximalen zusammenhangenden Teilgraphen von @. Ein Graph @ h e a t reduziert, wenn nicht verschiedene Punkte von @ mit genau denselben Punkten verbunden bzw. unverbunden sind. I n reduzierten Graphen kann die Identitiit durch die Kantenrelationen ri ausgedriickt werden. Die Valenz eines Punktes ist die Gesamtzahl der in ihn ein-und von ihm auslaufenden Kanten. @ h e a t hochstens n-wlent, wenn jeder Punkt von @ hochstens die Valenz n hat.
1st @ hochstens n-valent, aber nicht hochstens ( n -1)-valent, so heil3t n die Maximalvalenz von @. SinngemaS sind die Begriffe mindestens n-valent und Minimalvalenz definiert. @ h e a t endlich-valent, wenn jeder Punkt von @ von endlicher Valenz ist. Unter einem Zyklus sei ein doppelpunktfreier geschlossener Weg (ohne Rucksicht auf eventuelle Kantenrichtung) verstanden, bei dem wenigstens drei Punkte durchlaufen werden; die Anzahl der durchlaufenen Punkte heae die Lunge des Zyklus. 8 h e a e von der Hochstweite n , wenn jeder Zyklus in @ hochstens die Lange n hat. SinngemiiB wird von Mindestweite sowie von Maximalund Minimalweite gesprochen.
Ein Baum ist ein einfacher Graph ohne Zyklen. Ein Zykloid sei ein mindestens drei Punkte enthaltender zweifach zusammenhangender einfacher ungerichteter Graph (d. h., nach Herausnahme eines Punktes zerfallt der Graph nicht in mehrere Komponenten). Jedem einfachen ungerichteten Graphen kann auf kanonische Weise ein ungerichteter Baum (sein Xkelett) zugeordnet werden, der au f folgende Weise entsteht: Jedes maximale Zykloid Z von @ wird durch einen Punkt Pz ersetzt (den Kontruktionspnkt von Z ) , der mit allen Punkten Q verbunden wird, die keinem Zykloid angehoren und vorher zu einem Punkt von Z adjazent waren,') sowie mit allen Kontraktionspunkten Pz#, mit Z n Z' = 0 , so da13 vorher ein Punkt von 2 mit einem solchen von 2' adjazent war. Jede Artikulation2) von Zykloiden 2 , . . . , Z' bleibt als Punkt erhalten, der mit den Kontraktionspunkten P z , . . . , P z p verbunden wird.
Unter einer Theorie wird im folgenden stets eine in einer Sprache der 1. Stufe formalisierte Theorie verstanden. Eine Theorie T heil3e in einer Theorie S interl) Punkte eines Graphen heiDen adjazent, wenn sie durch eine Kante verbunden sind.
2, Das heil3t jeder gemeinsame Punkt mehrerer Zykloide.