Skóre grafu

Technology

12 hours ago

Author

V teorii grafů se termínem skóre grafu označuje libovolně uspořádaná posloupnost stupňů jeho vrcholů. Dvě skóre považujeme za stejná, pokud jedno dostaneme přerovnáním čísel (permutací) druhého - tzn. na zvoleném pořadí vrcholů nezáleží.

Dva isomorfní grafy mají shodné skóre, z toho vyplývá (obměnou implikace), že dva grafy s různým skóre jsou nutně neisomorfní. Opačná implikace ovšem neplatí, mají-li dva grafy stejné skóre, nemusí být vůbec isomorfní - to dokazuje následující příklad.

Dva trojúhelníky Šestiúhelník

Tyto grafy jsou různé (jeden je dokonce souvislý a druhý nesouvislý), přitom mají stejné skóre - (2, 2, 2, 2, 2, 2)

Věta o skóre

Pro jednoduché grafy platí tzv. věta o skóre: Nechť \mathit{D} = (d_1, \ldots, d_n) je posloupnost přirozených čísel. +more Předpokládejme, že d_1 \le d_2 \le\ldots\le d_n a označme posloupnost \mathit{D'} = (d_1', \ldots, d_{n-1}'), kde d_i' = \begin{cases}d_i, & i .

Pak D je skóre (nějakého) grafu právě tehdy, když D' je skóre grafu. Názorně si to lze představit tak, že z grafu odstraníme poslední vrchol stupně k, který byl spojený s předchozími k vrcholy v posloupnosti.

Příklad

Mějme posloupnost (1, 2, 2, 3, 4, 5, 5). Postupně na ni budeme aplikovat větu o skóre: # (1, 2, 2, 3, 4, 5, 5) # (1, 1, 1, 2, 3, 4) # (1, 0, 0, 1, 2), po přerovnání (0, 0, 1, 1, 2) # (0, 0, 0, 0)

Výsledná posloupnost (0, 0, 0, 0) je skóre grafu G = (V, E), kde \mathit{V} = \{v_1, v_2, v_3, v_4\}\mbox{a } \mathit{E} = \empty\;. Tedy i původní posloupnost je skóre grafu.

Poznámka: Takto lze pro každou posloupnost přirozených čísel rozhodnout, zda je to skóre nějakého grafu. Příbuzné tvrzení, princip sudosti, naopak umožňuje rozhodnout, kdy nějaká posloupnost skóre není (a to tehdy, je-li součet stupňů lichý).