Graficul rădăcină

În teoria grafurilor, un graf rădăcină este un graf în care un vârf este etichetat pentru a-l distinge de alte vârfuri. Acest vârf special se numește rădăcina graficului [1] [2] :454 .

Numărul de grafice rădăcină pentru 1, 2, 3, ... vârfuri este 1, 2, 6, 20, 90, 544, ... (secvența A000666 în OEIS ).

Graficele înrădăcinate pot fi combinate folosind produsul rădăcină al graficelor .

Copaci înrădăcinați

Un arbore înrădăcinat este un arbore în care este selectat un vârf (rădăcina arborelui). În mod formal, un arbore înrădăcinat este definit ca un set finit de unul sau mai multe noduri cu următoarele proprietăți: $T$

există o singură rădăcină a copacului ; $T$
nodurile rămase (cu excepția rădăcinii) sunt distribuite între mulțimi disjunse și fiecare dintre mulțimi este un arbore înrădăcinat; arborii sunt numiți subarbori ai rădăcinii date . $m\geq 0$ $T_{1},...,T_{m}$ $T_{1},...,T_{m}$ $T$

Definiții înrudite

Nivelul nodului - lungimea căii de la rădăcină la nod. Poate fi definit recursiv:

nivelul rădăcinii arborelui este 0; $T$
nivelul oricărui alt nod este cu unul mai mare decât nivelul rădăcinii celui mai apropiat subarboresc al arborelui care conține acel nod. $T$

Un copac cu un vârf marcat se numește arbore înrădăcinat .
- $m$ Nivelul al treilea al arborelui este setul de noduri de arbore, la nivelul de la rădăcina arborelui. $T$ $m$
- ordine parțială pe vârfuri: dacă vârfurile și sunt diferite și vârful se află pe lanțul elementar (unic!) care leagă rădăcina cu vârful . $u\prec v$ $u$ $v$ $u$ $v$
- subarbore rădăcină înrădăcinat ca subgraf . $v$ $\{v\}\cup \{w\mid v<w\}$
- Într-un context în care se presupune că un copac are o rădăcină, se spune că un copac fără o rădăcină distinctă este liber .

Note

↑ Daniel Zwillinger. CRC Standard Mathematical Tables and Formule, Ediția a 32-a. - CRC Press, 2011. - ISBN 978-1-4398-3550-0 .
↑ Frank Harary. Numărul de grafice liniare, direcționate, înrădăcinate și conectate // Tranzacții ale Societății Americane de Matematică . - 1955. - Emisiune. 78 . - S. 445-463 . - doi : 10.1090/S0002-9947-1955-0068198-2 .

Literatură

CD Godsil, BD McKay. Un nou produs grafic și spectrul său // Bull. Austral. Matematică. soc. - 1978. - T. 18 , nr. 1 . - S. 21-28 . - doi : 10.1017/S0004972700007760 .
Frank Harary. Numărul de grafice liniare, direcționate, înrădăcinate și conectate // Tranzacții ale Societății Americane de Matematică . - 1955. - Emisiune. 78 . - S. 445-463 . - doi : 10.1090/S0002-9947-1955-0068198-2 .

Link- uri externe

Weisstein, Eric W. Rooted Graph (engleză) pe site-ul Wolfram MathWorld .