Select your language

Suggested languages for you:
Log In Anmelden

Lernmaterialien für Graphentheorie an der FernUniversität in Hagen

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Graphentheorie Kurs an der FernUniversität in Hagen zu.

TESTE DEIN WISSEN

Satz von Menger (Knotenversion für Graphen)

Lösung anzeigen
TESTE DEIN WISSEN

5.3.21 Satz (Menger−Knotenversion für Graphen)
Sei G = (V, E, ∂) ein Graph mit |V| > 1 .

  1. Lokal: Für q, s ∈ V mit q ist ungleich s, qs ist kein Element von ∂(E) gilt λ(G, q, s) = κ(G, q, s).
  2. Global: Gibt es q, s ∈ V mit q ist ungleich s, so dass höchstens ein e ∈ E mit ∂(e) = qs existiert, so gilt λ(G) = κ(G).
Lösung ausblenden
TESTE DEIN WISSEN

Definition: interner Knoten eines Weges

Lösung anzeigen
TESTE DEIN WISSEN

5.3.10 Definition
Sei G = (V, E, ∂) ein Graph bzw. D = (V, E, ∂) ein Digraph, beide nicht leer.
Ein Knoten eines Weges W in G bzw. D heißt interner Knoten von W, falls er weder mit dem Anfangs- noch mit dem Endknoten von W übereinstimmt.

Lösung ausblenden
TESTE DEIN WISSEN

Definition: Minimalschnitt

Lösung anzeigen
TESTE DEIN WISSEN

4.1.1 Definition
Sei G = (V, E, ∂) ein Graph und Z, S ⊆ E .

Ein nichtleerer Schnitt S in G heißt Minimalschnitt in G, wenn er minimal ist (vgl. 2.1.6) unter den nichtleeren Schnitten in G.

Lösung ausblenden
TESTE DEIN WISSEN

Satz von Menger (Knotenversion für Digraphen)

Lösung anzeigen
TESTE DEIN WISSEN

5.3.19 Satz (Menger−Knotenversion für Digraphen)
Sei D = (V, E, ∂) ein Digraph mit n := |V| > 1 .

  1. Lokal: Für q, s ∈ V mit q ist ungleich s und (q, s) kein Element von ∂(E) gilt λ(D, q, s) = κ(D, q, s).
  2. Global: Gibt es q, s ∈ V mit q ist ungleich s, so dass höchstens ein e ∈ E mit ∂(e) = (q, s) existiert, so gilt λ(D) = κ(D).
Lösung ausblenden
TESTE DEIN WISSEN

Satz von Tutte

Lösung anzeigen
TESTE DEIN WISSEN

6.3.14 Satz (Tutte)
Sei G = (V, E, ∂) ein Graph. Dann sind äquivalent:

  1. G besitzt ein perfektes Matching, d.h. |V| = 2ν(G).
  2. Für jedes X ⊆ V gilt o(G − X) ≤ |X|.
Lösung ausblenden
TESTE DEIN WISSEN

Frage: Wie viele Gerüste besitzt jeder Graph?

Lösung anzeigen
TESTE DEIN WISSEN

2.2.9 Satz

Jeder Graph besitzt (mindestens) ein Gerüst.

Lösung ausblenden
TESTE DEIN WISSEN

Definition: Anzahl der aufspannenden Bäume eines Graphen


Lösung anzeigen
TESTE DEIN WISSEN

2.3.1 Definition
Sei G = (V, E, ∂) ein Graph.
Dann bezeichnen wir mit t(G) die Anzahl der G aufspannenden Bäume.

Lösung ausblenden
TESTE DEIN WISSEN

Definition: Schnitt

Lösung anzeigen
TESTE DEIN WISSEN

4.1.1 Definition
Sei G = (V, E, ∂) ein Graph und Z, S ⊆ E .

S heißt Schnitt in G (vgl. 1.1.16), wenn es eine Partition (V_1, V_2) von V gibt mit S = G[V_1, V_2].

Lösung ausblenden
TESTE DEIN WISSEN

Satz von Menger (Bogenversion)

Lösung anzeigen
TESTE DEIN WISSEN

5.3.5 Satz (Menger−Bogenversion)
Sei D = (V, E, ∂) ein Digraph mit |V| > 1 .

  1. Lokal: Für q, s ∈ V mit q ist ungleich s gilt λ'(D, q, s) = κ'(D, q, s).
  2. Global: Es gilt λ'(D) = κ'(D).
Lösung ausblenden
TESTE DEIN WISSEN

Definition: Wann heißen zwei Knoten eines Digraphen verbindbar?

Lösung anzeigen
TESTE DEIN WISSEN

2.4.1 Definition
Sei D = (V, E, ∂) ein Digraph.

Zwei Knoten v und w des Digraphen D heißen verbindbar, wenn sowohl w von v aus als auch v von w aus erreichbar sind.

Lösung ausblenden
TESTE DEIN WISSEN

Frage: Wenn ein Digraph keinen Dikreis hat, wie viele Quellen und Senken hat dieser dann?

Lösung anzeigen
TESTE DEIN WISSEN

2.4.13 Aufgabe
Sei D = (V, E, ∂) ein Digraph mit V ist nicht leer.
Gibt es keinen Dikreis in D, so hat D wenigstens eine Quelle und eine Senke.

