Definíció: Két él függetlensége: nincs közös végpontja két nem hurokélnek. Élhalmaz függetlenesége: páronként független nem gurokélek. v(G) a maximális méretû párosítás nagysága. Teljes párosítás olyan M párosítás,a mley az összes csúcsot páróítja, azaz mérete |V(G)|/2.
Definíció: Lefogó ponthalmaz: olyan ponthalmaz, hogy minden élnek legyen ebbe tartozó végpontja. T(g) a minimális méretû lefogó ponthalmaz nagysága.
Megjegyzés: Minden G gráfra v(G)<=T(G).
Megjegyzés: Egy páratlan pontszámú kör mutatja, hogy az egyenlõség nem szükségszerû. Független élpár, független élhalmaz, párosítás, teljes párosítás, nu paraméter
Definíció: G gráfban lévõ M párosítás triviális bõvítése.
Definíció: Mohó párosítási algoritmus: Legyen az üreshalmaz egy kiinduló M párosításunk. A triviális bõvítés segítségével növeljük M-et, amíg tudjuk. A végeredmény a mohó algoritmus outputja.
Megjegyzés: Egyáltában nem biztos, hogy az output optimális. Következtetés: a triviális bõvítés túl egyszerû. Bonyolultabb bõvítési eljárást keresünk.
Definíció: G gráfban lévõ M párosításra vonatkozó javító út.
Lemma: A javító út élei esetén a párosításhoz tartozás és párosításon kívülre esés felcserélésével egy nagyobb párosításhoz jutunk.
Definíció: Egy M páros'ítás jávító út segítségével történõ javítását ``javító utas javításnak'' nevezzük.
Definíció: Javító utas párosítási algoritmus: Legyen az üreshalmaz egy kiinduló M párosításunk. A javító utas bõvítés segítségével növeljük M-et, amíg tudjuk. A végeredmény az algoritmus outputja.
két nagyon fontos kérdés merül fel:
I) Teljes-e a javító utas bõvítési eljárás, azaz ha nem tudjuk elvégezni, akkor biztos, hogy párosításunk maximális elemszámú? Azaz a fenti algoritmus helyes-e? A mohó algoritmus után nyilvánvaló, hogy ez egyáltalán nem nyilvánvaló kérdés.
II) A fenti algoritmus implicit módon tartalmazza a következõ problémát: Adott egy gráf és M párosítása. keressünk javító utatat. Hogyan oldható ez meg?
Az elsõ kérdésre a válasz: igen, a fenti algoritmus optimális páros'ításhoz vezet. Ezt a következõ tétel bizonyítja.
Tétel (C. Berge): Egy gráfban egy M párosítás akkor és csak akkor maximális, ha nincs rá vonatkozó javító út.
Bizonyítás: Tegyük fel, hogy van M-nél nagyobb méretû N párosítás. Ekkor G csúcsai és M, illetve N élei egy gráfot adnak, amelyben minden komponens út vagy kör. Ebben kell egy olyan komponensnek lenni, amely több N-beli élet tartalmaz mint M-belit. Ennek egy útnak kell lenni, amely G-ben egy M-re vonatkozó javító út.
A II-es kérdésre a válasz nem egyszerû. Matematikusok körülbelül 10 évig dolgoztak egy hatékony eljárás kitalálására. Páros gráfokban a keresés viszonylag egyszerûen megoldható. A továbbiakban a páros gráfok esetét külön megvizsgáljuk.