Grafová postupnosť

**Grafová postupnosť** je postupnosť  \{ \mathrm{deg}_G \, \nu_i \}^n_{i=1}, kde n je počet vrcholov grafu G a   sú z množiny V pre i = 1, 2, \ldots, n.

Každému grafu G = (V,E) s V = \{v_1, \ldots, v_n\} možno jednoznačne priradiť postupnosť \left\{ s_i\right\}^n_{i=1}, kde = s_i = \{ \mathrm{deg}_G \, \nu_i \}^n_{i=1}  pre i = 1, \ldots, n.

V obyčajnom neorientovanom grafe G s vrcholovou množinou V(G)=\{ \nu_1, \nu_2, \ldots, \nu_n \}  môžeme zostrojiť postupnosť \mathrm{deg}(\nu_1), \mathrm{deg}(\nu_2), \ldots, \mathrm{deg}(\nu_n) nezáporných celých čísel. Takúto postupnosť nazývame stupňová postupnosť. Aby postupnosť bola grafová, musí pre každý index i platiť d_i \leq n-1 a samozrejme aj \left(\sum_{i=1}^n d_i\right) je párne číslo

Ak vrcholy budú označené tak, že \mathrm{deg} (\nu_1) \geq \mathrm{deg} (\nu_2) \geq \ldots \geq \mathrm{deg} (\nu_n) , túto postupnosť nazveme grafová postupnosť. 

## Veta o grafových postupnostiach
Pre grafové postupnosti platí užitočná veta:
Nech je daná postupnosť \left(\{d_i\}_{i=1}^n\right),  n ≥ 2, pričom d_1\geq 1_2\geq\ldots d_n a zároveň d_1 \leq n-1. Potom \left(\{d_i\}_{i=1}^n\right) je grafová vtedy, keď je grafová postupnosť.

   **d<sub>2</sub> − 1, d − 1, . . . , d<sub>d1</sub> +1 − 1, d<sub>d1</sub>+2, . . . , d<sub>n</sub>**

**Dôkaz:**

Ak (d_2 - 1, d_3 - 1, \ldots, d_{d1} + 1 - 1, d_{d1} + 2, \ldots, d_n) je grafová postupnosť, tak existuje graf G_2 = (V_2, E_2), V_2 = \{v_2, \ldots, v_n\} taký, že pre každé i = 2, \ldots, d_1 + 1 je \mathrm{deg} G_2 (v_i) = d_i - 1 a pre každé j = d_1 + 2, \ldots, n je \mathrm{deg} G_2 (v_i) = d_i.

Zostrojme graf G1 tak, že ku grafu G2 pridajme nový vrchol v1 a spojme ho novými hranami s vrcholmi v2, . . . , vd1+1. Potom platí degG1(v1) = d1, pre i = 2, \ldots, d_1 + 1 je degG_1(v_i) = degG_2(v_i) + 1 = d_i - 1 + 1 = d_i a pre ostatné i je degG_1 (v_i) = degG_2 (v_i) = d_i.

Teda G_1 má postupnosť stupňov vrcholov práve \{d_i\} n i = 1, čiže táto postupnosť je grafová.

Túto vetu použijeme aj pri konštrukcii algoritmu na zistenie, či daná postupnosť je grafová.

## Algoritmus na zistenie, či daná postupnosť je grafová
    1.	Ak postupnosť obsahuje člen prevyšujúci n-1, postupnosť nie je grafová. STOP. Inak pokračuj krokom 2.
    2.	Ak sú všetky členy postupnosti rovné 0, potom postupnosť je grafová. STOP
        Ak postupnosť obsahuje záporné číslo, potom postupnosť grafová nie je. STOP
        Inak pokračuj bodom 3.
    3.	Ak je to potrebné, usporiadaj členy postupnosti zostupne. Pokračuj krokom 4.
    4.	Zmaž prvý člen (nazvime ho k) a zníž o jednotku hodnotu nasledujúcich k členov postupnosti. Pokračuj krokom 2.

**Príklad:**

Zistite, či je postupnosť grafová:
a) 6, 5, 4, 4, 4, 3, 2, 1 
b) 8, 5, 3, 3, 3, 3, 2, 1 
c) 5, 4, 4, 3, 3, 2, 2, 1 

Riešenie:
:a) Postupnosť nie je grafová, pretože v grafe musí byť počet vrcholov nepárneho stupňa párny, čo v tomto prípade neplatí. Tu je počet nepárnych čísel 3. 
:b) Táto postupnosť tiež nie je grafová, lebo v grafe s n vrcholmi je maximálny možný stupeň vrcholu n-1. Pre 8 vrcholov je teda maximálny možný stupeň 7. 
:c) Obidve predchádzajúce podmienky sú splnené, počet vrcholov nepárneho stupňa je 4, teda párny a maximálny možný stupeň je 7, čo nie je porušené. Platí, že pôvodná postupnosť je grafová práve vtedy, ak je grafová aj postupnosť, ktorú z nej dostaneme takto: Zoradíme čísla na nerastúcu postupnosť. Vynecháme prvé číslo k a od k nasledujúcich čísel odpočítame jednotku. Postupnosť znovu zoradíme a tento postup opakujeme dovtedy, pokiaľ nedostaneme postupnosť, o ktorej vieme ľahko rozhodnúť, či je, alebo nie je grafová. 

     5, 4, 4, 3, 3, 2, 2, 1
     3, 3, 2, 2, 1, 2, 1
     zoradíme 3, 3, 2, 2, 2, 1, 1
     2, 1, 1, 2, 1, 1
     zoradíme 2, 2, 1, 1, 1, 1
     1, 0, 1, 1, 1
     zoradíme 1, 1, 1, 1
     0, 1, 1
     zoradíme 1, 1
     1
     0

Zhrnutie: V grafe musí byť počet vrcholov nepárneho stupňa párny. Graf s n vrcholmi musí mať maximálny možný stupeň vrcholu n-1.

## Externé odkazy
* http://fpedas.uniza.sk/~stacho/predn_02.pdf
* http://umv.science.upjs.sk/madaras/slide8.pdf
* http://umv.science.upjs.sk/madaras/dodatki.pdf

Kategória:Teória grafov