Matching

Ein matching in einem Graph $G$ ist eine Menge $M\subseteq E(G)$ von
Kanten, so dass $e\cap f=\mathrm{\varnothing }$ für alle $e\ne f\in M$.
(Kein Knoten ist inzident zu 2 Kanten aus $M$.)

Beispiel eines Matchings

Sei $A=\{a_1,a_2,a_3,a_4\}$ und $B=\{s_1^1,s_2^1,s_3^1,s_1^2,s_2^2\}$.
Die Kantenmenge des Graphen sei gegeben durch:

Ein perfektes Matching für die Partitionsmenge $A$ wird durch Auswahl der folgenden disjunkten Kanten gebildet:

In dieser Konfiguration ist jeder Studierende $a_i$ genau einer Kante in $M$ zugeordnet, und kein Thema wird doppelt verwendet.

Links

• DS_vollständiger_foliensatz.pdf