Rotdiagram

I grafteorin är en rotgraf en graf där en vertex är märkt för att skilja den från andra hörn. Denna speciella vertex kallas grafens rot [1] [2] :454 .

Antalet rotgrafer för 1, 2, 3, ... hörn är 1, 2, 6, 20, 90, 544, ... (sekvens A000666 i OEIS ).

Rotade grafer kan kombineras med rotprodukten av grafer .

Rotade träd

Ett rotat träd är ett träd där en vertex (trädets rot) är vald. Formellt definieras ett rotat träd som en ändlig uppsättning av en eller flera noder med följande egenskaper: $T$

det finns en rot av trädet ; $T$
de återstående noderna (förutom roten) är fördelade bland disjunkta uppsättningar , och var och en av uppsättningarna är ett rotat träd; träd kallas underträd till den givna roten . $m\geq 0$ $T_{1},...,T_{m}$ $T_{1},...,T_{m}$ $T$

Relaterade definitioner

Nodnivå - längden på vägen från roten till noden. Kan definieras rekursivt:

trädrotnivån är 0; $T$
nivån för någon annan nod är en högre än nivån på roten för det närmaste underträdet i trädet som innehåller den noden. $T$

Ett träd med en markerad vertex kallas ett rotat träd .
- $m$ Trädets :e skikt är uppsättningen trädnoder, på nivån från trädets rot . $T$ $m$
- partiell ordning på hörnen: om hörnen och är olika och vertexen ligger på den (unika!) elementära kedjan som förbinder roten med vertexen . $u\prec v$ $u$ $v$ $u$ $v$
- rotunderträd rotat som undergraf . $v$ $\{v\}\cup \{w\mid v<w\}$
- I ett sammanhang där ett träd antas ha en rot sägs ett träd utan en förnämlig rot vara fritt .

Anteckningar

↑ Daniel Zwillinger. CRC standard matematiska tabeller och formler, 32:a upplagan. - CRC Press, 2011. - ISBN 978-1-4398-3550-0 .
↑ Frank Harary. Antalet linjära, riktade, rotade och sammankopplade grafer // Transactions of the American Mathematical Society . - 1955. - Utgåva. 78 . - S. 445-463 . - doi : 10.1090/S0002-9947-1955-0068198-2 .

Litteratur

CD Godsil, BD McKay. En ny grafprodukt och dess spektrum // Bull. Austral. Matematik. soc. - 1978. - T. 18 , nr. 1 . - S. 21-28 . - doi : 10.1017/S0004972700007760 .
Frank Harary. Antalet linjära, riktade, rotade och sammankopplade grafer // Transactions of the American Mathematical Society . - 1955. - Utgåva. 78 . - S. 445-463 . - doi : 10.1090/S0002-9947-1955-0068198-2 .

Externa länkar

Weisstein, Eric W. Rooted Graph (engelska) på Wolfram MathWorlds webbplats .