Algorithmen für maximum matchi < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Algorithmen für maximum matching auf dynamischen, bipartiten Graphen |
Hallo zusammen,
wie die Überschrift schon sagt, bin ich auf der Suche nach einem Algorithmus, der auf einem Netzwerk das Maximum Matching findet.
Die Knoten des Netzwerks kann man in 2 Mengen teilen und es gibt nur Verbindungen von Knoten der Menge 1 in Menge 2 (soweit ich weiß heisst diese Eigenschaft bipartite).
Erschwerend kommt hinzu, dass das Netzwerk dynamisch ist. Das heisst in meinem Fall, dass sich die Verbindungen der Knoten verändern, je nachdem, welche Verbindungen ich davor ausgesucht habe. Habe ich also beispielsweise Knoten 1 mit Knoten 17 verbunden, so kann es sein, dass ich nichtmehr Knoten 2 mit Knoten 18 verbinden darf (obwohl das davor möglich war). Diese Dynamik folgt nach vorher definierten Regeln ab.
Damit vermute ich, dass ich im Bereich der "Dynamic Connectivity" bin.
Vielleicht bin ich auch im Bereich der "decreasing Dynamic Connectivity", da nachdem ich eine Verbindung ausgewählt habe keine neue Verbindungen hinzukommen, sondern nur gewählte verschwinden. Allerdings kann es natürlich sein, dass die gewählte Verbindung schlecht gewählt war und ich damit kein Maximum Matching erzeugen kann und somit wieder Schritte zurück gehen muss.
Was ich schon festgestellt habe ist, dass sich der Algorithmus von Hopecroft and Karp sehr dazu eignenen würde, falls das Problem nicht dynamisch wäre. Soweit ich das sehe, macht das aber bei einem veränderlichen Netzwerk keinen Sinn.
Meine Frage lautet nun: Gibt es für diesen Fall schon schlaue Algorithmen? Kann mich da jemand in die richtige Richtung schubsen?
Ich habe selber leider keine Ahnung von Grafentheorie und hoffe ihr könnt mir weiterhelfen.
Vielen vielen Dank im Voraus!
JoKoOno
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
[http://matheplanet.com/default3.html?call=viewforum.php?forum=70&ref=https%3A%2F%2F] <-- Thema: Algorithmen für maximum matching auf dynamischen, bipartiten Graphen
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:21 Fr 27.11.2015 | | Autor: | Jule2 |
Schau mal hier http://www.cs.au.dk/~gerth/papers/mfcs07matching.pdf
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:33 Fr 27.11.2015 | | Autor: | JackyJay |
Vielen Dank für die Antwort.
Allerdings bin ich davor auch schon auf dieses paper gestoßen und soweit ich das sehe gilt das Prinzip dort nur für konvexe bipartite Graphen (Wobei ich eingestehen muss, dass ich nicht genau weiss, was konvex bei Graphen bedeuten soll).
Was tue ich denn bei nicht-konvexen bipartiten Graphen?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:38 Sa 28.11.2015 | | Autor: | Jule2 |
Das kann ich dir jetzt leider auch nicht so genau sagen!
Denk mal das hat etwas mit Polyedertheorie zu tun denn man kann das ja dann auch lösen mit einem modifizierten simplex algo!!!
Hab aber noch was entdeckt schau dir mal die Ungarische Methode an allerdings wirst du wohl nicht Drum herumkommen denn Algo anzupassen!!
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 08:42 Mo 30.11.2015 | | Autor: | JackyJay |
Soweit ich das sehe, funktioniert die ungarische Methode aber nur auf nicht-dynamischen Netzwerken. Inwieweit das effektiv auf dynamischen funktionieren soll, sehe ich noch nicht.
Und was genau ist ein Simplex-algo?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:42 Mo 30.11.2015 | | Autor: | JackyJay |
Danke für die Antwort.
Aber so wie ich das sehe, funktioniert das Prinzip nur für nicht-dynamische Probleme. Oder liege ich da falsch?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:00 Di 01.12.2015 | | Autor: | Jule2 |
Ich würde sagen einen Vorgefertigten Algorithmus wirst du wohl nicht finden aber du kannst natürlich jeden Algorithmus der dir ein maximales matching berechnet so anpassen das dieser dir das auch mit deinen dynamischen Regeln berechnet!!!
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion | | Datum: | 09:57 Mi 02.12.2015 | | Autor: | JackyJay |
Hallo Jule2,
ich vermute, dass es nicht möglich ist einen "nicht-dynamischen" Algorithmus (also in meinem Fall ein algorithmus auf einem festes Netzwerk) so sinnvoll umzuwandeln, dass er auf dynamische Probleme (variables Netzwerk) angewandt werden kann. Jedenfalls habe ich das mit 2 Algorithmen versucht und beide waren dann sehr ineffektiv bzw. funktionieren nicht mehr.
Hast du das schoneinmal getan?
Bei welchem Algorithmus kann das denn funktionieren?
Hat sonst noch jemand eine Idee?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:10 Mi 02.12.2015 | | Autor: | Jule2 |
Hi,
Kannst du mir mal nen Beispiel Posten damit ich sehen kann was genau du für Regeln verwenden willst/sollst? Kann mir jetzt erstmal wenig darunter vorstellen! Und noch eine Frage ist dein Graph gewichtet??
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:29 Do 03.12.2015 | | Autor: | JackyJay |
Hallo,
ich weiss nicht was gewichtet bedeutet, aber jede Verbindungslinie ist auch einer Zahl zugeordnet und ich möchte nicht nur ein maximales matching finden, sondern auch ein Minimum über alle möglichen maximalen Matchings. Überhaupt ein maximales Matching zu finden ist erstmal wichtiger.
Ein paar Beispiele für diese Regln sind:
Wenn Knoten 1 mit Knoten 17 verbunden ist, dann darf Knoten 2-5 nicht mehr mit Knoten 18-30 verbunden sein. Wenn Knoten 2 mit Knoten 40 verbunden ist, fallen weitere Knoten weg, ... usw.
Alternativ, wenn Knoten 10 mit Knoten 11 verbunden ist, dann darf Knoten 20 nicht mehr mit Knoten 21-50 verbunden sein....
Es fallen also nach verschiedenen Regeln Verbindungslinien weg, je nachdem was ich davor ausgewählt habe.
War das verständlich?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:06 Do 03.12.2015 | | Autor: | Jule2 |
Ja das war verständlich und gewichtet bedeutet genau das was du vermutet hast nämlich das die Kanten ein Gewicht haben und das du dieses gewicht(kosten) minimieren oder maximieren willst!!
Also ich denk da heut mal darüber nach und melde mich Morgen dann nochmal!!
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Sa 12.12.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Ich öffne das Thema nochmal. Vielleicht hat mittlerweile jemand ja eine Idee.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:20 Di 19.01.2016 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
![[]](/images/popup.gif){kind=small}
https://de.wikipedia.org/wiki/Simplex-Verfahren