DM2

Eine Menge von Knoten, zwischen denen keine Kanten existieren.

Er besagt, dass der chromatische Index eines Graphen entweder dem maximalen Knotengrad oder diesem plus eins entspricht.

Einen Graphen, der ohne Kantenüberschneidungen in der Ebene gezeichnet werden kann.

Ein Graph, in dem mehrfache Kanten zwischen denselben Knoten erlaubt sind.

Die Anzahl der Kanten, die an einen Knoten angrenzen.

In bipartiten Graphen entspricht die Größe eines minimalen Knotenüberdeckungssets der Größe eines maximalen Matchings.

Einen Graphen, der keine Kreise enthält.

Eine Zuweisung von Farben zu den Knoten eines Graphen, sodass keine zwei benachbarten Knoten die gleiche Farbe haben.

Eine Folge von Kanten, bei der aufeinanderfolgende Kanten jeweils einen gemeinsamen Knoten teilen.

Eine Menge von Kanten, sodass jeder Knoten des Graphen an mindestens einer dieser Kanten beteiligt ist.

Eine maximale zusammenhängende Teilmenge des Graphen.

Ein Graph, der aus einem planaren Graphen entsteht, indem man für jede Fläche einen Knoten setzt und Kanten zwischen Flächen mit gemeinsamer Kante einfügt.

Ein Algorithmus, der Knoten nacheinander färbt und jedem Knoten die kleinstmögliche verfügbare Farbe zuweist.

Ein Spannbaum eines gewichteten Graphen mit minimaler Gesamtkantenlänge.

Eine vollständige Zuordnung ist möglich, wenn jede Teilmenge von Kandidaten mindestens so viele passende Optionen hat wie die Größe der Teilmenge.

Ein einfacher Graph ist ein ungerichteter Graph ohne Schleifen (Kanten, die einen Knoten mit sich selbst verbinden) und ohne Mehrfachkanten zwischen denselben Knotenpaaren.

Ein planarer Graph ist ein Graph, der in der Ebene gezeichnet werden kann, ohne dass sich die Kanten überschneiden.

Die Euler'sche Formel besagt, dass für einen zusammenhängenden planaren Graphen gilt: V - E + F = 2, wobei V die Anzahl der Knoten, E die Anzahl der Kanten und F die Anzahl der Flächen ist.

Der Dijkstra-Algorithmus wird verwendet, um die kürzesten Pfade von einem Startknoten zu allen anderen Knoten in einem Graphen mit nicht-negativen Kantengewichten zu finden.

Ein bipartiter Graph ist ein Graph, dessen Knotenmenge in zwei disjunkte Mengen aufgeteilt werden kann, sodass jede Kante einen Knoten aus einer Menge mit einem Knoten der anderen Menge verbindet.

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.