Teorie grafů

Diplomová práce, MFF UK
Lukáš Jirovský
Matematika - MIUZV


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

Stupně vrcholů

Definice

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

Příklad

Stupně vrcholů v grafu (příklad)
Obr. č. 2.14 - Příklad stupňů vrcholů v grafu

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

Skóre grafu

Definice

Označme vrcholy grafu G postupně v1, v2,...,vn (v libovolně zvoleném pořadí). Posloupnost
(degG(v1), degG(v2),..., degG(vn))
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

Skóre grafu
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.

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


Úvod

Základní pojmy

Vybrané problémy

Procvičování