Direkt zum Inhalt

Lexikon der Mathematik: k-fach kantenzusammenhängender Graph

ein zusammenhängender Graph G mit mindestens zwei Ecken, so daß GK′ für alle K′ ⊆ K(G) mit |K′| ≤ k − 1 (k ∈ ℕ) zusammenhängend bleibt.

Ist G k-fach kantenzusammenhängend, aber nicht (k + 1)-fach kantenzusammenhängend, so nennt man k = λ(G) Kantenzusammenhangszahl von G. Für einen zusammenhängenden Graphen G gilt genau dann λ(G) = k, wenn die kleinste trennende Kantenmenge aus k Kanten besteht.

Die Idee der folgenden Aussage stammt von K.Menger (1927), aber explizit wurde sie erst 1956 durch L.R. Ford und D.R. Fulkerson sowie P. Elias, A. Feinstein und C.E. Shannon angegeben.

Ein Graph ist genau dann k-fach kantenzusammenhängend, wenn zwischen je zwei verschiedenen Ecken k kantendisjunkte Wege existieren.

Bei der Konstruktion von „guten Einbahnstraßennetzen“ ist das folgende tiefliegende Ergebnis von Nash-Williams (1960) sehr nützlich.

Jeder 2k-fach kantenzusammenhängende Graph besitzt eine k-fach bogenzusammenhängende Orientierung.

Der Spezialfall k = 1, der nicht so schwierig zu beweisen ist, geht auf H.E. Robbins (1939) zurück.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos