Informatik: Matching-Algorithmen
Released by matroid on Mi. 14. März 2007 19:53:52 [Statistics]
Written by Plex_Inphinity - 13050 x read [Outline] Printable version Printer-friendly version -  Choose language   
Informatik

\(\begingroup\)
Logo 'Heiße AlgoRhythmen'

Matching-Algorithmen


Das Oberhaupt einer Familie möchte seine n Töchter verheiraten. Als Ehemänner kommen für ihn nur die m Jungen aus bestem Hause in Frage. Da das Familienoberhaupt kein Unmensch sein will, darf jede Tochter ihm eine Liste derjenigen Jungen geben, mit denen sie auf gar keinen Fall verheiratet werden will. Das Familienoberhaupt möchte so viele Töchter wie möglich unter die Haube bringen, muß dabei jedoch auch die Wünsche der Töchter berücksichtigen. Es steht somit vor einem sogenannten Matchingproblem.


Inhalt



Matchingprobleme


Ein Matchingproblem liegt immer dann vor, wenn man irgendwelche Dinge irgendwelchen anderen Dingen in eindeutiger Weise zuordnen möchte und nur bestimmte Zuordnungen erlaubt sind.
Die erlaubten Zuordnungen lassen sich am Besten mit Graphen modellieren. Die Knoten des Graphen entsprechen dann den Dingen und die Kanten zwischen den Knoten geben die erlaubten Zuordnungen wieder. Ein Graph, der das in der Einleitung angesprochene Problem modellieren würde, sähe dann zum Beispiel so aus:

Beispiel:


Die 5 Mädchen
A:={1,2,3,4,5}
sollen mit den 5 Jungen
B:={a,b,c,d,e}
gepaart werden.

1 darf höchstens mit a oder b verheiratet werden.
2 darf höchstens mit a verheiratet werden
usw...
Bild



Eine Paarung von irgendwelchen Knoten des Graphen nennt man in der Graphentheorie ein Matching des Graphen. Es ist durch die Angabe der Kanten zwischen den gematchten Knoten eindeutig bestimmt.

Definition(Matching):


fed-Code einblenden
Ein paar

Beispiele:




Die blau markierten Kanten sind jeweils Matchings.
Links sieht man ein inklusionsmaximales Matching M={{1,a},{3,c},{5,d}}.
In der Mitte sieht man ein Maximum-Matching M={{1,b},{2,a},{3,d},{4,c}}
Dies wäre also eine Lösung für das ein der Einleitung aufgeworfene Problem.
Leider geht der ungeliebte Junge e immer leer aus :-(.
Rechts ein perfektes Matching eines nicht-bipartiten Graphen M={(1,3),(2,5),(4,6)}

Man sieht insbesondere, dass ein inklusionsmaximales Matching nicht unbedingt auch eine Maximum Matching sein muß. Umgekehrt überlegt man sich aber leicht, dass jedes perfekte Matching ein Maximum Matching und jedes Maximum Matching auch inklusionsmaximal ist.

Im folgenden wollen wir uns einen Algorihmus für das Maximum Matching-Problem für (bipartite) Graphen überlegen.

Ein Greedy-Algorithmus für inklusionsmaximale Matchings


Ein inklusionsmaximales Matching eines Graphen zu finden ist viel einfacher, als ein Maximum Matching. Der folgende Algorithmus tut das.
Pseudocode GreedyMatching
  1. M:=leere Menge
  2. If (E ist leer) output M end
  3. Wähle eine Kante k aus E
  4. Füge k zu M hinzu
  5. Entferne k und alle mit k inzidierenden Kanten aus E
  6. goto 002
Wenn auch intuitiv klar ist, dass der Algorithmus immer ein inklusionsmaximales Matching liefert, wollen wir das hier mal spaßeshalber genauer beweisen. Idealerweise sollte man das immer tun .
Ein Korrektheitsbeweis besteht aus zwei Teilaussagen, die bewiesen werden müssen.
1. Der Algorithmus terminiert.
2. Wenn der Algorithmus terminiert, dann liefert er das richtige Ergebnis.

zu 1.
In jedem Durchlauf der goto-Schleife wird immer mindestens ein Element aus E entfernt, nämlich die Kante k. Somit wird |E| in jeder Iteration um mindestens eins kleiner. Nach höchstens |E| Schleifendurchläufen muß also |E|=0 sein, womit E leer ist und der Algorithmus nach der If-Abfrage in Zeile 002 terminiert.

zu 2.
i. Der Algorithmus gibt ein Matching M aus.

Dazu muß man sich eine geeignete Schleifeninvariante überlegen.
Vor und nach jeder Iteration gilt immer:

(I) M ist ein Matching und enthält keine Kanten, die mit einer Kante aus E inzidieren.

Dass dies eine Schleifeninvariante ist, zeigt man nun quasi induktiv.
Am Anfang, also in Zeile 001 und 002 gilt (I), da die leere Menge per Definition auch ein Matching ist und natürlich keine mit E inzidenten Kanten enthält.
Angenommen (I) gilt vor einer Iteration, also in Zeile 002.
Dann wird in 004 eine Kante zu M hinzugefügt, die laut Voraussetzung mit keiner Kante aus M inzidiert, womit M ein Matching bleibt und in 005 werden alle mit k inzidierenden Kanten aus E entfernt, womit (I) auch nach der Iteration erhalten bleibt.

ii. M ist inklusionsmaximal.

Angenommen nicht, dann gäbe es eine Kante k, die man noch zu M hinzufügen könnte, so dass M ein Matching bleibt. Dann hätte der Algorithmus aber nicht terminiert, da k mit keiner Kante aus M inzidiert und somit niemals aus E entfernt werden würde, d.h. die Bedingung (E ist leer) aus der If-Verzweigung wäre niemals erfüllt worden.

M-verbessernde Pfade


Angenommen wir haben schon irgendein Matching unseres Graphen berechnet, etwa mit dem Greedy-Algorithmus. Was wir nun bräuchten, wäre eine einfache Methode, um dieses Matching schrittweise zu einem Maximum Matching aufzupeppen. Den Schlüssel dazu bilden die sogenannten M-verbessernden Pfade.

Definition(M-freie Knoten)


fed-Code einblenden

Definition(M-verbessernde Pfade)


fed-Code einblenden
Aus einem M-verbessernden Pfad kann man leicht ein Matching konstruieren, das eine Kante mehr enthält als M, indem man einfach alle Kanten auf dem Pfad "invertiert".

Lemma:


fed-Code einblenden
Beweis durch Beispielbild :
Bild
Der Pfad P=0,1,2,3,4,5 im oberen Graphen ist M-verbessernd, da immer abwechselnd Matching- und Nicht-Matchingkanten durchlaufen werden und die beiden Endpunkte 0 und 5 mit keiner Matchingkante inzidieren. Im unteren Graphen wurde dieser Pfad invertiert, wodurch man ein Matching erhält, das genau eine Kante mehr hat.




Das Grundgerüst unseres Algorithmus liegt damit schonmal fest:
Pseudocode MaximumMatching
  1. M:=leere Menge
  2. while(G enthält einen M-verbessernden Pfad) do
  3. Suche einen M-verbessernden Pfad P
  4. M:=P+M
  5. endwhile
  6. print M
  7. end
Die Frage ist jetzt nur, ob der Algorithmus korrekt ist und wie man die Suche nach M-verbessernden Pfaden genau realisiert. Widmen wir uns erstmal der Korrektheit des Algorithmus.

Wie beim Greedy-Algorithmus sieht man, dass der Algorithmus irgendwann terminieren muß. Denn jedesmal, wenn Zeile 004 ausgeführt wird, wird das Matching M um eine Kante vergrößert. Ein Matching kann maximal |V|/2 Kanten haben, also terminiert der Algorithmus nach höchstens |V|/2 Iterationen der while-Schleife.

Dass das vom Algorithmus berechnete Matching auch tatsächlich ein Maximum Matching ist, folgt aus dem folgenden Satz von Claude Berge (1926-2002).

Satz von Berge


fed-Code einblenden

Dank Monsieur Berge können wir uns also sicher sein, dass der obige Algorithmus 'MaximumMatching' korrekt ist und für beliebige Graphen funktioniert. Bleibt noch die Frage, wie wir auf systematische Weise M-verbessernde Pfade in einem Graphen aufspüren und invertieren können. Dabei hilft die 'Tiefensuche'.

Tiefensuche


Tiefensuche, auch Depth-First-Search (DFS) genannt, ist eine der beiden Standard-Suchmethoden für Graphen. Die andere ist die Breitensuche (BFS).
Im Grunde sind DFS und BFS zunächst mal nur Algorithmen, die bei irgendeinem Knoten v des Graphen anfangen und sich von da aus an den Kanten des Graphen zu jedem anderen von v aus erreichbaren Knoten entlanghangeln.

Für eine vollständige Traversierung des Graphen braucht man 2 Prozeduren:

explore(vertex v) wird aufgerufen, wenn der Knoten v das erste mal entdeckt wird und ruft rekursiv explore(w) für alle noch unbesuchten Nachbarn w auf.
Dabei merken wir uns die Knoten v, die schonmal besucht wurden, indem wir sie mittels der booleschen Variable v.visited als besucht markieren.
So wird vermieden, dass wir unnötigerweise andauernd im Kreis laufen.
Da explore(v) jedoch nur die Zusammenhangskomponente in der v liegt durchsucht, brauchen wir noch eine Oberprozedur DFS(Graph g), die den ganzen Graphen überblicken kann und explore(v) für jede Zusammenhangskomponente einmal aufruft.
Pseudocode DFS
  1. procedure explore(vertex v)
  2. begin
  3. /* Tu hier irgendwas mit v */
  4. for all (v,u) in E do
  5. if(u.visited=false) then
  6. u.visited=true
  7. explore(u)
  8. endif
  9. endfor
  10. end
  11.  
  12. procedure DFS(Graph G)
  13. begin
  14. for all v in V do
  15. if(v.visited=false) then
  16. explore(v)
  17. endif
  18. endfor
  19. end

Ein Wort noch zur Zeitkomplexität der Tiefensuche. Wieviele Berechnungsschritte wird eine Tiefensuche in etwa machen?
Dabei interessiert uns nicht die genaue Anzahl der Schritte, da wir diese aus dem Pseudocode ohnehin nicht rauslesen können, sondern nur die sogenannte asymptotische Laufzeit. Diese mißt man bei Graphenalgorithmen üblicherweise als Funktion der Größen |V| und |E|.

Die Prozedur DFS(Graph G) führt in einer Schleife |V| mal gewisse Operationen aus (der if-test in Zeile 002, die Auswahl der Ecke v aus V, die Inkrementierung etwaiger Schleifenzähler, Stackverwaltung für den Funktionsaufruf in Zeile 005 etc.) deren Laufzeit jedoch unabhängig von den Größen |V| und |E| immer gleich, also konstant ist.
Die Ausführung von explore(v) nicht mitgerechnet, hat sie also eine Laufzeit, die proportional zu |V| ist, was man auch mit der Landauschen O-Notation O(|V|) ausdrückt.

Die Laufzeit der Prozedur explore(v) hängt von der Anzahl der Kanten, die mit v inzidieren ab. Insgesamt wird bei einem Aufruf von explore(v) jede Kante aus der Zusammenhangskomponente von v genau zweimal betrachtet (einmal von vorne und einmal von hinten), so dass ein Aufruf von DFS zusammengenommen eine Laufzeit von O(|V|+|E|) hat.

M-alternierende Tiefensuche


Wir wollen die Tiefensuche nun so modifizieren, dass sie zum Auffinden und anschließenden Invertieren von M-verbessernden Pfaden taugt.
Die hier verwendete Technik besteht darin, explore(v) auf einem freien Knoten v des Graphen aufzurufen, und dann immer direkt zwei Schritte auf einmal zu nehmen. Zuerst über eine ungematchte Kante {v,u} zu einem Knoten u und dann von u aus über die, falls vorhanden, eindeutige Matchingkante {u,w} zu einem Knoten w, von wo aus die Suche rekursiv fortgesetzt wird.
Kommen wir so irgendwann mal zu einem freien u, dann haben wir einen M-verbessernden Weg gefunden.
Wir brechen dann die Suche ab und machen uns auf den Rückweg, wobei wir quasi im Vorbeigehen die Kanten, die wir dabei überqueren invertieren.
v.match speichert dabei jeweils den mit v gematchten Knoten bzw. NULL, falls v frei ist.
Pseudocode invertPath(vertex v)
  1. // Gibt true zurück, falls es von v aus einen M-verbessernden Pfad gibt
  2. // und invertiert diesen dann.
  3. bool invertPath(vertex v)
  4. begin
  5. for all (v,u) in E do
  6. if(u.visited=false)
  7. u.visited=true
  8. if(u.match=NULL or invertPath(u.match)) //ist u frei oder führt zu eine
  9. u.match=v //freien Knoten? Dann Kante invertieren
  10. return true //und Suche abbrechen.
  11. endif //Sonst nächste Kante angucken
  12. endif
  13. endfor
  14. return false //Alle Kanten erfolglos ausprobiert
  15. end
Für den vollständigen Algorithmus fehlt nun nur noch eine Oberprozedur, die invertPath solange auf freien Knoten aufruft, bis es keine M-verbessernden Pfade mehr gibt. Dafür reicht es, wie wir unten beweisen werden, invertPath einmal auf jeden Knoten einer Partition (am Besten der kleineren) aufzurufen.
Pseudocode MaxBipMatching
  1. MaxBipMatching(BipartiteGraph g)
  2. begin
  3. vertex_list L := g.getPartition()
  4. for all v in L do
  5. unmark(g) //Entfernt wieder alle Knotenmarkierungen
  6. invertPath(v)
  7. endfor
  8. end

Beispiel:


Bild

Aufruf von invertPath(1).
Rot ist immer der gerade besuchte Knoten.
Lila sind alle Knoten, die schonmal besucht wurden.
Ab der unteren Zeile wird der gefundene M-verbessernde Pfad 1c5a2b invertiert. Man beachte, wie der Algorithmus vorher in die Sackgasse 1c5d3 läuft.

Laufzeit


Die for-Schleife in MaxBipMatching macht |L|, also nicht mehr als |V| Iterationen.
Wie bei der Tiefensuche erkennt man, dass invertPath(v) eine Laufzeit von O(|E|) hat.
Insgesamt hat MaxBipMatching somit eine Laufzeit von O(|V|*|E|), was ganz gut ist :-).

Wozu die Einschränkung auf bipartite Graphen?


Das folgende Beispiel zeigt, dass der Algorithmus für Graphen, die nicht bipartit sind, im Allgemeinen nicht funktioniert. Weder mit Tiefen- noch mit Breitensuche.
Bild


Der Algo läuft in eine Sackgasse und findet den M-verbessernden Weg 1246 nicht.
Natürlich hätte er ihn gefunden, wenn er von 1 zuerst zu 2 gegangen wäre, statt zu 3. Bloß woher soll er das wissen?

Warum klappts auf bipartite Graphen?


Auf bipartiten Graphen klappt es aber. Um dies einzusehen, stellen wir uns vor, dass der Graph eine Orientierung bekommt. Alle Matchingkanten werden von Partition B nach Partition A verlaufend orientiert und alle anderen Kanten andersrum.
Ist nun v ein freier Knoten aus Partition A, so sind die M-alternierenden Pfade, die bei v starten, genau die orientierten Pfade, die bei v starten.
Ein M-verbessernder Pfad von v aus ist ein M-alternierender Pfad, der zu einem freien Knoten w aus B führt, also ein orientierter Pfad von v nach w.
Da die Tiefensuche auf orientierten Graphen alle von v aus erreichbaren Knoten findet, findet sie also auch w und zwar über einen orientierten Pfad, also einen M-alternierenden Pfad.

