
Die Suche ergab 20 Treffer
- 9. Feb 2009 19:53
- Forum: Effiziente Graphenalgorithmen
- Thema: Laufzeitkomplexitäten von MST-Algorithmen
- Antworten: 2
- Zugriffe: 227
Re: Laufzeitkomplexitäten von MST-Algorithmen
Es gilt O(m log m) = O(m log n), da m max. aus O(n^2) und log(n^2) = 2*log(n) wenn ich in Mathe richtig aufgepasst habe 

- 8. Feb 2009 13:07
- Forum: Effiziente Graphenalgorithmen
- Thema: Planare Graphen
- Antworten: 4
- Zugriffe: 288
Re: Planare Graphen
Zu diesem Thema habe ich auch eine Frage: Wie werden die Kanten beim dualen Graphen im Falle von gerichteten Graphen gerichtet? Im Skript heisst es dazu auf Folie 312 "In the directed case, we orient e* = (f1, f2) in such a way that f1 is the face “to the right” when traversing the Jordan curve corr...
- 7. Feb 2009 12:01
- Forum: Effiziente Graphenalgorithmen
- Thema: Fragen zu Kapitel 4
- Antworten: 14
- Zugriffe: 814
Re: Fragen zu Kapitel 4
Warum ein Zyklus im Vorgängergraph zwangsläuig negative Länge hat, ist klar. Die Frage ist: WIE erkennt man einen Zyklus in O(n)? Kann man nicht argumentieren, dass der Vorgängergraph nur m=n-1 Kanten besitzt. Denn so ist er nach meinem Verständnis definiert (jedem Knoten wird ein Vorgänger eindeut...
- 3. Feb 2009 22:10
- Forum: Effiziente Graphenalgorithmen
- Thema: Fragen zu Kapitel 4
- Antworten: 14
- Zugriffe: 814
Re: Fragen zu Kapitel 4
Ich habe auch noch eine: Auf Folie 109 steht "Label setting algorithms are applicable only to directed acyclic graphs (DAGs) OR to graphs with non-negative arc lengths". Jedoch ist auf Folie 133 schon ein Beispiel angegeben für einen DAG wo Dijkstra nicht funktioniert, oder?
- 3. Feb 2009 12:26
- Forum: Effiziente Graphenalgorithmen
- Thema: Kanten beim Topsort
- Antworten: 4
- Zugriffe: 287
Re: Kanten beim Topsort
Also ich glaube dass der Graph links nicht ganz zum Ergebnis rechts passt. Die Kante (5,4) taucht im Topsort Graphen nicht auf, dafür aber Kanten (3,4) und (5,7) die der Graph links nicht enthält, oder sehe ich das falsch?
- 26. Jan 2009 21:06
- Forum: Effiziente Graphenalgorithmen
- Thema: Übung 9, Aufgabe 4 (Knotenüberdeckung)
- Antworten: 5
- Zugriffe: 708
Re: Übung 9, Aufgabe 4 (Knotenüberdeckung)
Bei deinem Beispiel hast du die Bipartition A={a,c,b} und B={e,d,f}. Jetzt hab ich angenommen es wurde bereits ein maximales matching gefunden. Hier zb die Kanten (c,e) und (b,d) (geht auch mit jedem anderen max. Matching). Jetzt musst du für jede Kante überlegen, welchen Knoten du in die Knotenüber...
- 26. Jan 2009 17:44
- Forum: Effiziente Graphenalgorithmen
- Thema: Übung 9, Aufgabe 4 (Knotenüberdeckung)
- Antworten: 5
- Zugriffe: 708
Re: Übung 9, Aufgabe 4 (Knotenüberdeckung)
Also ich habe angenommen, dass ich bereits ein Matching mit maximaler Kardinalität kenne (und natürlich die Bipartition) und daraus kann man dann ganz einfach eine minimale Knotenüberdeckung finden (man muss auf die M-alternierenden Pfade achten). Und in bipartiten Graphen ist -- wenn ich das in der...
- 24. Nov 2008 20:54
- Forum: Effiziente Graphenalgorithmen
- Thema: Arbeitsaufwand der Übungen
- Antworten: 5
- Zugriffe: 461
Re: Arbeitsaufwand der Übungen
Hallo, also ich kann dem ersten Beitrag zustimmen. Ich mache die Übungen meistens am Wochenende da ich während der Woche wegen Vorlesungen und Arbeiten nicht viel Zeit dafür habe. Bei mir geht das auch komplett dafür drauf zudem bin ich dann Montags noch nicht ganz mit allem fertig. Das Argument mit...
- 13. Jan 2008 17:25
- Forum: Archiv
- Thema: Klausurergebnisse hängen aus
- Antworten: 7
- Zugriffe: 1082
Re: Klausurergebnisse hängen aus
Mi., 16.01.2008, 15.00h – 16.00h, Raum A313 wurde in der Übung am Donnerstag bekanntgegeben
- 7. Dez 2007 11:40
- Forum: Archiv
- Thema: Bonus theoretische Übungsaufgaben
- Antworten: 3
- Zugriffe: 1162
Bonus theoretische Übungsaufgaben
Hallo,
gibt es eigentlich schon eine Bonusregelung für die Punkte in den theoretischen Übungsaufgaben? Es hieß ja am Anfang, das diese einen Bonus von einem 0.3 Notenschritt ausmachen. Wieviel Prozent der Punkte muss man denn dafür erreichen. Wäre halt schon gut zu wissen.
gibt es eigentlich schon eine Bonusregelung für die Punkte in den theoretischen Übungsaufgaben? Es hieß ja am Anfang, das diese einen Bonus von einem 0.3 Notenschritt ausmachen. Wieviel Prozent der Punkte muss man denn dafür erreichen. Wäre halt schon gut zu wissen.
- 27. Nov 2007 20:50
- Forum: Archiv
- Thema: brauche dringend Hilfe
- Antworten: 4
- Zugriffe: 941
Kann auch folgendes kleines rmi Tutorial empfehlen, hat mir zumindest sehr geholfen http://www.mm.informatik.tu-darmstadt.d ... orial.html
- 13. Nov 2007 20:19
- Forum: Archiv
- Thema: FIFO vs. Causal Multicast
- Antworten: 12
- Zugriffe: 1620
Erstmal danke fuer die Antworten, hat mir sehr geholfen. Muss jetzt nicht richtig sein, was ich sage, aber anders kann ich mir auch keinen Reim darauf machen. Und (verblüffend ähnliche ^^) andere Foliensätze anderer Unis haben das eben so drin (FIFO -->g, kausal -->) So sehe ich das auch. Das einzig...
- 11. Nov 2007 16:13
- Forum: Archiv
- Thema: FIFO vs. Causal Multicast
- Antworten: 12
- Zugriffe: 1620
FIFO vs. Causal Multicast
Ich verstehe den Unterschied zwischen FIFO und causal Multicast von Folie 51 nicht. Für mich sehen die Definitionen irgendwie gleich aus. Kann mir das vielleicht jemand mit eigenen Worten erklären? Wäre nett 

- 29. Okt 2007 11:17
- Forum: Archiv
- Thema: Aufgabe 2.1
- Antworten: 3
- Zugriffe: 880
Aufgabe 2.1
Sollen bei der Aufgabe 2.2 a),b),c) jeweils alle Ereignispaare fuer die das zutrifft aufgeschrieben werden, oder reicht da jeweils ein Beispiel mit einem Paar?