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
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

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
Dt. Schulen im Ausland: Mathe-Seiten: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 Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
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


Alle Foren
Status vor 13h 12m 6. Takota
UAnaRn/Satz Implizite Funktion System
Status vor 16h 08m 3. Dom_89
SDiffRech/Ableitung bilden
Status vor 23h 07m 6. Dom_89
SIntRech/Partielle Integration/Substitu
Status vor 23h 10m 3. Dom_89
SLinGS/Lösungsverhalten LGS
Status vor 2d 2. HJKweseleit
UFina/Effektiver Zinssatz
^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]