Skóre grafu

posloupnost stupňů vrcholů grafu v libovolném pořadí

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

editovat

Pro jednoduché grafy platí tzv. věta o skóre: Nechť   je posloupnost přirozených čísel. Předpokládejme, že   a označme posloupnost  , kde  

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

editovat

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  . 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

editovat