bipartiter Graph Algorithmus < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo an alle :)
Wie muss ein Algorithmus aussehen um festzustellen, dass ein Graph bipartit ist? Ich habe es schon selber versucht aber ich habe noch Schwierigkeiten selber einen Algorithmus zu schreiben.
Kann mir jemand zeigen wie solch ein Algorithmus aussehen muss um mir den Einstieg zu erleichtern?
Danke :)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:02 So 20.01.2008 | | Autor: | Gilga |
Ist äquivalent zu 2-färbbar.
Also bei einem Knoten anfangen (Weiß) und jeden nachbarknoten (Schwarz) .... und sofort bis alle gefärbt oder ein Widerspruch ensteht .... Weiß und Schwarz
... sonderfälle bzgl. nicht zusammenhängende Graphen beachten ,..... etc.
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:10 Mi 06.02.2008 | | Autor: | Dadalino |
Welche Laufzeit hat denn dieser Algorithmus? Brauche einen Algorithmus, der einen Graphen G=(V,E) in O(V+E) Zet auf die bipartit Eigenschaft prüft.
Außerdem... Wie fang ich in dem Graphen an zu suchen?
Also später schreibe ich:
if node = white
if node.neighbours = white
throw ERROR
if node.neighbours = Null
node.neighbours = black
und das selbe mit schwarz. aber wie fang ich an? brauch einfach nur die ersten zeilen in pseudocode...
Danke schonmal
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:54 Do 07.02.2008 | | Autor: | bazzzty |
> Welche Laufzeit hat denn dieser Algorithmus? Brauche einen
> Algorithmus, der einen Graphen G=(V,E) in O(V+E) Zet auf
> die bipartit Eigenschaft prüft.
> Außerdem... Wie fang ich in dem Graphen an zu suchen?
In dem Graphen kannst Du an einem beliebigen Knoten anfangen zu suchen, den färbst Du zum Beispiel weiß.
> Also später schreibe ich:
>
> if node = white
> if node.neighbours = white
> throw ERROR
> if node.neighbours = Null
> node.neighbours = black
> und das selbe mit schwarz. aber wie fang ich an? brauch
> einfach nur die ersten zeilen in pseudocode...
Um die gewünschte Laufzeit hinzubekommen, mußt Du allerdings sicherstellen, daß Du nicht immer wieder jeden Knoten überprüfen mußt, sprich: Du brauchst ein System. Dafür brauchst Du eine Liste oder irgendeinen andere Datenstruktur D, in die man Elemente einfügen kann, und aus der man ein Element holen&entfernen kann.
markiere irgendeinen Knoten v weiß.
füge v zu D zu
solange D nicht leer ist {
entnimm Element x aus D
für alle Nachbarn y von x {
wenn y ungefärbt ist, färbe y anders als x und füge y zu D hinzu
wenn y dieselbe Farbe wie x hat, ist der Graph nicht bipartit
}
}
Warum hat das die gewünschte Laufzeit? Jeder Knoten wird nur einmal in D eingefügt, nämlich nur, wenn er gerade eingefärbt wird. Also ist jeder Knoten nur einmal x. Während der Behandlung von x passiert aber nur für jede Kante von x etwas. Insgesamt also für jede Kante nur zweimal, nämlich von jeder Seite einmal. Das sind insgesamt O(V+E). Ich gehe gerne noch detaillierter darauf ein, wenn das unklar ist.
Als Anmerkung: Wenn D eine Liste ist, in die man hinten anfügt und vorne entfernt, dann ist das eine Breitensuche, das sollte ein Begriff sein, oder? Wann ist es eine Tiefensuche?
|
|
|
|
