Rodgraf

I grafteori er en rodgraf en graf , hvor et toppunkt er mærket for at skelne det fra andre toppunkter. Dette specielle toppunkt kaldes grafens rod [1] [2] :454 .

Antallet af rodgrafer for 1, 2, 3, ... toppunkter er 1, 2, 6, 20, 90, 544, ... (sekvens A000666 i OEIS ).

Rodede grafer kan kombineres ved hjælp af rodproduktet af grafer .

Rodede træer

Et rodfæstet træ er et træ , hvor et toppunkt (træets rod) er valgt. Formelt er et rodfæstet træ defineret som et endeligt sæt af en eller flere noder med følgende egenskaber: $T$

der er en rod af træet ; $T$
de resterende noder (bortset fra roden) er fordelt blandt usammenhængende sæt , og hvert af sættene er et rodfæstet træ; træer kaldes undertræer af den givne rod . $m\geq 0$ $T_{1},...,T_{m}$ $T_{1},...,T_{m}$ $T$

Relaterede definitioner

Node niveau - længden af stien fra roden til noden. Kan defineres rekursivt:

trærodniveauet er 0; $T$
niveauet af enhver anden knude er en højere end niveauet af roden af det nærmeste undertræ i træet , der indeholder den knude. $T$

Et træ med et markeret toppunkt kaldes et rodfæstet træ .
- $m$ Træets th tier er sættet af træknuder i niveauet fra træets rod. $T$ $m$
- delrækkefølge på toppunkterne: hvis toppunkterne og er forskellige og toppunktet ligger på den (unikke!) elementære kæde, der forbinder roden med toppunktet . $u\prec v$ $u$ $v$ $u$ $v$
- rod undertræ forankret som undergraf . $v$ $\{v\}\kop \{w\midt v<w\}$
- I en sammenhæng, hvor et træ antages at have en rod, siges et træ uden en fornem rod at være frit .

Noter

↑ Daniel Zwillinger. CRC standard matematiske tabeller og formler, 32. udgave. - CRC Press, 2011. - ISBN 978-1-4398-3550-0 .
↑ Frank Harary. Antallet af lineære, rettede, rodfæstede og forbundne grafer // Transactions of the American Mathematical Society . - 1955. - Udgave. 78 . - S. 445-463 . - doi : 10.1090/S0002-9947-1955-0068198-2 .

Litteratur

CD Godsil, BD McKay. Et nyt grafprodukt og dets spektrum // Bull. Austral. Matematik. soc. - 1978. - T. 18 , no. 1 . - S. 21-28 . - doi : 10.1017/S0004972700007760 .
Frank Harary. Antallet af lineære, rettede, rodfæstede og forbundne grafer // Transactions of the American Mathematical Society . - 1955. - Udgave. 78 . - S. 445-463 . - doi : 10.1090/S0002-9947-1955-0068198-2 .

Eksterne links

Weisstein, Eric W. Rooted Graph (engelsk) på Wolfram MathWorld- webstedet .