Zudem reicht es invertPath(v) auf jedem Knoten v aus A (bzw. B) einmal aufzurufen.
Sollte ein Aufruf von invertPath(v) nämlich dazu führen, dass v gematcht wird, dann wird v auch später noch gematcht sein. Denn durch das Invertieren von M-verbessernden Pfaden ändert sich nichts daran.
Sollte v nach dem Aufruf von invertPath(v) noch ungematcht sein, wurde also kein M-verbessernder Pfad von v aus gefunden, so wird es auch später keinen M-verbessernden Weg von v aus geben. Denn angenommen doch, dann hätte davor ein M-verbessernder Pfad invertiert werden müssen, der über eine von v aus erreichbare Matchingkante k zu einem freien Knoten w führt. Wäre das nämlich nicht so, hätte sich ja gar nichts an den von v aus erreichbaren Kanten und Knoten geändert, womit invertPath(v) genauso ablaufen würde, wie vorher.
Dann hätte invertPath(v) aber w auch schon gefunden, da k ja von v aus erreichbar ist und w von k aus erreichbar ist.

Eine Implementierung in C


Nachdem oben die Theorie entwickelt wurde, will ich hier mal zur Praxis übergehen und eine Implementierung in der Programmiersprache C wagen.

Zunächst mal überlegen wir uns mit welcher Datenstruktur wir Graphen repräsentieren wollen.
Ein Graph besteht aus Knoten (tVertex). Jeder Knoten enthält eine Liste mit Zeigern auf seine Nachbarknoten, also eine Kantenliste (tEdgeList).
Eine Kante ist ein Zeiger auf einen Knoten (tEdge).
Ein bipartiter Graph (tBipGraph) besteht insbesondere aus zwei Partitionen (partA, partB), welche Arrays von Knoten sind.
C Graphenstruktur
typedef struct _tVertex *tEdge;        
typedef struct _EdgeList *tpEdgeList;
typedef struct _BipGraph *tpBipGraph;
 
//Kantenliste
typedef struct _EdgeList
{
  tEdge vertex;
  tpEdgeList next;
} tEdgeList; 
 
typedef struct _tVertex
{
  tpEdgeList neighbors; 
  tEdge match;
  bool visited;
  int number;
} tVertex;
 
typedef struct _BipGraph
{
  tVertex * partA; 
  tVertex * partB;
  int sizeA;
  int sizeB;
} tBipGraph;

Damit können wir den Pseudocode fast eins zu eins übernehmen.
C invertPath
bool invertPath(tVertex * v)
{
  tpEdgeList edges;
  tEdge u;
 
  edges=v->neighbors;                              //kantenliste holen
  while(edges!=NULL) {                             //bis zum Ende durchlaufen
    u=edges->vertex;                              
    if(!u->visited) {
      u->visited=true;
      if(u->match==NULL || invertPath(u->match)) { //u frei oder
        u->match=v;                                //zu freiem Knoten führend?
        return true;                               //dann abbrechen
      }
    }
    edges=edges->next;                             //sonst nächste Kante probieren
  }
  return false;                                    //von v aus scnon alles erfolglos
}                                                  //abgegrast
Man beachte, dass C den ||-Operator lazy evaluiert. Das heißt, wenn u->match sowieso schon NULL ist, wird improvePath(u->match) garnicht erst aufgerufen. Somit
ist sichergestellt, dass wir uns keine NULL-Pointer-Exception einfangen.
C maxMatching
void maxMatching(tpBipGraph g)
{
  tVertex * part;
  int size;
 
  size=g->sizeA;             //größe von Partition A holen
  part=g->partA;             //partition A holen (sollte die kleinere sein)
  for(int i=0;i<size;i++) {  //alle Knoten der Partition durchlaufen
    unmark(g);               //alle Knotenmarkierungen wieder entfernen
    invertPath(&part[i]);    //M-verbessernden Weg von i aus suchen und invertieren
  }
}

Was noch fehlt sind ein paar Hilfsprozeduren für die Graphenverwaltung.
C Funktionen zur Graphenverwaltung
// Erweitert die Kantenliste start um eine weitere Kante newEdge 
// (Siehe dazu Gockels Artikel über Verkettete Listen)
tpEdgeList insertAtStart(tpEdgeList start,tEdge newEdge)
{
  tpEdgeList newList=(tpEdgeList)malloc(sizeof(tEdgeList));
  newList->vertex=newEdge;
  newList->next = start;
  return newList;
} 
 
// Erzeugt einen bipartiten Graphen mit sizeA+sizeB Knoten ohne Kanten 
tpBipGraph createEmptyBipGraph(int sizeA,int sizeB)
{
  tpBipGraph g;
 
  g=(tpBipGraph) malloc(sizeof(tBipGraph));           // Erstmal Speicher allozieren
  g->partA=(tVertex *) malloc(sizeof(tVertex)*sizeA);
  g->partB=(tVertex *) malloc(sizeof(tVertex)*sizeB);
 
  for(int i=0;i<sizeA;i++) {                         //  dann Knoten initialisieren
    g->partA[i].number=i;
    g->partA[i].visited=false;
    g->partA[i].match=NULL;
    g->partA[i].neighbors=NULL;
  }
  for(int i=0;i<sizeB;i++) {
    g->partB[i].number=i;
    g->partB[i].visited=false;
    g->partB[i].match=NULL;
    g->partB[i].neighbors=NULL;
  }
  g->sizeA=sizeA;
  g->sizeB=sizeB;
 
  return g;
} 
// Fügt die Kante (a,b) ein in den bipartiten Graphen g ein
void addEdge(tpBipGraph g,int a,int b)
{
  tVertex * va,*vb;
 
  va=(g->partA)+a;                                 //Zeiger auf a-ten Knoten holen
  vb=(g->partB)+b;                                 //Zeiger auf b-ten Knoten holen
  va->neighbors=insertAtStart(va->neighbors,vb);   //Kante von a nach b einfügen
  vb->neighbors=insertAtStart(vb->neighbors,va);   //Kante von b nach a einfügen
}
// Erzeugt einen bipartiten Graphen mit sizeA+sizeB Knoten und numEdges Kanten 
// zwischen den Knoten mit den im Array edges übergebenen Knotennummern 
tpBipGraph createBipGraph(int sizeA, int sizeB, int numEdges, int * edges)
{
  tpBipGraph g=createEmptyBipGraph(sizeA,sizeB);   //leeren Graph bauen
 
  for(int i=0;i<2*numEdges;i +=2) {                 //Im zweierschritt kanten einfügen
    addEdge(g,edges[i],edges[i+1]);
  }
  return g;
}
 
// Zum experimentieren :-). 
// Erzeugt einen Zufallsgraphen mit sizeA+sizeB Knoten 
// und Kantenwahrscheinlichkeit ca. 1/p 
tpBipGraph createRandomBipGraph(int sizeA, int sizeB,int p)
{
  tpBipGraph g=createEmptyBipGraph(sizeA,sizeB); //leeren Graph bauen
 
  srand(time(NULL));                             //Zufall säen
  for(int i=0;i<sizeA;i++) {                     //Für jedes Knotenpaar eine Zahl  
    for(int j=0;j<sizeB;j++) {                   //ziehen
      if(rand()%p==0) {                          //Zahl durch p teilbar?
        addEdge(g,i,j);                          //dann Kante rein
      }
    }
  }
  return g;
}
 
// Entfernt die Markierungen aller Knoten
void unmark(tpBipGraph g)
{
  for(int i=0;i<g->sizeA;i++) {
    g->partA[i].visited=false;
  }
  for(int i=0;i<g->sizeB;i++) {
    g->partB[i].visited=false;
  }
}
 
// Gibt den Graphen auf der Konsole aus. 
void printGraph(tpBipGraph g)
{
  int size;
  tpEdgeList edges;
 
  size=g->sizeA;
  printf("Graph:\n");                            //Damit man weiß, was es ist.
  for(int i=0;i<size;i++) {                      //Knoten aus A-Partition durchlaufen
    edges=g->partA[i].neighbors;                 
    while(edges!=NULL) {                         //und die Liste der Nachbarn
      printf("%d-%d\n",i,edges->vertex->number); //ausgeben
      edges=edges->next;
    }
  }
}
 
// Gibt die Matchingkanten aus. 
void printMatching(tpBipGraph g)
{
  int size,matchsize=0;
 
  tVertex * vertices;
  printf("Matching:\n");
  size=g->sizeB;                                     //Die B-Knoten tragen die 
  vertices=g->partB;                                 //Matching-Information
  for(int i=0;i<size;i++) {
    if(vertices[i].match!=NULL) {                    //Knoten gematcht?
      printf("%d-%d\n",vertices[i].match->number,i); //dann ausgeben mit wem
      matchsize++;
    }
  }
  printf("matchsize:%d\n",matchsize);
}

Und wie ruft man das Programm nun auf?
Ganz einfach:
Man numeriert zunächst die Knoten jeder Partition seines Graphen bei 0 beginnend durch und schreibt dann die Kanten nacheinander in ein int-Array. Beim Graphen aus dem ersten Beispiel würde man also a=0, b=1,... setzen und hätte dann folgendes Array:
int bspKanten[]={0,0 , 0,1 , 1,0 , 2,0 , 2,2 , 2,3 , 3,2 , 4,3};
Dieses übergibt man sodann der Funktion createBipGraph.
int main()
{
  tpBipGraph bspGraph;
  int bspKanten[]={0,0 , 0,1 , 1,0 , 2,0 , 2,2 , 2,3 , 3,2 , 4,3};
 
  bspGraph=createBipGraph(5,5,8,bspKanten); //Graph mit 5+5 Ecken und 8 Kanten bauen
//Oder ein Zufallsgraph mit 100+100 Ecken und Kantenwahrscheinlichkeit 1/2
//bspGraph=createRandomBipGraph(100,100,2);
  printGraph(bspGraph);                     //Zur Kontrolle mal ausgeben
  maxMatching(bspGraph);                    //Maximum Matching berechnen
  printMatching(bspGraph);                  //und ausgeben
  return 0;
}

Man kann sich den Quellcode auch als Datei aus dem Notizbuch der Algorithmen AG herunterladen:
MaxMatching.cpp
Sollte mit jedem vernünftigen C-Compiler kompilierbar sein.
Für eine gute Anleitung zur Installation eines solchen Compilers siehe den Artikel Einführung in C - Installation eines C-Compilers von Java-Guru.
Mit dem klappt es auf jedenfall (habe ich getestet).



Schlusswort


Bleibt noch zu sagen, dass dies natürlich nicht unbedingt die performanteste Implementierung sein muß. Man könnte zum Beispiel die rekusive Funktion invertPath in eine iterative Version umschreiben, was meistens schneller ist.
Mir ging es hier aber nur darum, den Algorithmus einigermaßen nachvollziehbar zu erklären.

Außerdem gibt es für das Bipartite Maximum Matching-Problem noch asymptotisch schnellere Algorithmen, wie etwa den Algorithmus von Hopcroft-Karp mit einer Laufzeit von O(|V|^1/2 * |E|). Er ist nicht viel komplizierter als der, den ich beschrieben habe, und beruht auch auf M-verbessernden Pfaden.

Ebenso ist für das Maximum Matching-Problem auf allgemeinen Graphen ein O(|V|^(1/2) * |E|)-Algorithmus bekannt.
Dazu vielleicht mehr in einem anderen Artikel.

Interessant wird es auch, wenn die Kanten noch zusätzlich gewichtet sind und man nun nicht ein Matching maximaler Kardinalität, sondern maximalen Gewichts sucht.
Dazu hat N-Man hier auf dem MP schonmal einen Artikel geschrieben:
kleine mathematische Hilfe für potentielle Schwiegermütter.

Viele Grüße,
Plex
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Informatik :: Algorithmen :: Grundstudium Informatik :: Interessierte Studenten :: Theoretische Informatik :
Matching-Algorithmen [von Plex_Inphinity]  
Ein Matching-Algorithmus für das bipartite Maximum Matching Problem wird vorgestellt.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 13050
 
