Kružnica (teória grafov)

Orientovaná kružnica na piatich vrcholoch

Kružnica alebo cyklus alebo uzavrený ťah v teórii grafov označuje taký graf, ktorý sa skladá z jediného cyklu – teda uzavretej postupnosti prepojených vrcholov. Kružnica môže byť orientovaná i neorientovaná.

Graf, ktorý ako podgraf obsahuje kružnicu, sa nazýva cyklický. V opačnom prípade sa nazýva acyklický (pozri strom).

Definícia

Kružnica je graf $C_{n}=(V,E)$, kde $V=\left\{v_{1},\ldots ,v_{n}\right\}$ a $E=\left\{e_{1},\ldots ,e_{n}\right\}$ a platí:

• orientovaný graf

$e_{i}=\left(v_{i},v_{i+1}\right),i=1,\ldots ,n-1$ a $e_{n}=\left(v_{n},v_{1}\right)$

každý vrchol orientovanej kružnice má vstupný i výstupný stupeň rovný 1

• neorientovaný graf

$e_{i}=\left\{v_{i},v_{i+1}\right\},i=1,\ldots ,n-1$ a $e_{n}=\left\{v_{n},v_{1}\right\}$

každý vrchol neorientovanej kružnice má stupeň 2.

Vlastnosti kružnice

• eulerovská kružnica – opíše všetky hrany grafu, viackrát tú istú hranu nepoužíva, do vrcholu môže vstupovať viackrát
• hamiltonovská kružnica – opíše všetky vrcholy grafu, nevstupuje do vrcholu viackrát, hrany nemusí obsahovať všetky
• kružnica v bipartitnom grafe (vrcholy sú rozdelené do dvoch častí, hrany vedú iba medzi časťami navzájom)

Zdroj

Tento článok je čiastočný alebo úplný preklad článku Kružnice (graf) na českej Wikipédii (číslo revízie nebolo určené).