Flashcards zu den Grundlagen der Graphentheorie

Question 1

Was ist ein Graph $G=(V,E)$?

Accepted Answer

Ein Graph ist ein geordnetes Paar $G=(V,E)$, wobei $V$ eine Menge von Knoten (Ecken) ist und $E$ eine Menge von Kanten, wobei jede Kante zwei Knoten verbindet (in einem ungerichteten Graphen ist eine Kante ein ungeordnetes Paar $\{u,v\}$).

Question 2

Was ist der Unterschied zwischen einem Walk, einem Weg und einem Zyklus?

Accepted Answer

Ein Walk darf Knoten/Kanten wiederholen. Ein Weg ist ein Walk ohne wiederholte Knoten. Ein Zyklus ist ein geschlossener Weg (Start = Ende) ohne wiederholte Knoten außer dem ersten/letzten.

Question 3

Was bedeutet es, dass ein Graph planar ist, und wie lautet Eulers Formel für zusammenhängende planare Graphen?

Accepted Answer

Planar bedeutet, dass er in der Ebene ohne Kantenkreuzungen (außer an Knoten) gezeichnet werden kann. Für eine zusammenhängende planare Einbettung gilt $$V-E+F=2,$$ wobei $F$ die Anzahl der Flächen (einschließlich der äußeren Fläche) ist.

Flashcards zu den Grundlagen der Graphentheorie

Mathematik Meistern mit KI

Lernressourcen

Vertraut & Anerkannt