azyklischer ungerichteter graph |
| 07.12.2004, 23:36 | Dana20w | Auf diesen Beitrag antworten » |
| azyklischer ungerichteter graph wisst ihr wie man bei einem ungerichteten graphen, welcher durch eine nachbarschaftsliste gegeben ist prüfen kann ob er kreise enthält oder nicht ? Hat es etwas mit dem Grad einer Ecke zu tun ? Sitze schon seit stunden an dieser AUfgabe 
aahhhIch freue mich über jeden Hinweis ! Gruß, Dana20w ------------------- konkrete Aufgabe: Gegeben sei ein ungerichteter Graph mit n Ecken. 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. Falls der Graph als Adjazenzmatrix dargestellt ist – welche Komplexität hat ein darauf basierender Algorithmus, der den Graphen auf Kreisfreiheit testet? |
||
| 08.12.2004, 18:25 | riwe | Auf diesen Beitrag antworten » |
| RE: azyklischer ungerichteter graph ist schon sehr, sehr lange her, aber vielleicht hilft es: a) man ersetzt den ungerichteten durch einen entsprechenden gerichteten graphen gleicher knotenmenge. b) dann gilt:sei G ein gerichteter kreisfreier graph. dann kann man die knoten derart numerieren, dass für jeden bogen die nummerdes startknotens kleiner ist als die des zielknotens. literatur: walter, nägler graphen, algorithmen, programme (s.53) werner wenn du es brauchst, schick ich dir die verbal, bzw. pascalalgorithmen dazu |
||
| 11.12.2004, 17:27 | Dana20w | Auf diesen Beitrag antworten » |
Hallo, vielen Dank für die schnelle Antwort ! Aber eins verstehe ich nicht: Bei gerichteten Graphen ist doch schon ein Kreis vorhanden, wenn 1->2 und 2->1 ... bei ungerichteten müssen doch mindestens 3 Kanten für den Kreis vorhanden sein, weil ja sonst jede Kante zwischen 2 Punkten schon ein Kreis wäre. Demzufolge müsste der Algorithmus für ungerichtete Graphen ganz anders sein, als bei gerichteten Oder ? Viele Grüße Danaw20 |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
