Partnervermittlungen versuchen aus ihrem Portfolio so viele Paare wie möglich zu bilden, damit ihre Provisionen maximal werden.
Es sind zwar die gegenseitigen Sympathien bekannt, doch mit welchem Verfahren können maximal viele Paare ermittelt werden?

Das Problem kann als Graph dargestellt werden: Links sind alle Damen und rechts alle Herren als Knoten, sowie die bestehenden Sympathien als Kanten (Verbindungslinien) dargestellt.
Werden zusätzlich eine Quelle (Q) und eine Senke (S) ergänzt, kann man die Frage nach dem maximalen Fluss von der Quelle zur Senke stellen. Dabei hat jede Verbindung die gleiche Kapazität, nämlich 1. D.h. jeder Partner hat genau eine Partnerin und umgekehrt.
Je mehr von der Quelle zur Senke geleitet werden kann, desto grösser sind die Provisionen.

Vorgehen

1. Phase: Man definiert Partnerschaften von der Quelle zur Senke über eine Partnerin und einen passenden Partner. Wenn auf direktem Weg keine weiteren Partnerschaften mehr möglich sind, geht man zu Phase 2 über.

2. Phase: Man weist einer freien Partnerin einen zwar sympathischen aber bereits besetzten Partner zu und folgt dann dessen bisherigen Partnerschaft zurück (Grün zu Rot). Für diese Partnerin versucht man einen anderen passenden, freien Partner zu finden. Allensfalls muss erneut ein besetzter Partner zugewiesen und die bestehende Partnerschaften zurück verfolgt werden. Stösst man dabei auf einen freien Partner, so wird dieser mit der Senke verbunden.
Damit werden die rückverfolgten Verbindungen (Rot zu Grau) aufgehoben und durch die neu gefundenen Partnerschaften (Blau zu Grün) ersetzt.

Hinweis: Verbindungen definiert man durch Klicks auf die Knoten, beginnend bei der Quelle und hin zur Senke. Den aktuellen Pfad kann man abbrechen, indem man erneut auf die Quelle klickt.

Dieses Vorgehen ist den Algorithmen zu optimalen Flüssen verwandt und auch unter dem Thema "Partnerschaftsvermittlung" bekannt. Im Jahr der Informatik war dieses Verfahren Algorithmus der Woche: zum Online Artikel.