Mathematik Graphentheorie – Grundbegriffe und Wege
Karteikarten zum Thema „Mathematik“ · 15 Karten · von atrio. Beispiele: Was ist ein Graph in der Graphentheorie? · Was sind Knoten und Kanten?
Karten
15 KartenWas ist ein Graph in der Graphentheorie?
Rückseite
Ein Graph G = (V, E) besteht aus einer Knotenmenge V und einer Kantenmenge E, die Paare von Knoten verbindet.
Was sind Knoten und Kanten?
Rückseite
Knoten (Ecken) sind die Grundelemente, Kanten verbinden zwei Knoten miteinander und stellen Beziehungen dar.
Was ist der Grad eines Knotens?
Rückseite
Der Grad eines Knotens ist die Anzahl der an ihm inzidierenden Kanten; bei gerichteten Graphen unterscheidet man Ein- und Ausgrad.
Was unterscheidet einen gerichteten von einem ungerichteten Graphen?
Rückseite
Bei gerichteten Graphen haben Kanten eine Richtung (Bögen), bei ungerichteten Graphen sind Kanten symmetrische Verbindungen ohne Orientierung.
Was ist ein Weg in einem Graphen?
Rückseite
Ein Weg ist eine abwechselnde Folge von Knoten und Kanten, bei der jede Kante ihre Endknoten verbindet; Knoten dürfen sich wiederholen.
Was ist ein einfacher Weg?
Rückseite
Ein einfacher Weg enthält keine wiederholten Knoten – außer eventuell Start- und Endknoten bei einem Zyklus.
Was ist ein Zyklus in einem Graphen?
Rückseite
Ein Zyklus ist ein geschlossener einfacher Weg mit mindestens drei Kanten, bei dem Start- und Endknoten identisch sind.
Was bedeutet zusammenhängend bei Graphen?
Rückseite
Ein ungerichteter Graph ist zusammenhängend, wenn zwischen je zwei Knoten mindestens ein Weg existiert; bei gerichteten Graphen spricht man von starker Zusammenhang.
Was ist ein Baum in der Graphentheorie?
Rückseite
Ein Baum ist ein zusammenhängender, kreisfreier Graph; er hat genau n-1 Kanten für n Knoten und genau einen Weg zwischen je zwei Knoten.
Was ist ein vollständiger Graph?
Rückseite
Ein vollständiger Graph K_n enthält alle möglichen Kanten zwischen n Knoten – jede Knotenpaar ist direkt verbunden.
Was ist ein bipartiter Graph?
Rückseite
Ein bipartiter Graph hat eine Knotenmenge, die in zwei disjunkte Teilmengen zerfällt, wobei Kanten nur zwischen den Teilmengen verlaufen.
Was ist der Unterschied zwischen Euler- und Hamilton-Weg?
Rückseite
Ein Euler-Weg durchläuft jede Kante genau einmal, ein Hamilton-Weg besucht jeden Knoten genau einmal.
Was ist eine Brücke in einem Graphen?
Rückseite
Eine Brücke ist eine Kante, deren Entfernung die Anzahl der Zusammenhangskomponenten des Graphen erhöht.
Was ist ein induzierter Teilgraph?
Rückseite
Ein induzierter Teilgraph entsteht durch Auswahl einer Knotenuntermenge und Übernehmen aller Kanten, deren beide Endknoten in der Teilmenge liegen.
Was besagt das Handshaking-Lemma?
Rückseite
Die Summe aller Knotengrade in einem ungerichteten Graphen ist doppelt so groß wie die Anzahl der Kanten – jedes Kantenende wird einmal gezählt.