Aufrufstatistik des Artikels
Insgesamt 2377 externe Seitenaufrufe zwischen 2012.01 und 2021.04 [Anzeigen]
DomainAnzahlProz
https://google.com190.8%0.8 %
https://google.ch10%0 %
https://google.de33314%14 %
https://matheplanet.com10%0 %
http://google.de140158.9%58.9 %
http://google.fr2249.4%9.4 %
http://google.pl1958.2%8.2 %
https://google.ru532.2%2.2 %
http://google.es461.9%1.9 %
http://google.it281.2%1.2 %
http://images.google.de100.4%0.4 %
https://www.bing.com90.4%0.4 %
http://de.search.yahoo.com70.3%0.3 %
https://www.ecosia.org50.2%0.2 %
http://www.bing.com220.9%0.9 %
https://duckduckgo.com40.2%0.2 %
http://google.com40.2%0.2 %
http://www.ecosia.org30.1%0.1 %
http://search.icq.com10%0 %
http://google.at10%0 %
http://search.conduit.com30.1%0.1 %
http://www.buenosearch.com10%0 %
http://172.16.0.5:191010%0 %
https://wconf7.hrz.uni-marburg.de10%0 %
http://at.search.yahoo.com10%0 %
http://suche.t-online.de10%0 %
http://r.duckduckgo.com10%0 %
http://de.yhs4.search.yahoo.com10%0 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 7 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2021.04.05-2021.04.18 (7x)https://google.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 2320 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2018 (357x)http://google.de/url?sa=t&rct=j&q=
2020-2021 (251x)https://google.de/
201306-06 (98x)http://google.fr/url?sa=t&rct=j&q=baum mit eindeutiges perfektes matching bei...
201205-05 (93x)http://google.fr/url?sa=t&rct=j&q=inklusionsmaximal
201301-01 (90x)http://google.pl/url?sa=t&rct=j&q=maximales matching algorithmus
201302-08 (86x)http://google.de/url?sa=t&rct=j&q=perfektes matching beispiel
201405-05 (85x)http://google.de/url?sa=t&rct=j&q=matching probleme
201307-07 (65x)http://google.de/url?sa=t&rct=j&q=maximales matching wie finden
201211-11 (63x)http://google.de/url?sa=t&rct=j&q=was sind matchingprobleme
201305-05 (61x)http://google.de/webhp?ix=seb&ion=1
201203-03 (59x)http://google.de/url?sa=t&rct=j&q=perfektes matching bipartit erklärt
201406-06 (55x)http://google.de/url?sa=t&rct=j&q=matchings in bipartiten graphen
201404-04 (55x)http://google.pl/url?sa=t&rct=j&q=matching maximaler kardinalität
202101-01 (54x)https://google.de/url?sa=t
202007-07 (53x)https://google.ru/
201212-12 (51x)http://google.de/url?sa=t&rct=j&q=probleme ein maximum matching zu finden
201502-02 (51x)http://google.de/url?sa=t&source=web&cd=8&ved=0CDMQFjAH
201202-02 (50x)http://google.pl/imgres?q=bipartite Hopcroft-Karp c++ array
201204-04 (49x)http://google.de/url?sa=t&rct=j&q=matchings
201207-07 (49x)http://google.de/url?sa=t&rct=j&q=vollständiger graph matching matroid
201505-05 (48x)http://google.de/url?sa=t&source=web&cd=7&ved=0CCwQFjAG
201206-06 (46x)http://google.es/url?sa=t&rct=j&q=matching algorithmus
201408-09 (41x)http://google.de/url?sa=t&rct=j&q=inklusionsmaximale menge
201311-11 (39x)http://google.de/url?sa=t&rct=j&q=matching beispiel
201210-10 (38x)http://google.de/url?sa=t&rct=j&q=profile matching algorithmus
201208-08 (38x)http://google.de/url?sa=t&rct=j&q=matching mathematik
201401-01 (35x)http://google.de/url?sa=t&rct=j&q=baum hat höchstens ein perfektes matchin...
201303-03 (33x)http://google.fr/url?sa=t&rct=j&q=perfektes matching algorithmus
201201-01 (30x)http://google.de/url?sa=t&rct=j&q=perfektes matching algorithmus
201209-09 (29x)http://google.de/url?sa=t&rct=j&q=matching-algorithmen
201501-01 (28x)http://google.it/url?sa=t&rct=j&q=
2013-2016 (28x)http://google.de/url?sa=t&rct=j&q=matching algorithmus
202009-09 (25x)https://google.de
201309-09 (22x)http://google.de/url?sa=t&rct=j&q=inklusionsmaximal
202010-10 (10x)https://google.com/
201602-06 (9x)http://images.google.de/url?sa=t&rct=j&q=
202007-12 (7x)https://www.bing.com/
201202-02 (6x)http://de.search.yahoo.com/search;_ylt=A7x9QX4exDtPuyQAxYIzCQx.?p=bipartite m...
201711-11 (6x)http://google.de/url?sa=t&rct=j&q=maximales matching greedy algorithmus O(n)
2020-2021 (5x)https://www.ecosia.org/
201404-05 (5x)http://www.bing.com/search?q=Algorithmen Matching&qs=n&form=QBLH&filt=all&pq=...
2016-2017 (5x)http://google.de/
2020-2021 (4x)https://duckduckgo.com/
201508-08 (4x)http://google.de/url?sa=t&source=web&cd=4&ved=0CD8QFjADahUKEwi-z-XG5arHAhVFsx...
201703-03 (4x)http://google.de/search?site=&source=hp&ei=dmbCWJfiKcKuUf_er-AC&q=algorithmus...

[Top of page]

"Informatik: Matching-Algorithmen" | 1 Comment
The authors of the comments are responsible for the content.

Re: Matching-Algorithmen
von: gilgamash am: Mo. 14. Mai 2007 15:44:00
\(\begingroup\)
Grüße,

habe den Artikel kurz überflogen; eine kleine Anmerkung: Informatikern dürfte grundsätzlich klar sein, was ein Greedy-Algorithmus ist und sie dürften m.E.n. auch das Beispiel (und den Aufhänger des Artikels) kennen. Da ich daher annehme, dass der Artikel nicht in erster Linie für Informatiker gedacht ist, würde ich kurz erläutern, was Greedy-Algorithmen sind und eventuell erwähnen, woher der Name kommt.

Beste Grüße,
Gilgamash
\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]