Kořenový graf

V teorii grafů je kořenový graf graf , ve kterém je jeden vrchol označen, aby se odlišil od ostatních vrcholů. Tento speciální vrchol se nazývá kořen grafu [1] [2] :454 .

Počet kořenových grafů pro 1, 2, 3, ... vrcholy je 1, 2, 6, 20, 90, 544, ... (sekvence A000666 v OEIS ).

Kořenové grafy lze kombinovat pomocí kořenového součinu grafů .

Zakořeněné stromy

Zakořeněný strom je strom, ve kterém je vybrán jeden vrchol (kořen stromu). Formálně je kořenový strom definován jako konečná množina jednoho nebo více uzlů s následujícími vlastnostmi: $T$

existuje jeden kořen stromu ; $T$
zbývající uzly (kromě kořene) jsou rozděleny mezi disjunktní množiny a každá z množin je kořenový strom; stromy se nazývají podstromy daného kořene . $m\geq 0$ $T_{1},...,T_{m}$ $T_{1},...,T_{m}$ $T$

Související definice

Úroveň uzlu - délka cesty od kořene k uzlu. Lze definovat rekurzivně:

úroveň kořene stromu je 0; $T$
úroveň jakéhokoli jiného uzlu je o jednu větší než úroveň kořene nejbližšího podstromu stromu obsahujícího tento uzel. $T$

Strom s vyznačeným vrcholem se nazývá kořenový strom .
- $m$ Třetí vrstva stromu je množina uzlů stromu na úrovni od kořene stromu. $T$ $m$
- částečné pořadí na vrcholech: pokud jsou vrcholy a různé a vrchol leží na (jedinečném!) elementárním řetězci spojujícím kořen s vrcholem . $u\prec v$ $u$ $proti$ $u$ $proti$
- kořenový podstrom zakořeněný jako podgraf . $proti$ $\{v\}\pohár \{w\mid v<w\}$
- V kontextu, kde se předpokládá, že strom má kořen, se strom bez rozlišujícího kořene nazývá volný .

Poznámky

↑ Daniel Zwillinger. CRC Standardní matematické tabulky a vzorce, 32. vydání. - CRC Press, 2011. - ISBN 978-1-4398-3550-0 .
↑ Frank Harary. Počet lineárních, řízených, kořenových a spojených grafů // Transactions of the American Mathematical Society . - 1955. - Vydání. 78 . - S. 445-463 . - doi : 10.1090/S0002-9947-1955-0068198-2 .

Literatura

CD Godsil, BD McKay. Nový grafový produkt a jeho spektrum // Bull. Jižní. Matematika. soc. - 1978. - T. 18 , no. 1 . - S. 21-28 . - doi : 10.1017/S0004972700007760 .
Frank Harary. Počet lineárních, řízených, kořenových a spojených grafů // Transactions of the American Mathematical Society . - 1955. - Vydání. 78 . - S. 445-463 . - doi : 10.1090/S0002-9947-1955-0068198-2 .

Externí odkazy

Weisstein, Eric W. Rooted Graph (anglicky) na webových stránkách Wolfram MathWorld .