Teorie grafů

2. Základní pojmy / Stupně vrcholů / skóre grafu

Stupně vrcholů

Definice

Nechť G je graf, v jeho vrchol. Symbolem deg_G(v) označme počet hran grafu G obsahujících vrhchol v.
Číslo deg_G(v) nazveme stupněm vrcholu v v grafu G.

Příklad

Obr. č. 2.14 - Příklad stupňů vrcholů v grafu

Obr. č. 2.15 - Příklad grafu s vrcholem stupně 0

Skóre grafu

Definice

Označme vrcholy grafu G postupně v₁, v₂,...,v_n (v libovolně zvoleném pořadí). Posloupnost
(deg_G(v₁), deg_G(v₂),..., deg_G(v_n))
nazýváme posloupnost stupňů grafu G nebo skóre grafu G.

Dvě skóre považujeme za stejná, pokud jedno můžeme dostat z druhého přerovnáním čísel (permutací).

Příklady

Obr. č. 2.16 - Příklad skóre grafu

Důsledek

Pokud dva grafy mají různé skóre, nejsou isomorfní.

Neplatí ale opak tohoto tvrzení (stejné skóre → isomorfní grafy). Příklad, který by takovéto tvrzení nesplnil, je na obr. č. 2.17 – zkuste si rozmyslet, proč grafy nejsou isomorfní, ačkoliv mají stejné skóre.

Obr. č. 2.17 - Příklad dvou neisomorfních grafů se stejným skóre