UKTG Prednáška 10. týždeň

Zhrnutie prednášky

Prednáška uvádza do teórie grafov ako disciplíny diskrétnej matematiky, ktorá nesúvisí s grafmi funkcií, a motivuje ju vetou o štyroch farbách. Graf je definovaný ako usporiadaná dvojica množiny vrcholov a množiny hrán, pričom hrany sú dvojprvkové podmnožiny vrcholov. Zavádzajú sa pojmy incidencia, susednosť, stupeň vrchola a minimálny a maximálny stupeň. Dokazuje sa, že v každom grafe je počet vrcholov nepárneho stupňa párny, pretože súčet stupňov sa rovná dvojnásobku počtu hrán. Ďalej sa vysvetľuje izomorfizmus grafov ako bijekcia vrcholov zachovávajúca hrany, ukázaná na príklade a s nutnými podmienkami. Na záver sa začínajú pojmy sled, ťah a cesta.

• - Teória grafov patrí do diskrétnej matematiky; graf tu nie je graf funkcie.
• - Veta o štyroch farbách: každú politickú mapu možno zafarbiť štyrmi farbami tak, že susedné štáty majú rôzne farby.
• - Graf G = (V, E) tvorí množina vrcholov a množina hrán, čo sú dvojprvkové podmnožiny V.
• - Stupeň vrchola je počet hrán, ktoré z neho vychádzajú; minimálny a maximálny stupeň sa značia δ(G) a Δ(G).
• - Súčet stupňov sa rovná 2|E|, preto je počet vrcholov nepárneho stupňa vždy párny.
• - Grafy sú izomorfné, ak existuje bijekcia vrcholov zachovávajúca hrany.
• - Izomorfné grafy majú rovnaký počet vrcholov a hrán, rovnaké dĺžky kružníc a rovnaké stupne vrcholov.
• - Sled, ťah a cesta sa líšia tým, či sa v nich smú opakovať vrcholy alebo hrany.

Zhrnutie pripravené s pomocou AI z prepisu videa.