Graphen und Algorithmen Flashcards
Ungerichteter Graph
Der hat Knoten und Kanten (Linie)
Wie viele Knoten muss ein ungerichteter Graph minimal haben?
1
Wie viele Kanten muss ein ungerichteter Graph minimal haben?
0
Loops und multiple Kanten in einem ungerichteten Graph ist
Nicht erlaubt
Gerichteter Graph
Der hat Knoten und Kanten (Pfeile)
Loops in einem gerichteten Graph ist
erlaubt
Zwei Pfeile von a nach b in einem gerichteten Graph ist
Nicht erlaubt
Ein Pfeil von a nach b + ein Pfeil von b nach a in einem gerichteten Graph sind
erlaubt
Eine Kante benachbart mit einem Knoten, dann sie sind
Incident
Eine Kante benachbart mit einer anderen Kante / ein Knoten benachbart mit einem anderen Knoten, dann sie sind
adjacent
n ist
Die Anzahl der Knoten
Teilgraph von G ist
G’ = (V’, E’) mit V’ ⊆ V und E’ ⊆ E
Vollständiger Graph ist
Ein Graph, deren Knoten miteinander verbunden sind. Vollständiger Graph mit n Knoten heißt Kn.
Der Grade δ(v)
die Anzahl der Knoten, die mit Kanten incident sind.
Regulärer Graph
K-regulärer Graph ist, wenn jeder Knoten den gleichen Grad hat
Sum der δ(v) macht
2 x | E |
