Färbung von Graphen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:45 Mo 22.06.2009 | | Autor: | Spucky |
| Aufgabe | Aufgabe 2.2 (Graphenalgorithmen)
Es sei G ein ungerichteter Graph, in dem jede von n Ecken mit genau einer Farbe gefärbt werden kann. G heißt zweifärbbar, wenn seine gesamte Eckenmenge so mit zwei verschiedenen Farben gefärbt
werden kann, dass keine zwei Ecken mit gleicher Farbe durch eine Kante verbunden sind.
Entwerfen Sie einen Algorithmus mit worst case-Komplexität O(|E| + |K|) , der G ungefärbt als Input bekommt
und damit folgendes tut:
Wenn G zweifärbbar ist, erhält seine Eckenmenge eine korrekte Zweifärbung.
Wenn G nicht zweifärbbar ist, wird eine entsprechende Antwort ausgegeben.
Nehmen Sie dabei an, dass G durch Nachbarschaftslisten repräsentiert ist.
a) Notieren Sie Ihren Algorithmus (Pseudocode) in möglichst präziser Form, analog den Algorithmen im Kursmaterial. (Tipp: Sie können bekannte Algorithmen auch variieren.)
b) Zeigen Sie anhand der folgenden beiden Testgraphen, wie Ihr Algorithmus arbeitet (und zum richtigen Ergebnis kommt). Geben Sie die Zwischenschritte an.
c) Welche Komplexität hat Ihr Algorithmus im worst case, wenn der Graph als Adjazenzmatrix repräsentiert ist? Bitte mit kurzer Begründung.
Testgraphen:
[Dateianhang nicht öffentlich] |
Hallo Leute,
eine neue Aufgabe. Ich hoffe, Ihr könnt mir helfen.
Also, bei a sollen wir einen Pseudocode schreiben.
Die Aufgaben des gefragten Algorithmus würde ich wie folgt umsetzen:
(1) if G zweifärbbar then
(2) E korrekte Zweifärbung
(3) else Ausgabe: "Der Graph ist nicht zweifärbbar
endif
Aufgrund der Komplexität würde ich dies dann in die Tiefensuche einfließen lassen:
Tiefensuche
(1) initialisiere alle Ecken E als unmarkiert
(2) initialisiere einen leeren Stack
(3) initialisiere n mit einer beliebigen Ecke aus E, markiere n
(4) loop
(5) while alle Nachbarn von n sind markiert do
(6) if Stack ist leer then
(7) break loop { fertig }
else
(8) hole n := pop() vom Stack
endif
endwhile
(9) wähle einen unmarkierten Nachbarn n' von n { Wahlfreiheit! }
(10) B := B [mm] \cup [/mm] {{n, n'}} { update B }
(11) markiere n'
(12) push(n) auf den Stack
(13) n := n'
endfor
(14) if n' zweifärbbar then
(15) E korrekte Zweifärbung
(16) else Ausgabe: "Der Graph ist nicht zweifärbbar
endif
Endloop
Aber das ist sicher falsch.
Ich wäre sehr dankbar, wenn mir jemand helfen könnte.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
-----------------------------------------------------------------------------------------
Folgendes sind Ergänzungen zur Aufgabe, die nicht in der Aufgabenstellung standen:
Tiefensuche
(1) initialisiere alle Ecken E als unmarkiert
(2) initialisiere einen leeren Stack
(3) initialisiere e mit einer beliebigen Ecke aus E, markiere e
(4) loop
(5) while alle Nachbarn von e sind markiert do
(6) if Stack ist leer then
(7) break loop { fertig }
else
(8) hole e := pop() vom Stack
endif
endwhile
(9) wähle einen unmarkierten Nachbarn e' von e { Wahlfreiheit! }
(10) B := B [mm] \cup [/mm] {{e, e'}} { update B }
(11) markiere e'
(12) push(e) auf den Stack
(13) e := e'
Endloop
Breitensuche
(1) initialisiere alle Ecken E als unmarkiert
(2) initialisiere eine Warteschlange mit einer beliebigen Ecke e [mm] \in [/mm] E
(3) while Warteschlange ist nicht leer do
(4) hole e := pop() aus der Warteschlange
(5) for alle Nachbarn e' von e do { Reihenfolgefreiheit! }
(6) if e' ist unmarkiert then
(7) B := B [mm] \cup [/mm] {{e, e'}} { update B }
(8) markiere e'
(9) push(e') in die Warteschlange
endif
endfor
endwhile
Kruskal-Algorithmus
(1) sortiere alle Kanten K nach nichtabsteigenden Gewichten c { evtl. Uneindeutigkeit }
K = {k1, k2, . . . , km} mit c(k1) [mm] \le [/mm] c(k2) [mm] \le [/mm] . . . [mm] \le [/mm] c(km) { der Sortierung! }
(2) for i := 1 to m do
(3) if ki schließt keinen Kreis in B then
(4) B := B [mm] \cup [/mm] {ki} { update B }
(5) endif
endfor
Dijkstra-Algorithmus
(1) initialisiere dist[e] := [mm] \infty [/mm] für e [mm] \in [/mm] E
(2) initialisiere dist[s] := 0
(3) initialisiere eine Prioritätswarteschlange mit s
(4) while Prioritätswarteschlange ist nicht leer do
(5) hole e := pop() aus der Prioritätswarteschlange
(6) if e [mm] \not= [/mm] s then
(7) B := B [mm] \cup [/mm] {kante[e]} { update B }
endif
(8) for alle Nachbarn e' von e do { Reihenfolgefreiheit! }
(9) if dist[e'] > dist[e]+c({e, e'}) then
(10) dist[e'] := dist[e]+c({e, e'})
(11) kante[e'] := {e, e'}
(12) push(e′) in die Prioritätswarteschlange { evtl. Uneindeutigkeit }
endif { der Einsortierung! }
endfor
endwhile
------------------------------------------------------------------------------------------
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:21 Fr 26.06.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
