párosítások

Párosítások olyan fogalom a diszkrét matematikában, amely elemek vagy csúcsok közötti kapcsolatok rendszerezett társítását írja le úgy, hogy a párképződés diszjunkt legyen. Két gyakori nézőpont létezik: halmazelméleti és grafelméleti értelem.

Halmazelméleti értelemben egy 2n elemű halmaz párosítása egy olyan felosztás, amely minden elemet 2 elemű blokkokba rendez, és a blokkok nem fedik egymást. Ha az egész halmaz fel van töltve ilyen blokkokkal, a párosítás tökéletes (vagy 1-faktor).

Grafelméleti értelemben egy gráfon egy párosítás egy olyan élek halmaza, amelyben semelyik csúcsot sem érinti több él. Ha minden csúcsot érint pontosan egy él, akkor tökéletes párosításról beszélünk. Eredményessége különösen fontos a kapcsolórendszerek modellezésében.

Kiemelten a bipartit gráfokban a párosítások gyakran modellezik feladatok és erőforrások hozzárendelését vagy kapcsolattervezési problémákat. A maximális párosítás a lehető legtöbb élt tartalmazza, a tökéletes pedig akkor van meg, ha minden csúcs érintett.

Csoportosítási és számítási szempontból a 2n elemű készlet összes párosításának száma (2n-1)!!, és egy n×n teljes bipartit gráf tökéletes párosításainak száma n!. Algoritmikusan gyakran augmentáló utakkal vagy a Hopcroft–Karp algoritmussal találják meg a maximális párosítást, amely bipartit gráfokra hatékony.

Jellemző alkalmazások: feladat- és erőforrás-hozzárendelés, munkaerő-elosztás, valamint biológiai és kémiai párosítások modellezése.

---