Gráfico raíz

En la teoría de grafos, un gráfico raíz es un gráfico en el que un vértice está etiquetado para distinguirlo de otros vértices. Este vértice especial se llama raíz del gráfico [1] [2] :454 .

El número de gráficos raíz para 1, 2, 3, ... vértices es 1, 2, 6, 20, 90, 544, ... (secuencia A000666 en OEIS ).

Los gráficos con raíces se pueden combinar usando el producto raíz de los gráficos .

Árboles enraizados

Un árbol con raíz es un árbol en el que se selecciona un vértice (la raíz del árbol). Formalmente, un árbol enraizado se define como un conjunto finito de uno o más nodos con las siguientes propiedades: $T$

hay una raíz del árbol ; $T$
los nodos restantes (excepto la raíz) se distribuyen entre conjuntos disjuntos , y cada uno de los conjuntos es un árbol con raíz; los árboles se llaman subárboles de la raíz dada . $m\geq 0$ $T_{1},...,T_{m}$ $T_{1},...,T_{m}$ $T$

Definiciones relacionadas

Nivel de nodo : la longitud de la ruta desde la raíz hasta el nodo. Se puede definir recursivamente:

el nivel de la raíz del árbol es 0; $T$
el nivel de cualquier otro nodo es uno mayor que el nivel de la raíz del subárbol más cercano del árbol que contiene ese nodo. $T$

Un árbol con un vértice marcado se llama árbol enraizado .
- $metro$ El nivel th del árbol es el conjunto de nodos del árbol, al nivel de la raíz del árbol. $T$ $metro$
- orden parcial en los vértices: si los vértices y son diferentes y el vértice se encuentra en la cadena elemental (¡única!) que conecta la raíz con el vértice . $u\precv$ $tu$ $v$ $tu$ $v$
- subárbol raíz enraizado como subgrafo . $v$ $\{v\}\taza \{w\mid v<w\}$
- En un contexto en el que se supone que un árbol tiene una raíz, se dice que un árbol sin una raíz distinguida es libre .

Notas

↑ Daniel Zwillinger. Tablas y fórmulas matemáticas estándar de CRC, 32.ª edición. - CRC Press, 2011. - ISBN 978-1-4398-3550-0 .
↑ Frank Harary. El número de gráficos lineales, dirigidos, con raíces y conectados // Transacciones de la Sociedad Matemática Estadounidense . - 1955. - Emisión. 78 . - S. 445-463 . -doi : 10.1090 / S0002-9947-1955-0068198-2 .

Literatura

CD Godsil, BD McKay. Un nuevo producto gráfico y su espectro // Bull. Austral. Matemáticas. soc. - 1978. - T. 18 , núm. 1 . - S. 21-28 . -doi : 10.1017/ S0004972700007760 .
Frank Harary. El número de gráficos lineales, dirigidos, con raíces y conectados // Transacciones de la Sociedad Matemática Estadounidense . - 1955. - Emisión. 78 . - S. 445-463 . -doi : 10.1090 / S0002-9947-1955-0068198-2 .

Enlaces externos

Weisstein, Eric W. Rooted Graph (inglés) en el sitio web de Wolfram MathWorld .