Matching (Graphentheorie)

Die Theorie um das Finden von Matchings in Graphen ist in der diskreten Mathematik ein umfangreiches Teilgebiet, das in die Graphentheorie eingeordnet wird.

Folgende Situation wird dabei betrachtet: Gegeben sei eine Menge von Dingen und zu diesen Dingen Informationen darüber, welche davon einander zugeordnet werden könnten. Ein Matching (in der Literatur manchmal auch Paarung) ist dann als eine solche Auswahl aus den möglichen Zuordnungen definiert, die kein Ding mehr als einmal zuordnet.

Die am häufigsten gestellten Fragen in dieser Situation sind dann die folgenden:

1. Wie findet man ein Matching, das eine maximale Anzahl an Dingen einander zuordnet?
   Dieses Problem ist das klassische Matchingproblem.
2. Gibt es ein Matching, das alle Dinge zuordnet? Wenn ja, wie viele?
   Solche Matchings heißen perfektes Matching. Die Anzahl der perfekten Matchings in einem Graphen ${\displaystyle G}$ wird meistens mit ${\displaystyle \Phi (G)}$ notiert.
3. Angenommen, man könnte quantifizieren „wie wichtig“ (oder „teuer“) die einzelnen Zuordnungen wären: Wie findet man dann ein Matching, das eine maximale Zahl von Dingen zuordnet und dabei ein möglichst großes (oder kleines) Gewicht hat?
   Dieses Problem heißt gewichtetes Matchingproblem. Zwischen einer Maximierungs- und einer Minimierungsaufgabe wird hier oftmals nicht unterschieden: Indem man bei allen Gewichten (Kosten) das Vorzeichen vertauscht, kann man beide Probleme ohne nennenswerten Aufwand ineinander überführen.
4. Angenommen, man hätte genau zwei Klassen von Dingen und angenommen, man wüsste, dass es ausschließlich zwischen diesen Klassen mögliche Zuordnungen gibt. Werden die Probleme 1–3 dadurch einfacher?
   Dieses Problem heißt bipartites (gewichtetes) Matchingproblem und ist ein viel diskutierter Spezialfall.
5. Kann man anderes Wissen, das man über die Struktur der möglichen Zuordnungen hat, ähnlich wie in 4 geschickt benutzen, um die Probleme 1–3 effizienter zu lösen?

Die Theorie um die Matchings untersucht möglichst effiziente Lösungsverfahren dieser Probleme, klassifiziert diese nach ihrer Laufzeit mit den Methoden der Komplexitätstheorie und stellt Beziehungen dieser Probleme zueinander und zu anderen Problemen in der Mathematik her.