Kružnica (teória grafov)

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).

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

• orientovaný graf

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

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

• neorientovaný graf

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

každý vrchol neorientovanej kružnice má stupeň 2.^[1]

• 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)

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

Tento článok týkajúci sa matematiky je zatiaľ „výhonok“. Pomôž Wikipédii tým, že ho doplníš a rozšíriš.