Diszkrét matematika 210306b Kombinatorika, Gráfok скачать в хорошем качестве

Diszkrét matematika 210306b Kombinatorika, Gráfok

Ez a videó a Diszkrét matematika tantárgy levelező tagozatának előadása, melyet a Csoda81 csatorna töltött fel. Az előadás két fő témakört érint: a kombinatorika egy speciális ágát és a gráfelmélet alapjait. Íme az előadás részletes összefoglalása a fontosabb időpontokkal: 1. Extremális halmazrendszerek [00:28] A videó első fele a kombinatorikával foglalkozik, azon belül is azokkal a rendszerekkel, ahol a halmazok számát (m) kell maximalizálni bizonyos feltételek mellett. Sperner-tétel: Kimondja, hogy ha egyetlen halmaz sem tartalmazhat egy másikat (nincs "tojássárgája effektus"), akkor a halmazok maximális száma n alatt az n/2 (egészrész) [03:45]. Erdős–De Bruijn-tétel: Olyan halmazrendszerekről szól, ahol bármely két halmaz metszete legfeljebb egy elemű. Ebben az esetben a halmazok száma legfeljebb n lehet [16:15]. Geometriai kapcsolat: Megemlíti a Gallai-tételt, amely a síkbeli pontok és az általuk meghatározott egyenesek közötti kapcsolatot írja le [18:54]. 2. Partíciós problémák [20:40] A felosztások két típusát tárgyalja: Számpartíciók: Egy egész szám felbontása összegekre [21:25]. Halmazpartíciók: Egy alaphalmaz felosztása diszjunkt részhalmazokra. Itt kerül szóba a korlátos partíciók problémája és a logikai szitaformula alkalmazása [24:02]. 3. Gráfelméleti alapfogalmak [34:35] Az előadás második fele a gráfelméletbe vezeti be a hallgatókat: Alapdefiníciók: Csúcsok (vertex), élek, irányított és irányítatlan gráfok [38:42]. Fogszám és a Kézfogási tétel: A csúcsok fogszámainak összege megegyezik az élek számának kétszeresével [41:01]. Ebből következik, hogy a páratlan fokú csúcsok száma mindig páros [48:29]. Utak és körök: Megkülönbözteti az egyszerű utat (nincs csúcsismétlődés) a sima úttól [52:37]. Összefüggőség és komponensek: A "tintacsöppentős algoritmus" segítségével szemlélteti, hogyan bontható egy gráf összefüggő komponensekre [01:12:31]. 4. Euler-körök és Euler-utak [01:45:04] Az előadás egyik legfontosabb algoritmikus része: Euler-kör: Olyan kör, amely a gráf összes élén pontosan egyszer megy keresztül. Feltétele: a gráf összefüggő (az izolált csúcsoktól eltekintve) és minden csúcs fogszáma páros [01:49:50]. Euler-út: Akkor létezik, ha pontosan két páratlan fokú csúcs van (ez lesz a start és a cél), vagy minden csúcs páros [02:13:04]. Gyakorlati példák: Megemlíti a dominókat, a "rajzold meg egy vonallal" feladatokat és a királyi palota alaprajzán alapuló fejtörőt [02:06:41]. A videó egy 10 perces szünettel zárul, jelezve, hogy a következő részben bonyolultabb témák következnek [02:17:32].