árbol centrado

Gráfico de árbol con 1 o 2 centros.

A la izquierda un árbol centrado, a la derecha uno bicéntrico. Los números muestran la excentricidad de cada nodo.

En el subcampo matemático de la teoría de grafos , un árbol centrado es un árbol con un solo centro , y un árbol bicéntrico es un árbol con dos centros.

Dado un gráfico, la excentricidad de un vértice v se define como la mayor distancia de v a cualquier otro vértice. Un centro de un gráfico es un vértice con excentricidad mínima . Un gráfico puede tener un número arbitrario de centros. Sin embargo, Jordan (1869) ha demostrado que para los árboles sólo existen dos posibilidades:

1. El árbol tiene precisamente un centro (árboles centrados).
2. El árbol tiene precisamente dos centros (árboles bicéntricos). En este caso, los dos centros son adyacentes.

Una prueba de este hecho la da, por ejemplo, Harary. ^[1]

Notas

1. (Harary 1969), Teorema 4.2

Referencias

• Jordania, Camille (1869). "Sobre los ensamblajes de líneas". Journal für die reine und angewandte Mathematik (en francés). 70 (2): 185-190.
• Harary, Frank (1969). Teoría de grafos . Profesional de Addison-Wesley.

enlaces externos

• Weisstein, Eric W. "Árbol bicéntrico". MundoMatemático .
• Weisstein, Eric W. "Árbol centrado". MundoMatemático .