DM2

Ein Matching ist eine Menge von Kanten ohne gemeinsame Knoten, sodass keine zwei Kanten einen Knoten teilen.

Ein perfektes Matching ist ein Matching, das alle Knoten des Graphen abdeckt; jeder Knoten ist genau mit einer Kante im Matching verbunden.

Das Heiratssatz besagt, dass ein bipartiter Graph ein Matching hat, das alle Knoten einer Teilmenge abdeckt, wenn und nur wenn für jede Teilmenge S dieser Teilmenge die Anzahl der Nachbarn von S mindestens so groß ist wie die Größe von S.

Die chromatische Zahl eines Graphen ist die minimale Anzahl von Farben, die benötigt wird, um die Knoten so zu färben, dass keine zwei benachbarten Knoten die gleiche Farbe haben.

Der Vier-Farben-Satz besagt, dass jeder planare Graph mit höchstens vier Farben gefärbt werden kann, sodass keine zwei benachbarten Knoten die gleiche Farbe haben.

Ein platonischer Körper entspricht einem regelmäßigen, konvexen Polyeder mit kongruenten Flächen aus regelmäßigen Polygonen, wobei an jeder Ecke die gleiche Anzahl von Flächen zusammentrifft und einen regelmäßigen Graphen bildet.

Die fünf platonischen Körper sind Tetraeder, Würfel (Hexaeder), Oktaeder, Dodekaeder und Ikosaeder.

Ein einfacher Pfad ist ein Pfad in einem Graphen, der keine Knoten wiederholt.

Ein Baum ist ein zusammenhängender Graph ohne Zyklen; er ist azyklisch und zusammenhängend.

Das Handshaking Lemma besagt, dass in einem ungerichteten Graphen die Summe der Grade aller Knoten gleich der doppelten Anzahl der Kanten ist.

Ein eulerscher Kreis ist ein Rundgang, der jede Kante eines Graphen genau einmal benutzt und am selben Knoten startet und endet.

Ein zusammenhängender Graph hat genau dann einen eulerschen Kreis, wenn jeder Knoten einen geraden Grad hat.

Der Grad eines Knotens ist die Anzahl der Kanten, die an ihn angrenzen.

Ein Graph ist zusammenhängend, wenn es zwischen jedem Paar von Knoten einen Pfad gibt.

Ein hamiltonscher Kreis ist ein Rundgang, der jeden Knoten genau einmal besucht und zum Ausgangsknoten zurückkehrt.

Ein eulerscher Kreis durchläuft jede Kante genau einmal, während ein hamiltonscher Kreis jeden Knoten genau einmal besucht.

Ein Baum hat genau dann ein perfektes Matching, wenn er eine gerade Anzahl von Knoten hat.

Ein vollständiger Graph ist ein Graph, in dem jedes Paar von verschiedenen Knoten durch eine eindeutige Kante verbunden ist.

Nein, K3,3 ist nicht planar; er kann nicht ohne Kantenüberschneidungen in der Ebene gezeichnet werden.

Der Satz von Kuratowski besagt, dass ein Graph genau dann nicht planar ist, wenn er einen Teilgraphen enthält, der eine Unterteilung von K5 oder K3,3 ist.

Die Gradfolge ist eine Liste der Grade der Knoten in einem Graphen, normalerweise in absteigender Reihenfolge.

Zwei Graphen sind isomorph, wenn es eine Bijektion zwischen ihren Knotenmengen gibt, die die Nachbarschaftsstruktur erhält; die Graphen haben die gleiche Struktur.

Ein Teilgraph ist ein Graph, der aus einer Teilmenge der Knoten und Kanten eines größeren Graphen gebildet wird.

Ein Spannbaum eines zusammenhängenden Graphen ist ein Teilgraph, der ein Baum ist und alle Knoten des Graphen enthält.

Ein Graph, bei dem jede Kante eine Richtung hat, die von einem Knoten zu einem anderen führt.

Ein Graph, bei dem jeder Kante ein numerischer Wert oder Gewicht zugeordnet ist.

Ein Pfad, der an einem Knoten beginnt und endet, ohne dabei Kanten oder Knoten zu wiederholen (außer dem Start- und Endknoten).

Eine Sequenz von Knoten, bei der jeder aufeinanderfolgende Knoten durch eine Kante verbunden ist.

Einen Graphen, in dem es zwischen jedem Paar von Knoten mindestens einen Pfad gibt.

Ein Kreis, der jede Kante eines Graphen genau einmal durchläuft und zum Startknoten zurückkehrt.

Ein Kreis, der jeden Knoten eines Graphen genau einmal besucht und zum Startknoten zurückkehrt.

In jedem ungerichteten Graphen ist die Summe aller Knotengrade gleich dem Doppelten der Anzahl der Kanten.

Ein zusammenhängender, kreisfreier Graph.

Ein Teilgraph, der ein Baum ist und alle Knoten des ursprünglichen Graphen enthält.