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 ${\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]

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)

Referencie

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

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