In der Graph-Theorie ist der Umfang eines Graphen die Länge eines kürzesten im Graphen enthaltenen Zyklus. Wenn der Graph keine Zyklen enthält (d. h. es ein acyclic Graph ist), wird sein Umfang definiert, um Unendlichkeit zu sein.

Zum Beispiel hat ein 4-Zyklen-(Quadrat) Umfang 4. Ein Bratrost hat Umfang 4 ebenso, und ein Dreiecksineinandergreifen hat Umfang 3. Ein Graph mit dem Umfang vier oder mehr ist ohne Dreiecke.

Käfige

Ein Kubikgraph (haben alle Scheitelpunkte Grad drei), des Umfangs, der so klein wie möglich ist, ist als - Käfig (oder als (3), - Käfig) bekannt. Der Graph von Petersen ist der einzigartige 5-Käfige-(es ist der kleinste Kubikgraph des Umfangs 5), der Graph von Heawood ist der einzigartige 6-Käfige-, der Graph von McGee ist der einzigartige 7-Käfige- und Tutte acht Käfig ist der einzigartige 8-Käfige-. Dort kann vielfache Käfige für einen gegebenen Umfang bestehen. Zum Beispiel gibt es drei nichtisomorphe 10 Käfige, jeden mit 70 Scheitelpunkten: Der Balaban 10-Käfige-, Verwüstet Graphen, und Verwüstet Graphen-Wong.

Image:Petersen1 winziger svg|The Graph von Petersen hat einen Umfang von 5

Image:Heawood_Graph.svg|The Heawood Graph hat einen Umfang von 6

Image:McGee Graph svg|The Graph von McGee hat einen Umfang von 7

Image:Tutte acht Käfig svg|The Tutte-Coxeter Graph (Tutte acht Käfig) hat einen Umfang von 8

Umfang und das Graph-Färben

Für irgendwelche positiven ganzen Zahlen und, dort besteht ein Graph mit dem Umfang mindestens und der chromatischen Zahl mindestens; zum Beispiel ist der Graph von Grötzsch ohne Dreiecke und hat chromatische Nummer 4 und das Wiederholen, dass der Aufbau von Mycielskian, der verwendet ist, um den Graphen von Grötzsch zu bilden, Graphen ohne Dreiecke der willkürlich großen chromatischen Zahl erzeugt. Paul Erdős war erst, um das allgemeine Ergebnis mit der probabilistic Methode zu beweisen. Genauer hat er gezeigt, dass ein zufälliger Graph auf Scheitelpunkten, die durch die Auswahl unabhängig gebildet sind, ob man jeden Rand mit der Wahrscheinlichkeit einschließt mit der Wahrscheinlichkeit hat, die zu 1 neigt, wie zur Unendlichkeit an den meisten Zyklen der Länge oder weniger geht, aber keinen unabhängigen Satz der Größe Deshalb hat, verlässt das Entfernen eines Scheitelpunkts von jedem kurzen Zyklus einen kleineren Graphen mit dem Umfang größer als, in dem jede Farbenklasse eines Färbens klein sein muss, und der deshalb mindestens Farben in jedem Färben verlangt.

Zusammenhängende Konzepte

Der sonderbare Umfang und sogar Umfang eines Graphen sind die Längen eines kürzesten sonderbaren Zyklus und kürzesten gleichen Zyklus beziehungsweise.

Gedanke als kleinste Länge eines nichttrivialen Zyklus, der Umfang lässt natürliche Verallgemeinerungen als die höheren oder 1-Systole-Systolen in der systolic Geometrie zu.