Inhaltsverzeichnis
Wann hat ein Graph einen Kreis?
Zyklischer Graph Ein Zyklus oder Kreis heißt trivial, wenn er weniger als drei Knoten enthält. Ein Kreis, der genau drei Knoten enthält, wird Dreieck genannt. Einen Graphen ohne Dreieck nennt man dann dreiecksfrei. Als Taillenweite eines Graphen bezeichnet man die Länge eines kürzesten nicht trivialen Kreises.
Ist jeder Baum ein Graph?
Allgemein gilt, dass jeder Baum planar, das heißt ohne Überschneidungen der Kanten gezeichnet werden kann. Je nach Anwendungszweck gibt es weitere Wünsche an die Art der Ausgabe: alle Kanten sind gerade Linien. alle Knoten haben ganzzahlige Koordinaten.
Wann ist ein Graph Hamiltonsch?
ein Graph G, der einen Kreis C besitzt, welcher alle Ecken des Graphen enthält, für den also E(C) = E(G) gilt. Ein Weg W eines Graphen G mit E(W) = E(G) heißt Hamiltonscher Weg. Ist jedes Eckenpaar eines Graphen G durch einen Hamiltonschen Weg verbunden, so spricht man von einem Hamilton-zusammenhängenden Graphen.
Wann ist ein Graph ein Wald?
Definition: Ein (ungerichteter) Graph ist ein Baum, wenn er zusammenhängend ist und keinen Kreis enthält. Ein (ungerichteter) Graph, dessen Zusammenhangskomponenten Bäume sind, wird ein Wald genannt, d.h. jeder kreisfreie Graph ist ein Wald.
Wann ist ein Graph Bipartit?
Ein Graph G wird genau dann als bipartit oder auch paar bezeichnet, wenn sich seine Knoten in zwei disjunkte Teilmengen A und B aufteilen lassen. Zwischen den Knoten innerhalb einer Teilmenge dürfen dabei keine Kanten bestehen.
Was ist ein geschlossener Kantenzug?
Ein geschlossener Kantenzug ist ein Kantenzug, der an seinem Anfangspunkt endet (Nitzsche 2009, S. 238). Durchläuft er dabei jeden seiner Knoten genau einmal, nennt man ihn Kreis (Hußmann 2007, S. 17).
Wann ist eine topologische Sortierung eindeutig?
Eine Reihenfolge, welche alle Bedingungen erfüllt, nennt man topologische Sortierung der Menge anstehender Tätigkeiten. Im Gegensatz zur Sortierung einer Totalordnung ist die Reihenfolge nicht eindeutig, sondern es kann mehrere Möglichkeiten geben.