Untergruppen-Bildung in DAGs < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 10:49 Do 17.04.2008 | | Autor: | eram |
| Aufgabe | Innerhalb eines DAG (directed acyclic graph, gerichteter kreisfreier Graph) soll der größtmögliche Sub-Dag gefunden werden für den gilt:
- nur durch eine Eingangskante
- und nur eine Ausgangskante verbindet den Sub-Graph mit dem Rest-Graph. |
Sehr geehrte Kollegen,
auf der Suche nach einem passenden Algorithmus bin ich bisher auf Färbungen, Sortierungen usw. gestoßen.
Mir fehlt die Orientierung.
Ein Hinweis in welcher Ecke ich suchen sollte wäre schon sehr hilfreich. Wenn mir natürlich jemand gleich den Namen eines Algrithmuses nennen könnte ...
Ich habe diese Frage (noch) in keinem Forum auf anderen Internetseiten gestellt.
Bester Gruß,
Eduard
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:52 Sa 19.04.2008 | | Autor: | RedHead |
Also spontan fällt mir dazu Travelling Salesman ein...dazu gibt es diverse Tools die das Problem erläutern...aber ich muss gestehen ich bin grad nicht mehr in dem Thema drin...ich könnte am Donnerstag nochmal intesiver suchen aber vielleicht hilft dir das ja schon als Tipp.
ansonsten weiß ich das ich das damals mit hilfe von:
Ottmann, Thomas & Widmayer, Peter - Algorithmen und Datenstrukturen
gelernt hab gibt es auch als PDF
MfG RedHead
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:20 Fr 25.04.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
