Lineární algebra pro grafiky

Pro úspěšné zdolání této kapitoly je vhodné mít alespoň základní znalosti z teorie grafů. Většinu potřebných pojmů z tohoto oboru sice v následujícím textu vysvětlujeme, pokud by to však čtenáři nepostačovalo, doporučujeme prolistovat libovolnou učebnici teorie grafů, např. [MatNeš].

Graf $ G$ je množina vrcholů $ V(G)$ spolu s množinou hran $ E(G)$, tedy dvojic různých prvků z $ V(G)$, o kterých si představujeme, že je hrana spojuje. Graf může být také orientovaný, pak jsou prvky $ E(G)$ uspořádané dvojice, a dva vrcholy tedy mohou být spojeny ve směru $ i\to j$, $ j\to i$ či $ i\leftrightarrow j$, nebo nemusí být spojeny vůbec. Stupeň vrcholu je počet všech hran, které z něho vycházejí (plus těch, které vcházejí, u orientovaných grafů). Graf je souvislý, pokud lze mezi libovolnými dvěma vrcholy přejít po hranách. Pokud graf není souvislý, rozpadá se přirozeně na komponenty souvislosti (přesná definice komponenty souvislosti je ,,každý maximální souvislý podgraf''). Graf se nazývá bipartitní, pokud lze jeho vrcholy rozdělit do dvou množin (partit) tak, že žádné dva vrcholy z jedné množiny nejsou spojeny hranou. Podobně definujeme $ n$-partitní grafy (dělíme vrcholy do $ n$ skupin). Strom je souvislý graf, který neobsahuje cyklus.



Podsekce