Fabian Rohlik
← all Quizzes
Sei $G$ ein zusammenhängender Graph. Wenn das Entfernen einer Kante $e$ $G$ zusammenhängend lässt, dann enthält $G$ einen Zyklus.
Ein ungerichteter Graph ist genau dann Eulersch, wenn er zusammenhängend ist und alle Knoten geraden Grad haben.
Ein zusammenhängender Graph muss einen Zyklus enthalten.
Sie möchten den energieeffizientesten Weg für ein E-Bike finden, bei dem Bergabfahren den Akku auflädt (negative Gewichte). Es existieren keine negativen Zyklen. Welcher Algorithmus?
Die Zeitkomplexität von BFS auf einem Graphen mit $n$ Knoten und $m$ Kanten ist $O(n + m)$.