Diszkrét matematika 210306c Hamilton-körök, kockagráfok, Gray-kódok скачать в хорошем качестве

Diszkrét matematika 210306c Hamilton-körök, kockagráfok, Gray-kódok

Ez a videó a Diszkrét matematika tantárgy levelező kurzusának előadása, amely a Hamilton-körökkel és utakkal, valamint a kockagráfokkal foglalkozik. Főbb témakörök: Hamilton-körök és utak definíciója: A Hamilton-kör a gráf összes csúcsán pontosan egyszer halad át [00:52]. Az előadó kiemeli, hogy ezt gyakran összekeverik az Euler-körökkel (amik az éleken mennek végig). NP-teljesség: A Hamilton-kör létezésének eldöntése egy tetszőleges gráfban egy NP-teljes probléma [01:43]. Ez azt jelenti, hogy jelenleg nem ismerünk rá "gyors" (polinomidőben futó) algoritmust, és ha találnánk ilyet, azzal a világ összes hasonló problémáját is gyorsan meg tudnánk oldani [04:32]. Algoritmusok: Bár létezik megoldás (pl. az összes permutáció végigpróbálása, azaz a "brute force"), ez rendkívül lassú: már egy 50 csúcsú gráfnál is évmilliárdokig tarthat a futtatása [11:44]. Negatív tételek (Mikor nincs Hamilton-kör?): * Elvágó pontrendszer: Ha a gráfból k darab csúcsot elhagyva az legalább k+1 komponensre esik szét, akkor nincs benne Hamilton-kör [15:33]. Erősen elvágó pontrendszer: Ha k pont elhagyásával legalább k+2 komponens keletkezik, akkor Hamilton-út sincs [23:16]. Pozitív tételek (Mikor van Hamilton-kör?): Dirac-tétel: Egyszerű gráfban, ha minden csúcs fokszáma legalább n/2, akkor van Hamilton-kör [27:03]. Ore-tétel: Ha bármely két nem szomszédos csúcs fokszámának összege legalább n, van Hamilton-kör [30:27]. Pósa Lajos tétele: A kisfokú csúcsok számát korlátozza a Hamilton-kör létezéséhez [32:09]. Kockagráfok (Hypercubes) és Gray-kódok: Az n-dimenziós kockagráfok felépítése rekurzív módon történik [41:47]. Minden kockagráfban létezik Hamilton-kör [46:07]. A kockagráf Hamilton-köre mentén haladva a csúcsok címkéi (0-1 sorozatok) mindig csak egyetlen helyiértéken változnak meg – ezt nevezzük Gray-kódnak [49:15]. Ezt többek között áramkörök minimalizálására (Karnaugh-tábla) használják [50:35]. A videó végén az előadó megemlíti, hogy a következő alkalommal a gráfelmélet további részeivel és a számelmélettel folytatják [51:34].