Páros gráfokról már korábban is volt szó.

Most viszont csak róluk lesz szó, úgyhogy próbáljuk meg egy kis hipnózis segítségével fölidézni, miket is kéne tudnunk a páros gráfokról.

Egy G gráf páros gráf, ha csúcsainak a V(G) halmaza felbontható az A és B diszjunkt részhalmazokra úgy…

hogy A-n és B-n belül nem vezetnek élek.

Az ilyen gráfokat úgy fogjuk jelölni, hogy V(A, B, E).

Itt A és B a gráf csúcsainak két diszjunkt halmaza, E pedig a köztük vezető élek halmaza.

Egy G gráf páros gráf, ha csúcsainak a V(G) halmaza felbontható az A és B diszjunkt részhalmazokra úgy, hogy A-n és B-n belül nem vezetnek élek.

A páros gráf jelölées: V(A, B, E).

Aztán volt még itt más is…

Azt is megnéztük, hogy egy G gráf pontosan akkor páros, ha minden G-ben szereplő kör páros hosszúságú.

Egy G gráf akkor és csak akkor páros,

ha minden G-ben szereplő kör páros hosszúságú.

És végül még egy dolog…

Egy G gráfban az E(G) élhalmaznak egy M részhalmazát párosításnak nevezzük, ha M semelyik két elemének nincs közös végpontja.

Ez itt például egy párosítás.

Ez a párosítás egy A-t fedő párosítás, mert a benne szereplő élek A-nak minden csúcsát lefogják.

És egyúttal B-t fedő párosítás is.

Ha a gráfon kisebb átalakítást végzünk…

Akkor már nehezebb A-t fedő párosítást találni.

De azért van.

Ebben a gráfban viszont…

Biztosan nem létezhet B-t fedő párosítás.

Vagy B4-et párosítjuk A4-gyel…

vagy pedig B3-at.

De mindkettőt egyszerre nem lehet.

És nincsen A-t fedő párosítás sem.

Vagy A2-t fedjük le…

vagy A3-at.

Mindkettőt egyszerre nem lehet.

Olyankor, amikor a gráf egy kicsit bonyolultabb…

néha bizony nehéz eldönteni, hogy létezik-e A-t vagy B-t lefedő párosítás.

Szerencsére mindjárt jön néhány tétel, ami segít tisztázni ezeket a kínzó kérdéseket.

Nehogy egész éjjel álmatlanul forgolódjunk emiatt.