Napsal uživatel Tomáš Feltl dne 2. Leden 2026 - 8:00.
STUDIJNÍ TEXT (Teorie)
Graf v informatice není „koláčový diagram“ či sloupcový nebo bodový graf, jak ho známe z MS Excelu. V matematice a informatice je graf abstraktní struktura, která modeluje vztahy mezi objekty. Formálně zapisujeme graf jako uspořádanou dvojici:
G = (V, E)
kde V je množina vrcholů/uzlů (Vertices/Nodes) a E je množina hran (Edges).
1. Typologie grafů
| Typ grafu | Vizuál / Značení | Popis | Příklad z praxe |
|---|---|---|---|
| Neorientovaný | Čára bez šipky | Vztah je symetrický. Pokud jsou spojeni A a B, platí to oboustranně. | Přátelství na Facebooku, chemická vazba, silnice II. třídy. |
| Orientovaný (Digraf) | Šipka → | Vztah má směr. Záleží na tom, odkud kam jdeme. | Follow na Instagramu, jednosměrka, odkaz na webu, potravní řetězec. |
| Vážený (Weighted) | Číslo u hrany | Hraně je přiřazena hodnota (cena, vzdálenost, kapacita). | Mapa (km), počítačová síť (šířka pásma), potrubí (průtok). |
| Strom (Tree) | Rozvětvená struktura | Souvislý graf bez cyklů. Má kořen (root) a listy (leaves). | Souborový systém (složky), HTML stránka (DOM), fylogenetický strom, turnajový pavouk. |
| Cyklus | Uzavřená smyčka | Cesta, která začíná a končí ve stejném vrcholu. | Krebsův cyklus, autobusová linka okružní jízdy. |
| Bipartitní graf | Dvě sady vrcholů | Vrcholy lze rozdělit na dvě množiny, hrany vedou jen mezi nimi, ne uvnitř nich. | Přiřazování: Studenti ↔ Témata projektů. Herci ↔ Filmy. |
2. Jak graf vidí počítač? (Matice sousednosti)
Počítač nevidí kolečka spojená čarami. Potřebuje takový typ dat převést na čísla. Nejčastěji používáme tzv. matici sousednosti (Adjacency Matrix). Je to čtvercová tabulka N × N, kde řádky i sloupce představují vrcholy.
Pravidla pro tvorbu:
- Očísluj si vrcholy (nody) 1, 2, ..., n.
- Vytvoř tabulku n × n.
- Políčko na řádku i a sloupci j označujeme A(i,j).
- 1 (nebo váha hrany) = Hrana z i do j existuje.
- 0 (nebo ∞) = Hrana neexistuje.
Příklad:
Máme orientovaný graf: 1 → 2, 2 → 3, 3 → 1 (cyklus) a 2 → 1 (cesta zpět).
- Všimni si: Řádek 1 má jedničku ve sloupci 2 (cesta 1→2).
- Symetrie: U neorientovaných grafů je matice symetrická podle hlavní diagonály (Aij = Aji). U orientovaných (jako zde) symetrická být nemusí!
