Számítástudomány epizód tartalma:
Gyorsan és szuper-érthetően megtudhatsz mindent a páros gráfokról, párosításokról, a páros gráf pontosztályait fedő párosításokról és még sok minden másról...
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.