Скачать или смотреть 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].