Diszkrét matematika Graf 1 Gráfelmélet alapjai скачать в хорошем качестве

Diszkrét matematika Graf 1 Gráfelmélet alapjai

Ez a videó egy Diszkrét matematika előadás felvétele, amelyet 2025. március 21-én tartottak levelezős hallgatóknak. Az előadó a gráfelmélet alapfogalmait vezeti be, hangsúlyozva az algoritmikus és számítástechnikai megközelítést. Főbb témakörök és időpontok: Bevezetés és alapfogalmak [00:01]: A kurzus technikai részletei (BBB szoba, konzultációk) és a gráfelmélet jelentősége, mint objektumok közötti kapcsolatok rendszere (V csúcshalmaz és E élhalmaz). Irányított vs. Irányítatlan gráfok [07:35]: Az előadás főként az irányítatlan gráfokra fókuszál, ahol az éleknek nincs kitüntetett iránya. Gyakorlati példa: A folyón átkelés feladványa [12:10]: A farkas, a kecske és a káposzta problémájának modellezése gráffal, ahol a csúcsok a lehetséges állapotok, az élek pedig a megengedett lépések. Gráftípusok és élfajták: Hurokél és többszörös él [09:57]: Az olyan élek, amelyek önmagukba térnek vissza, vagy két csúcs között több is fut belőlük. Egyszerű gráf [01:12:51]: Olyan gráf, amelyben nincs hurokél és többszörös él. Teljes gráf (K n ​ ) [01:22:19]: Ahol minden csúcs minden más csúccsal össze van kötve. Páros (kétpólusú) gráf [01:23:41]: A csúcsok két csoportra oszthatók, és élek csak a két csoport között futnak. Részgráfok típusai [01:28:13]: Sima részgráf, feszítő részgráf (minden csúcsot tartalmaz) és feszített részgráf (adott csúcshalmaz közötti összes eredeti élet tartalmazza). Utak, körök és összefüggőség: Séta és út [01:35:03]: Élek és csúcsok sorozata; az egyszerű útban nincs ismétlődés. Komponensek és összefüggőség [01:45:29]: A gráf maximális összefüggő részei. Az előadó a „tintacsöppentős algoritmussal” [01:47:45] szemlélteti, hogyan tárhatók fel a komponensek. Fogszám és a Kézfogási tétel [01:03:33]: A csúcsok fogszámainak összege megegyezik az élek számának kétszeresével. Ebből következik, hogy a páratlan fokú csúcsok száma mindig páros. Híres gráfok [01:14:37]: A Petersen-gráf és a Kempe-gráf bemutatása, valamint az izomorfizmus [01:16:38] (szerkezeti azonosság) fogalmának érintése. A videó végén [01:19:25] az előadó technikai szünetet tart, mielőtt rátérne a Havel-Hakimi algoritmus ismertetésére.