(Twitter)
0
Hey,
ich glaube der Ford-Fulkerson auf einem geeigneten Netzwerk sollte dir hier weiter helfen. Dafür musst du deinen Graphen zu einem Netzwerk erweitern, in dem du 2 zusätzliche Knoten ergänzt und die jeweiligen Kanten mit den passenden Kapazitäten (1) hinzufügst.
Innerhalb des Ford Fulkerson Algorithmus schaust du dir dann augmentierende Pfade an, die deinen Flusswert erhöhen und somit dein Matching vergrößern.
Also für eine solche Art von komplexen Aufgaben gibt es nicht DIE einfache Lösung. Ich hoffe der Algorithmus ist euch bekannt. Dann sollte das darüber machbar sein.
VG
Stefan
ich glaube der Ford-Fulkerson auf einem geeigneten Netzwerk sollte dir hier weiter helfen. Dafür musst du deinen Graphen zu einem Netzwerk erweitern, in dem du 2 zusätzliche Knoten ergänzt und die jeweiligen Kanten mit den passenden Kapazitäten (1) hinzufügst.
Innerhalb des Ford Fulkerson Algorithmus schaust du dir dann augmentierende Pfade an, die deinen Flusswert erhöhen und somit dein Matching vergrößern.
Also für eine solche Art von komplexen Aufgaben gibt es nicht DIE einfache Lösung. Ich hoffe der Algorithmus ist euch bekannt. Dann sollte das darüber machbar sein.
VG
Stefan
Diese Antwort melden
Link
geantwortet
el_stefano
M.Sc., Punkte: 6.68K
M.Sc., Punkte: 6.68K
Hallo Stefan, vielen Dank für deine Antwort. Leider habe ich mit Netzwerken nichts am Hut, ich bin in der algorithmischen Mathematik gefangen. Mein Problem ist eigetlich, dass mir immer noch nicht ganz klar ist, was ein Maximales Matching genau bedeutet...
─
svepo
25.03.2021 um 10:08
Naja ein Netzwerk ist einfach ein Graph mit bestimmten Kapazitäten auf den Kanten. Aber wenn ihr das nicht hattet, werdet ihr wohl auch noch nicht den Ford Fulkerson oder Edmonds Karp Algorithmus gehabt haben. Soweit ich weiß, ist das aber in der Optimierung das Standard Vorgehen zur Bestimmung maximaler Matchings.
Was ein Matching ist hast du verstanden? Maximales Matching bedeutet nun, dass du die maximale Anzahl an Kanten in deinem Matching hast. Ein Matching ist an sich ja eine Teilmenge deiner Kantenmenge, also sind bestimmte Kanten zwischen deinen zwei Bipartitionen, die deine Matching Bedingung erfüllen.
Du willst nun möglichst viele Kanten in dieses Matching hinein tun. ─ el_stefano 25.03.2021 um 10:12
Was ein Matching ist hast du verstanden? Maximales Matching bedeutet nun, dass du die maximale Anzahl an Kanten in deinem Matching hast. Ein Matching ist an sich ja eine Teilmenge deiner Kantenmenge, also sind bestimmte Kanten zwischen deinen zwei Bipartitionen, die deine Matching Bedingung erfüllen.
Du willst nun möglichst viele Kanten in dieses Matching hinein tun. ─ el_stefano 25.03.2021 um 10:12
Also ein Matching ist maximal, wenn durch hinzufügen einer weiteren Kante die Matchingbedingung verletzt wird.
─
el_stefano
25.03.2021 um 10:24
Soweit klar, aber nehmen wir an, es handelt sich um bipartite Graphen ohne jegliche Bedingung und ohne vorgegebenes Matching, nur mit ungewichteten Kanten?
─
svepo
25.03.2021 um 10:25
Hast du einen konkreten Graphen vorgegeben? Dann könntest du den hier reinposten. Oder soll es allgemein sein?
Wenn die oben genannten Algorithmen nicht bekannt sind, dann bleibt scheinbar wirklich nur ausprobieren. ─ el_stefano 25.03.2021 um 10:27
Wenn die oben genannten Algorithmen nicht bekannt sind, dann bleibt scheinbar wirklich nur ausprobieren. ─ el_stefano 25.03.2021 um 10:27
Ich hab mal einen als Bsp. in die Frage gepostet.
─
svepo
25.03.2021 um 10:43
Hier müsste \(M =\{ (1,B), (2,D), (4,A) \} \) ein maximales Matching sein. Es ist nicht eindeutig, weil du auch die Kante \( (3,D) \) hinzufügen könntest, wofür du aber \( (2,D) \) aus dem Matching streichen müsstest. Bei Knoten \( 1 \) hast du auch die Wahl, ob du die Kante \( (1,B) \) oder \( (1,C) \) ins Matching tust.
─
el_stefano
25.03.2021 um 11:59
Achja und herausgefunden habe ich das über "probieren". Habe erstmal geguckt, was passiert, wenn ich \( (1,A) \) ins Matching nehme, dann was bei Knoten \( 2 \) möglich ist. Dann sieht man aber recht schnell, dass da dann nur 2 Kanten ins Matching können. Um 3 Kanten ins Matching zu bekommen, musst du das dann eben entsprechend anpassen.
─
el_stefano
25.03.2021 um 12:01
Also doch probieren.
Die Maximalität wurde in diesem Beispiel mit dem Satz von König und der Knotenüberdeckung bewiesen. Aber was genau bedeutet "Knotenüberdeckung"? ─ svepo 25.03.2021 um 12:13
Die Maximalität wurde in diesem Beispiel mit dem Satz von König und der Knotenüberdeckung bewiesen. Aber was genau bedeutet "Knotenüberdeckung"? ─ svepo 25.03.2021 um 12:13
Hab's, vielen Dank!
─
svepo
25.03.2021 um 12:22
Ja stimmt in Bipartiten Graphen besagt der Satz von König, dass die minimale Knotenüberdeckungszahl der Anzahl an Matchingkanten entspricht.
Eine Knotenüberdeckung ist definiert als Teilmenge der Knotenmenge, die von jeder Kante mindestens einen Endknoten enthält. Du schaust dir also alle Kanten an und einer der Endpunkte liegt dann eben in der Knotenüberdeckung. Ziel ist es nun möglichst wenig Knoten in der Knotenüberdeckung zu haben.
Im Allgemeinen ist dieses Problem auch NP-schwierig. Für bipartite Graphen folgt aus dem Satz von König, dass man die minimale Knotenüberdeckungszahl mit dem maximalen Matching finden kann, da man effizient das maximale Matching (z.B. mittels Edmonds-Karp) in polynomieller Zeit berechnen kann.
Also selbst für die minimale Knotenüberdeckung benutzt man die maximale Matching Algorithmen. ─ el_stefano 25.03.2021 um 12:31
Eine Knotenüberdeckung ist definiert als Teilmenge der Knotenmenge, die von jeder Kante mindestens einen Endknoten enthält. Du schaust dir also alle Kanten an und einer der Endpunkte liegt dann eben in der Knotenüberdeckung. Ziel ist es nun möglichst wenig Knoten in der Knotenüberdeckung zu haben.
Im Allgemeinen ist dieses Problem auch NP-schwierig. Für bipartite Graphen folgt aus dem Satz von König, dass man die minimale Knotenüberdeckungszahl mit dem maximalen Matching finden kann, da man effizient das maximale Matching (z.B. mittels Edmonds-Karp) in polynomieller Zeit berechnen kann.
Also selbst für die minimale Knotenüberdeckung benutzt man die maximale Matching Algorithmen. ─ el_stefano 25.03.2021 um 12:31