Skóre grafu

Z Wikipedie, otevřené encyklopedie

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 věty), ž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)

[editovat] Věta o skóre

Platí tzv. věta o skóre: Nechť \mathit{D} = (d_1, \ldots, d_n) je posloupnost přirozených čísel. 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 < n - d_n \\ d_i - 1, & i\ge n - d_n\;\end{cases}

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.

[editovat] Příklad

Mějme posloupnost (1, 2, 2, 3, 4, 5, 5). Postupně na ni budeme aplikovat větu o skóre:

  1. (1, 2, 2, 3, 4, 5, 5)
  2. (1, 1, 1, 2, 3, 4)
  3. (1, 0, 0, 1, 2), po přerovnání (0, 0, 1, 1, 2)
  4. (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ý).

[editovat] Externí odkazy

V jiných jazycích