Diszkrét matematika Graf 2 250321 gráfelmélet, Havel-Hakimi algoritmus скачать в хорошем качестве

Diszkrét matematika Graf 2 250321 gráfelmélet, Havel-Hakimi algoritmus

Ez a videó a Diszkrét matematika 2. kurzus 2025. március 21-i levelező tagozatos előadásának második része, amelyet a Csoda81 csatorna tett közzé. Az előadás a gráfelmélet több fontos témakörét járja körül, algoritmusokkal és gyakorlati példákkal illusztrálva. Főbb témakörök és fejezetek: 1. Havel-Hakimi algoritmus [01:12] Ez az algoritmus segít eldönteni, hogy egy adott fogszámú számsorozatból felépíthető-e egy egyszerű gráf (hurokél és többszörös él nélküli). Az algoritmus lényege a fogszámok csökkenő sorrendbe állítása, majd a legnagyobb fogszámú csúcs igényének kielégítése a többi csúcs fogszámának csökkentésével. Példa egy megvalósítható gráfra (fogszámok: 6, 5, 5, 4, 3, 2, 2, 1) [02:03] és egy ellenpélda, ahol az algoritmus ellentmondásra jut, így a gráf nem létezik [12:40]. 2. Euler-körök és Euler-utak [17:14] Euler-kör: Olyan kör, amely a gráf összes élét pontosan egyszer tartalmazza. Feltétele: a gráf összefüggő és minden csúcs foka páros [19:59]. Euler-út: Olyan út, amely minden élet egyszer érint, de nem feltétlenül ér vissza a kezdőpontba. Feltétele: pontosan nulla vagy kettő páratlan fokú csúcs van [34:56]. Az előadó bemutat egy algoritmust az Euler-körök keresésére, amely kis körök egy nagy körre való "felfűzésén" alapul [26:23]. 3. Hamilton-körök és Hamilton-utak [38:01] A Hamilton-kör a gráf minden csúcsát pontosan egyszer érinti. Ez egy NP-teljes probléma, ami azt jelenti, hogy nincs rá ismert általános "gyors" (polinomidőben futó) algoritmus [39:47]. Az előadás tárgyalja az elvágópont-rendszerek szerepét: ha bizonyos csúcsok elhagyásával a gráf több komponensre esik szét, mint ahány csúcsot elhagytunk, akkor a gráfban biztosan nincs Hamilton-kör vagy -út [47:25]. Említésre kerül a Dirac-tétel, amely elegendő feltételt ad a Hamilton-kör létezésére a csúcsfokszámok alapján [54:20]. 4. Gráfok tárolása: Mátrixreprezentációk [55:43] Szomszédsági (Adjacencia) mátrix: Az n×n-es mátrix azt tárolja, mely csúcsok között van él. Irányítatlan gráf esetén szimmetrikus [58:42]. Mátrixhatványozás tétele: Egy fontos tétel szerint a szomszédsági mátrix k-adik hatványának i,j eleme megadja az i és j csúcs közötti pontosan k hosszúságú utak számát [01:13:45]. Illeszkedési (Incidencia) mátrix: Itt a sorok a csúcsokat, az oszlopok pedig az éleket reprezentálják [01:27:30]. A videó végén az előadó 10 perc szünetet rendel el az ötödik fejezet előtt [01:34:20].