Skóre grafu

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.

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. Předpokládejme, že $d_{1}\leq d_{2}\leq \ldots \leq 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\geq 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.

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}}=\emptyset \;$. 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ý).

Externí odkazy

• Článek o skóre na www.mathworld.com