Lösung ausblenden
TESTE DEIN WISSEN

Satz von Euler für zusammenhängende Graphen

Lösung anzeigen
TESTE DEIN WISSEN

3.1.6 Bemerkung

Für einen zusammenhängenden Graphen G = (V, E, ∂) mit V ist nicht leer sind äquivalent:

  1. G ist eulersch.
  2. G ist Vereinigung paarweise kantendisjunkter Kreise.
  3. G ist gerade.
Lösung ausblenden
  • 346721 Karteikarten
  • 7770 Studierende
  • 100 Lernmaterialien

Beispielhafte Karteikarten für deinen Graphentheorie Kurs an der FernUniversität in Hagen - von Kommilitonen auf StudySmarter erstellt!

Q:

Satz von Menger (Knotenversion für Graphen)

A:

5.3.21 Satz (Menger−Knotenversion für Graphen)
Sei G = (V, E, ∂) ein Graph mit |V| > 1 .

  1. Lokal: Für q, s ∈ V mit q ist ungleich s, qs ist kein Element von ∂(E) gilt λ(G, q, s) = κ(G, q, s).
  2. Global: Gibt es q, s ∈ V mit q ist ungleich s, so dass höchstens ein e ∈ E mit ∂(e) = qs existiert, so gilt λ(G) = κ(G).
Q:

Definition: interner Knoten eines Weges

A:

5.3.10 Definition
Sei G = (V, E, ∂) ein Graph bzw. D = (V, E, ∂) ein Digraph, beide nicht leer.
Ein Knoten eines Weges W in G bzw. D heißt interner Knoten von W, falls er weder mit dem Anfangs- noch mit dem Endknoten von W übereinstimmt.

Q:

Definition: Minimalschnitt

A:

4.1.1 Definition
Sei G = (V, E, ∂) ein Graph und Z, S ⊆ E .

Ein nichtleerer Schnitt S in G heißt Minimalschnitt in G, wenn er minimal ist (vgl. 2.1.6) unter den nichtleeren Schnitten in G.

Q:

Satz von Menger (Knotenversion für Digraphen)

A:

5.3.19 Satz (Menger−Knotenversion für Digraphen)
Sei D = (V, E, ∂) ein Digraph mit n := |V| > 1 .

  1. Lokal: Für q, s ∈ V mit q ist ungleich s und (q, s) kein Element von ∂(E) gilt λ(D, q, s) = κ(D, q, s).
  2. Global: Gibt es q, s ∈ V mit q ist ungleich s, so dass höchstens ein e ∈ E mit ∂(e) = (q, s) existiert, so gilt λ(D) = κ(D).
Q:

Satz von Tutte

A:

6.3.14 Satz (Tutte)
Sei G = (V, E, ∂) ein Graph. Dann sind äquivalent:

  1. G besitzt ein perfektes Matching, d.h. |V| = 2ν(G).
  2. Für jedes X ⊆ V gilt o(G − X) ≤ |X|.
Mehr Karteikarten anzeigen
Q:

Frage: Wie viele Gerüste besitzt jeder Graph?

A:

2.2.9 Satz

Jeder Graph besitzt (mindestens) ein Gerüst.

Q:

Definition: Anzahl der aufspannenden Bäume eines Graphen


A:

2.3.1 Definition
Sei G = (V, E, ∂) ein Graph.
Dann bezeichnen wir mit t(G) die Anzahl der G aufspannenden Bäume.

Q:

Definition: Schnitt

A:

4.1.1 Definition
Sei G = (V, E, ∂) ein Graph und Z, S ⊆ E .

S heißt Schnitt in G (vgl. 1.1.16), wenn es eine Partition (V_1, V_2) von V gibt mit S = G[V_1, V_2].

Q:

Satz von Menger (Bogenversion)

A:

5.3.5 Satz (Menger−Bogenversion)
Sei D = (V, E, ∂) ein Digraph mit |V| > 1 .

  1. Lokal: Für q, s ∈ V mit q ist ungleich s gilt λ'(D, q, s) = κ'(D, q, s).
  2. Global: Es gilt λ'(D) = κ'(D).
Q:

Definition: Wann heißen zwei Knoten eines Digraphen verbindbar?

A:

2.4.1 Definition
Sei D = (V, E, ∂) ein Digraph.

Zwei Knoten v und w des Digraphen D heißen verbindbar, wenn sowohl w von v aus als auch v von w aus erreichbar sind.

Q:

Frage: Wenn ein Digraph keinen Dikreis hat, wie viele Quellen und Senken hat dieser dann?

A:

2.4.13 Aufgabe
Sei D = (V, E, ∂) ein Digraph mit V ist nicht leer.
Gibt es keinen Dikreis in D, so hat D wenigstens eine Quelle und eine Senke.

Q:

Satz von Euler für zusammenhängende Graphen

A:

3.1.6 Bemerkung

Für einen zusammenhängenden Graphen G = (V, E, ∂) mit V ist nicht leer sind äquivalent:

  1. G ist eulersch.
  2. G ist Vereinigung paarweise kantendisjunkter Kreise.
  3. G ist gerade.
Graphentheorie

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten Graphentheorie Kurse im gesamten StudySmarter Universum

Medientheorie

Universität Weimar

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Graphentheorie
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Graphentheorie