Hi,
ich habe ein Problem mit dieser Aufgabe und hoffe hier eine Hilfestellung zu bekommen. Eine Lösung erwarte ich nicht, wenn mir jemand nur einen Hinweis geben könnte wäre ich schon froh:
Gegeben sei ein ungerichteter Graph mit n Ecken:
a) Skizzieren Sie einen Algorithmus mit einer Komplexität von O(n) (im „Worst Case“), der den Graphen daraufhin testet, ob er azyklisch ist, also keine Kreise besitzt (Antwort: „ja“ oder „nein“). Nehmen sie dabei an, dass der Graph durch Nachbarschaftslisten repräsentiert ist.
Meine Überlegung war bisher:
ich muss folgendes Nachweisen:
Ein geschlossener Weg (also ein geschlossener Kantenzug, der keine Ecke mehrmals enthält) wird als Kreis bezeichnet.
Also erste Kante gleich letzte Kante (geschlossener Weg - wie das bei einem ungerichteten Graphen?) und keine Ecke kommt mehrmals vor. Dazu habe ich mir schon einen Algorithmus überlegt, der überprüft ob keine Ecke mehr als 2 Verbindungen/Kanten zu anderen Ecken hat.
Wisst Ihr mehr?
Vielen Dank und Gruß
Bonkers
Informatik: geschlossene Wege
Hallo,
ich habe ein Problem mit dieser Aufgabe und hoffe hier eine
Hilfestellung zu bekommen. Eine Lösung erwarte ich nicht, wenn
mir jemand nur einen Hinweis geben könnte wäre ich schon froh:
Das Brett Informatik wäre um Längen besser dafür. Ich probiere es trotzdem mal…
Gegeben sei ein ungerichteter Graph mit n Ecken:
a) Skizzieren Sie einen Algorithmus mit einer Komplexität von
O(n) (im „Worst Case“), der den Graphen daraufhin testet, ob
er azyklisch ist, also keine Kreise besitzt (Antwort: „ja“
oder „nein“). Nehmen sie dabei an, dass der Graph durch
Nachbarschaftslisten repräsentiert ist.
(Hervorhebung von mir>
Meine Überlegung war bisher:
ich muss folgendes Nachweisen:
Du musst gar nix nachweisen. Du sollst einen Algorithmus angeben.
Ein geschlossener Weg (also ein geschlossener Kantenzug, der
keine Ecke mehrmals enthält) wird als Kreis bezeichnet.
Also erste Kante gleich letzte Kante (geschlossener Weg - wie
das bei einem ungerichteten Graphen?) und keine Ecke kommt
mehrmals vor. Dazu habe ich mir schon einen Algorithmus
überlegt, der überprüft ob keine Ecke mehr als 2
Verbindungen/Kanten zu anderen Ecken hat.
Wisst Ihr mehr?
Wenn ich gerade keinen sehr grossen Denkfehler habe, dann ist ein Graph ohne geschlossene Kantenzüge ein Wald, also eine Menge von Bäumen.
Du kannst das überprüfen, indem du alle Knoten abläufst und sie markierst. Von jedem Knoten aus besuchst du alle seine Nachbarn, und markierst die ebenfalls. Sobald du einen schon markierten Knoten besuchst, hast du einen Zyklus gefunden. Wenn du niemals einen schon markierten Knoten gefunden hast und jeden Knoten besucht hast (entspricht Laufzeit O(n)), dann ist er Zyklenfrei.
HTH und Grüße,
Moritz
Hallo,
also mit dem Tiefensuchealgorithmus kann man das Problem leicht lösen.
http://www.computerbase.de/lexikon/Tiefensuche
Kommt man über eine nicht benutzte Kante, zu einem besuchten Knoten
->Zyklus ansonsten durchläuft man alle Kanten und Knoten.
Gruss Peter