Kreise
Wir betrachten nun Graphen, die sich zyklisch anordnen lassen:
Definition (Kreis, Dreieck)
Ein Graph G = (E, K) mit n = |E| ≥ 3 heißt ein Kreis mit n Ecken, falls es eine Anordnung e1, …, en der Ecken gibt derart, dass
K = { e1e2, e2e3, …, en − 1en } ∪ { ene1 }.
Ein Kreis mit 3 Ecken heißt auch ein Dreieck.
In der Graphentheorie kann man also singen: „Mein Kreis, der hat drei Ecken. Mein Dreieck ist ein Kreis.“
Aus der Definition lesen wir ab: Ist G = (E, K) ein Kreis, so ist die Ordnung von G gleich der Größe von G, d. h. |E| = |K|. Damit kann zum Beispiel ein Graph mit 10 Ecken und 12 Kanten kein Kreis sein. Weiter hat ein Kreis die konstante Gradfolge 2, …, 2.
Beispiele
(1) | Ist G ein Graph der Ordnung 3, so ist G genau ein Kreis (und damit ein Dreieck), wenn G vollständig ist. |
(2) | Ist G = (E, K) ein Graph der Ordnung 4, so ist G genau dann ein Kreis, wenn |K| = 4 und G kein Dreieck enthält, d. h. es gibt keine Ecken a, b, c mit ab, bc, ca ∈ K. |
(3) | Der Graph G = (E, K) mit E = { 1, …, 6 } und K = { 12, 13, 23, 45, 46, 56 } hat die konstante Gradfolge 2, …, 2, ist aber kein Kreis. |
(4) | Sei G = (E, K) mit E = { 1, …, 12 } und K = { 14, 16, 26, 29, 35, 37, 4-10, 5-10, 78, 8-11, 9-12, 11-12 }. Der Graph ist ein Kreis mit der Eckenanordnung e1, …, e12 = 1, 6, 2, 9, 12, 11, 8, 7, 3, 5, 10, 4. |
Wir definieren wieder natürliche Repräsentanten für Kreisgraphen:
Definition (die Graphen Cn)
Seien n ≥ 3. Dann ist der kanonische Kreis mit n Ecken Cn definiert durch
| Ecken von Cn: | 1, …, n |
| Kanten von Cn: | i(i + 1) mit 1 ≤ i < n, sowie die Kante n1 |
Die kanonischen Kreise C7 und C12