matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Hochschulmathe
  Status Uni-Analysis
    Status Reelle Analysis
    Status UKomplx
    Status Uni-Kompl. Analysis
    Status Differentialgl.
    Status Maß/Integrat-Theorie
    Status Funktionalanalysis
    Status Transformationen
    Status UAnaSon
  Status Uni-Lin. Algebra
    Status Abbildungen
    Status ULinAGS
    Status Matrizen
    Status Determinanten
    Status Eigenwerte
    Status Skalarprodukte
    Status Moduln/Vektorraum
    Status Sonstiges
  Status Algebra+Zahlentheo.
    Status Algebra
    Status Zahlentheorie
  Status Diskrete Mathematik
    Status Diskrete Optimierung
    Status Graphentheorie
    Status Operations Research
    Status Relationen
  Status Fachdidaktik
  Status Finanz+Versicherung
    Status Uni-Finanzmathematik
    Status Uni-Versicherungsmat
  Status Logik+Mengenlehre
    Status Logik
    Status Mengenlehre
  Status Numerik
    Status Lin. Gleich.-systeme
    Status Nichtlineare Gleich.
    Status Interpol.+Approx.
    Status Integr.+Differenz.
    Status Eigenwertprobleme
    Status DGL
  Status Uni-Stochastik
    Status Kombinatorik
    Status math. Statistik
    Status Statistik (Anwend.)
    Status stoch. Analysis
    Status stoch. Prozesse
    Status Wahrscheinlichkeitstheorie
  Status Topologie+Geometrie
  Status Uni-Sonstiges

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieAlgorithmen für maximum matchi
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Graphentheorie" - Algorithmen für maximum matchi
Algorithmen für maximum matchi < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Algorithmen für maximum matchi: Anregungen
Status: (Frage) überfällig Status 
Datum: 11:39 Fr 27.11.2015
Autor: JackyJay

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





        
Bezug
Algorithmen für maximum matchi: Idee
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:21 Fr 27.11.2015
Autor: Jule2

Schau mal hier http://www.cs.au.dk/~gerth/papers/mfcs07matching.pdf


Bezug
                
Bezug
Algorithmen für maximum matchi: Rückfrage zur Idee
Status: (Frage) beantwortet Status 
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?

Bezug
                        
Bezug
Algorithmen für maximum matchi: Antwort
Status: (Antwort) fertig Status 
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!!

Bezug
                                
Bezug
Algorithmen für maximum matchi: Rückfrage
Status: (Frage) reagiert/warte auf Reaktion Status 
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?

Bezug
                                        
Bezug
Algorithmen für maximum matchi: Antwort
Status: (Antwort) fertig Status 
Datum: 10:46 Mo 30.11.2015
Autor: schachuzipus

Hallo,

> Und was genau ist ein Simplex-algo?

Der Simplexalgorithmus (oder -verfahren) ist ein Optimierungsalgorithmus:

[guckstdu]

[]https://de.wikipedia.org/wiki/Simplex-Verfahren


Gruß

schachuzipus

Bezug
                                                
Bezug
Algorithmen für maximum matchi: Dynamisch?
Status: (Mitteilung) Reaktion unnötig Status 
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?

Bezug
                                                        
Bezug
Algorithmen für maximum matchi: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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!!!

Bezug
                                                                
Bezug
Algorithmen für maximum matchi: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
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?



Bezug
                                                                        
Bezug
Algorithmen für maximum matchi: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                                                                                
Bezug
Algorithmen für maximum matchi: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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?

Bezug
                                                                                        
Bezug
Algorithmen für maximum matchi: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
Algorithmen für maximum matchi: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:20 Sa 12.12.2015
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
        
Bezug
Algorithmen für maximum matchi: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 14:08 Mo 11.01.2016
Autor: JackyJay

Ich öffne das Thema nochmal. Vielleicht hat mittlerweile jemand ja eine Idee.

Bezug
                
Bezug
Algorithmen für maximum matchi: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:20 Di 19.01.2016
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.unimatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]