MST/Branching lineare Zeit, < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 16:25 Sa 16.03.2013 | | Autor: | nobodon |
| Aufgabe 1 | | Sei G ungerichtet und c: E -> {2,3,5,7,11}, geben Sie einen linearen Algo an der ein Min-spanning-Tree bestimmt. |
| Aufgabe 2 | Gegeben ein Digraph, mit Kantenkapazitäten c. Gesucht ist ein Algo in O(n+m) der ein Branching B angibt, mit
c(B) >= 0.5 * C(B') für alle Branching B'. |
Ich denke Aufgabe sind ziemlich gleich, vll reicht es schon eine Aufgabe zu lösen.
Zur 1 Dachte zuerst an Kruskal, denn man die Kanten in linearen Zeit sortieren O(log(5)*m). Aber Kreise lassen sich nicht konstant eleminieren, deswegen geht das nciht. Dann wollte ich es mit Prim machen:
V(T):= v, v beliebig
While V(T) != V(G) DO
if es existiert Kante mit c(e) < 5
if es existiert Kante mit c(e) = 2, füge diese Kante zu T hinzu
...
usw, d.h. max 3 if-Abfragen, aber dann ist aufgefallen dass eine Abfrage O(delta(V(T))) Laufzeit hat, denn man musst ja alle adjazenten Knoten überprüfen im worst case, also ist dies auch nciht linear.
Bei der 2 hab ich ähnliche Probleme.
Es reicht erstmal wenn mir bei der 1 weitergeholfen wird.
Schönes WE nco,
hoffe ihr könnt mir so schnell wie möglich helfen, denn Montag schreibe ich klausur :P
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Mo 18.03.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
