En el campo matemático de la teoría de grafos , un grafo de trayectoria o grafo lineal es un grafo cuyos vértices se pueden enumerar en el orden v 1 , v 2 ,…, v n de modo que las aristas sean { v i , v i +1 } donde i = 1, 2,…, n - 1. De manera equivalente, un camino con al menos dos vértices está conectado y tiene dos vértices terminales (vértices que tienen grado 1), mientras que todos los demás (si los hay) tienen grado 2.
Gráfico de ruta | |
---|---|
Vértices | norte |
Bordes | n - 1 |
Radio | ⌊ n / 2⌋ |
Diámetro | n - 1 |
Automorfismos | 2 |
Número cromático | 2 |
Índice cromático | 2 |
Espectro | {2 cos ( k π / ( n + 1)); k = 1, ..., n } |
Propiedades | Unidad de distancia Gráfico bipartito Árbol |
Notación | |
Tabla de gráficos y parámetros |
Las rutas suelen ser importantes en su función de subgráficos de otros gráficos, en cuyo caso se denominan rutas en ese gráfico. Un camino es un ejemplo particularmente simple de un árbol y, de hecho, los caminos son exactamente los árboles en los que ningún vértice tiene grado 3 o más. 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 de teoría de grafos. Véase, por ejemplo, Bondy y Murty (1976), Gibbons (1985) o Diestel (2005).
Como diagramas de Dynkin
En álgebra , los gráficos de trayectoria 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 .
Ver también
Referencias
- Bondy, JA ; Murty, USR (1976). Teoría de grafos con aplicaciones . Holanda Septentrional. 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. págs. 6–9. ISBN 3-540-26182-6.