Algorithmus gesucht < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 00:18 Mo 29.01.2007 | | Autor: | Bastiane |
| Aufgabe | | Gegeben sei ein stark zusammenhängender Digraph G mit nichtnegativen, reellen Kantengewichten c. Finde [mm] f:E(G)\to\IN, [/mm] so dass der Graph, der f(e) Kopien von [mm] $e\in [/mm] E(G)$ und $V(G)$ als Knotenmenge enthält, eulersch ist mit [mm] \summe_{e\in E(G)}c(e)f(e) [/mm] minimal. Man gebe einen polynomiellen Algorithmus hierfür an. |
Hallo zusammen!
Erstmal eine Frage zum Verständnis der Formulierung: "Kopien" bedeutet, dass ich die Kanten mehrfach nehme, ja? Und die Funktion f gibt mir genau an, wie oft ich welche Kante nehme. Ich denke, das habe ich richtig verstanden!?
Aber heißt es auch, dass ich die Kante nur so, wie sie ist, mehrmals nehmen kann, also als gerichtete Kante? Ich kann sie also nicht in die andere Richtung nehmen!?
Ok - wenn das geklärt ist, dann möchte ich noch fragen, ob irgendwer eine Idee hat, wie man das ungefähr machen könnte.
Ach ja, damit ein Digraph eulersch ist, muss für jeden Knoten die Anzahl der eingehenden Kanten gleich der der ausgehenden sein.
Naiv könnte man natürlich irgendwie ansetzen, dass man die Knoten nach der Anzahl "fehlender" Kanten sortiert und dann z. B. bei dem Knoten anfängt, bei dem am wenigsten fehlt und dort dann eine Kante "hinzufügt". Das Problem ist nur, dass das die Summe nicht beachtet und die muss ich ja irgendwie da mit reinbringen.
Um die Summe zu beachten bzw. zu minimieren, sollten natürlich möglichst billige Kanten häufiger, und teurere seltener vorkommen. Aber wie bringe ich da dann die Gradbedingung mit rein?
Vielleicht hat ja jemand einen brauchbaren Ansatz?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
| |
|
Hallo liebe Bastiane,
die Aufgabenstellung hast Du meiner Ansicht nach richtig verstanden. Und wenn [mm] e=(u,v)\in [/mm] E, aber [mm] (v,u)\notin [/mm] E, dann kann man (v,u) auch gar nicht verwenden, d.h. man darf nicht Inverse von Kanten einfach so nehmen, wenn sie nicht im Graphen schon vorhanden sind.
Bedeutet denn [mm] \IN [/mm] die Menge der natürlichen Zahlen ohne 0 ? Ich denke mal, dass dem so ist, und dann müssen wir jede vorhandene Kante auch tatsächlich mindestens einmal nehmen.
- Kann man das nicht mit MinCostFlow machen ? Habt Ihr eine Aussage, dass es bei ganzzahligen Kapazitäten und
ganzzahligen Funktionen [mm] b\colon V\to\IN [/mm] immer einen ganzzahligen MinCostFlow, also [mm] f\colon E\to\IN_{0} [/mm] gibt ?
- Falls ja: Kann folgendes funktionieren ?
Wir setzen für jeden Knoten den b-Wert gleich Outdegree - Indegree (oder umgekehrt - je nachdem, wie bei Euch die Konvention war). Es soll also zB in einen Knoten, der 3 ausgehende, aber nur eine eingehende Kante hat, der Wert 2 reinfliessen.
Die Knoten, die schon balanciert sind, bekommen also b=0.
Wenn man dann nen ganzzahligen MinCostFlow bekäme, so würd man einfach jede Kante e sooft zusätzlich (!)
nehmen, wie der Flußwert der Kante ist.
Könnte das klappen ?
Lieben Gruss,
Mathias
|
|
|
|
