Teória grafov – grafová postupnosť

Grafová postupnosť

V obyčajnom neorientovanom grafe G s vrcholovou množinou $V (G) = {v_{1}, v_{2}, \dots, v_{n}}$ môžeme zostrojiť postupnosť $\deg (v_{1}), \deg (v_{1}), \dots, \deg (v_{n})$ nezáporných celých čísel. Takúto postupnosť nazývame stupňová postupnosť. Ak vrcholy budú označené tak, že $\deg (v_{1}) \geq \deg (v_{1}) \geq \dots \geq \deg (v_{n})$ , túto postupnosť nazveme grafová postupnosť. Pre grafové postupnosti platí užitočná veta:

Veta :Postupnosť $β_{1} : d_{1}, d_{2}, \dots, d_{n}$ nezáporných celých čísel, kde $d_{1} \geq d_{2} \geq \dots d_{n}$ a $p \geq 2$ a $d_{1} \geq 1$ je grafová práve vtedy, keď je grafová postupnosť

α_{2} : d_{2} - 1, d_{3} - 1, \dots, d_{d_{1} + 1} - 1, d_{d_{1} + 2}, d_{d_{1} + 3}, \dots, d_{n}

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

Ak postupnosť obsahuje člen prevyšujúci n-1, postupnosť nie je grafová. STOP. Inak pokračuj krokom 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.
Ak je to potrebné, usporiadaj členy postupnosti zostupne. Pokračuj krokom 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 daná stupňová postupnosť je grafová.

$α_{1} : 4, 4, 4, 4, 3, 3, 2$

Riešenie. Postupnosť je usporiadaná. Označme si neusporiadanú postupnosť, ktorá vznikne v i-tom kroku algoritmu $α_{i}$ a túto postupnosť po usporiadaní $β_{i}$ . krok 1. Postupnosť má 7 členov. Prvý člen 4 je menší ako 6 (neprevyšuje 5), pokračujeme bodom 2.

Podľa priebehu algoritmu môžeme zostrojiť obyčajný neorientovaný graf, ktorý bude mať grafovú postupnosť $α_{1}$ . Začneme poslednou postupnosťou $α_{6}$ a dostaneme sa až k postupnosti $α_{1}$ . Postupnosť $α_{6}$ je tvorená dvoma nulami, to znamená, že k nej prislúchajúci graf tvoria dva izolované vrcholy. (Podľa označenia v₄ a v₆ ). Z postupnosti $β_{5}$ sme ju dostali odstránením vrcholu v₁ a hrany incidentnej s ním a vrcholom v₆. Podobne postupujeme, až kým sa nedostaneme k postupnosti $β_{1} = α_{1}$ .

Grafovou postupnosťou však graf nie je jednoznačne určený. Grafovú postupnosť 2,2,2,1,1 spĺňajú grafy G1 i G2.

Teória grafov – grafová postupnosť

Grafová postupnosť

Navigačné menu

Hľadať