Rozprávaj o neorientovanom grafe a jeho vlastnostiach.

Neporovnateľný graf je pár $(V, E)$, kde $V$ je množina vrcholov (uzlov) a $E$ je množina hrán. Každá hrana predstavuje neorientovaný pár ${u, v}$ vrcholov, kde $u, v \in V$.

Hlavné vlastnosti:

• Hrany bez smeru: Väzba medzi vrcholmi je symetrická. Ak existuje hrana medzi $u$ a $v$, znamená to, že sa môžete pohybovať ako z $u$ do $v$, tak aj z $v$ do $u$.
• Stupeň vrcholu: Počet hrán incidentných na daný vrchol. Označuje sa ako $deg(v)$.
• Súčet stupňov všetkých vrcholov: V akomkoľvek neorientovanom grafe je súčet stupňov všetkých vrcholov rovný dvojnásobku počtu hrán. $\sum_{v \in V} deg(v) = 2|E|$.
• Cesta: Sekvencia vrcholov $v_0, v_1, ..., v_k$, kde každá dvojica $(v_i, v_{i+1})$ je hrana.
• Cykel: Cesta, ktorá začína a končí v tom istom vrchole, pričom všetky ostatné vrcholy sú jedinečné.
• Spojitosť: Graf sa nazýva spojitý, ak existuje cesta medzi akoukoľvek dvojicou vrcholov. Nespájajúci graf sa skladá z viacerých spojitých komponentov.
• Vážený graf: Ku každej hrane možno priradiť číselnú hodnotu (váhu).
• Absencia slučiek a násobných hrán (jednoduchý graf): V jednoduchých neorientovaných grafoch môže medzi dvoma vrcholmi existovať najviac jedna hrana, a hrany neprepájajú vrchol sám so sebou (žiadne slučky).
• Kompletný graf: Graf, v ktorom je každý pár rôznych vrcholov spojený hranou. Označuje sa ako $K_n$, kde $n$ je počet vrcholov.
• Dvojzložkový graf: Množina vrcholov môže byť rozdelená na dve disjunktné podmnožiny $U$ a $W$, tak, že každá hrana spája vrchol z $U$ s vrcholom z $W$.