Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

maximales Matching eines bipartiten Graphen
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> maximales Matching eines bipartiten Graphen
 
Autor Nachricht
Giles2k
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 22.01.2009
Beiträge: 4

BeitragVerfasst am: 22 Jan 2009 - 01:44:08    Titel: maximales Matching eines bipartiten Graphen

Hallo!

Ich habe ein Problem, weiß aber keine Lösung. Das Problem ähnelt dem Suchen eines maximalen Matchings in einem bipartiten Graphen, so mein Ansatz.
Problem:

2 Mengen von Personen sind vorhanden.
Es geht darum, möglichst vielen Personen aus der ersten Menge eine Person aus der zweiten Menge zuzuordnen.
Dazu können alle Personen mögliche, feste Termine angeben, an denen sie Zeit haben, um die Person aus der anderen Gruppe zu treffen.

Wenn die Personen aus beiden Gruppen nur genau einen Termin angeben könnten, könnten die verschiedenen Termine, die aus der ersten Menge zusammenkommen, als linke Seite eines bipartiten Graphen modelliert werden, und die verschiedenen Termine, die aus der zweiten Menge zusammenkommen, als die rechte Seite eines bipatiten Graphen. Dann kann ein Greedy-Algorithmus ein maximales Matching im Graphen berechnen. (Eventuell erinnert/kennt jemand hier die Aufgabe dazu aus dem 26. BWInf 1. Runde mit den Preispaarungen, die vorgenommen werden sollen.)

Problem ist hier aber, dass jede Person k Termine angeben kann, zu der sie Zeit hat, um eine Person aus der anderen Menge zu treffen. Hierbei geben die Personen möglichst viele Termine an, an denen sie können, damit die wahrscheinlichkeit steigt, einer Person aus der anderen Menge zugeordnet werden zu können. Wenn eine Person eine andere zu einen der angegebenen Termine zugeordnet bekommen hat, verfallen also alle anderen Termine, die sie angegeben hatte.

Beide Mengen haben eine Kardinalität von ca. 200 Personen. Wenn jede Person dann noch ca. 3 Termine angibt, wird schnell klar, dass nicht alle Paarungskombinationen durchprobiert werden können.

Zur Frage: Kann mir jemand einen Algorithmus nennen, der ein solches maximales Matching vornimmt?
mfG und großen Dank im Vorraus, Giles2k
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 22 Jan 2009 - 01:53:28    Titel:

http://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm ?
Giles2k
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 22.01.2009
Beiträge: 4

BeitragVerfasst am: 22 Jan 2009 - 02:42:26    Titel:

vielen Dank für die schnelle Hilfe noch so spät.
Ich habe mir den Algorithmus von Hopcroft und Karp http://de.wikipedia.org/wiki/Algorithmus_von_Hopcroft_und_Karp (auf deutsch) angeschaut. Mir viel jedoch plötzlich eine andere Möglichkeit das Problem als Hochzeitspaarungsproblem zu modellieren ein.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> maximales Matching eines bipartiten Graphen
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum