Hispanopedia WikiEn el campo matemático de la teoría de grafos , un grafo de caminos (o grafo lineal ) es un grafo cuyos vértices se pueden enumerar en el orden v 1 , v 2 , ..., v n de tal manera que las aristas son { v i , v i +1 } donde i = 1, 2, ..., n − 1 . De forma equivalente, un camino con al menos dos vértices está conectado y tiene dos vértices terminales (vértices de grado 1), mientras que todos los demás (si los hay) tienen grado 2.
Los caminos suelen ser importantes por su función como subgrafos de otros grafos, en cuyo caso se denominan caminos en ese grafo. Un camino es un ejemplo particularmente simple de árbol , y de hecho, los caminos son precisamente los árboles en los que ningún vértice tiene grado 3 o superior. Una unión disjunta de caminos se denomina bosque lineal .
Los caminos son conceptos fundamentales de la teoría de grafos, descritos en las secciones introductorias de la mayoría de los textos sobre teoría de grafos. Véanse, por ejemplo, Bondy y Murty (1976), Gibbons (1985) o Diestel (2005).
Como diagramas de Dynkin
En álgebra , los grafos de caminos aparecen como los diagramas de Dynkin de tipo A. Como tales, clasifican el sistema de raíces de tipo A y el grupo de Weyl de tipo A, que es el grupo simétrico .
Véase también
Referencias
- ↑ Si bien lo más común es usar P n para un camino de n vértices, algunos autores (por ejemplo Diestel) usan P n para un camino de n aristas y n +1 vértices.
- Bondy, JA ; Murty, USR (1976). Teoría de grafos con aplicaciones . North Holland. págs. 12–21 . ISBN 0-444-19451-7.
- Diestel, Reinhard (2005). Teoría de grafos (3.ª ed.). Textos de posgrado en matemáticas , vol. 173, Springer-Verlag, pp. 6-9 . ISBN 3-540-26182-6.
Enlaces externos
- Weisstein, Eric W. "Grafo de ruta" . MathWorld .
- Árboles (teoría de grafos)
- Familias paramétricas de grafos
