SzámÃtástudomány alapjai 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.
SzámÃtástudomány alapjai epizód.