- gestellte Fragen oder gegebene Antworten wurden upvotet (5 Punkte je Upvote)
- erhaltene Antwort akzeptiert (2 Punkte je Antwort)
- gegebene Antwort wurde akzeptiert (15 Punkte je Antwort)
Erste Frage
Aufrufe: 157
Aktiv: 23.01.2022 um 17:32
0
Es heißt wenn ein Kreis einfach sei, wenn v1,...,vs alle unterschiedlich sind.
Wenn wir den Fall hätten{(v1,v2),(v2,v9),(v9,v1)} das wäre ja ein Kreis, aber v2 kommt 2x vor und v9 auch 2x, die sind ja also gar nicht unterschiedlich oder? Wäre das jetzt kein einfacher Kreis? Wenn ja, was wäre ein einfacher Kreis?
Du hast die Definition falsch verstanden. In der Definition des Pfades müssen die einzelnen Knoten ja mehrfach auftreten, da die eine Kante mit dem Knoten $v_i$ endet und die darauffolgende Kante mit dem Knoten $v_i$ beginnt. Das beeinflusst aber nicht, ob es sich um einen einfachen Pfad oder Kreis handelt. Dein Beispiel ist also ein einfacherr Kreis, denn jeder Knoten wird nur einmal durchlaufen. Der Kreis $p=\{(v_1,v_2),(v_2,v_3),(v_3,v_4),(v_4,v_2),(v_2,v_5),(v_5,v_1)\}$ wäre nicht einfach, da der Knoten $v_2$ zweimal durchlaufen wird. Aber du siehst, dass eine Kante immer mit dem Knoten endet, mit der die folgende Kante beginnt. Ansonsten hätte man keine aufeinanderfolgenden Kanten. Du siehst aber auch, dass die hier für $v_2$ zweimal der Fall ist, weshalb der Knoten eben doppelt durchlaufen wird.