Grafico del percorso - Path graph

Questo articolo è circa una famiglia di grafici. Per i percorsi come parti di grafici arbitrari, vedere Path (teoria dei grafi) .
Da non confondere con il grafico a linee .
Grafico del percorso
Path-graph.svg
Un grafico di percorso su 6 vertici
vertici n
bordi n − 1
Raggio ⌊ n / 2⌋
Diametro n − 1
automorfismi 2
Numero cromatico 2
Indice cromatico 2
Spettro {2 cos( k π / ( n  + 1)); k = 1, ..., n }
Proprietà Unità di distanza
Grafico bipartito
Albero
Notazione
Tabella di grafici e parametri

Nel campo matematico della teoria dei grafi , un grafico percorso o grafico lineare è un grafo i cui vertici possono essere elencati nell'ordine v 1 , v 2 , …, v n tale che gli archi siano { v i , v i +1 } dove i = 1, 2, …, n − 1. Equivalentemente, un cammino con almeno due vertici è connesso e ha due vertici terminali (vertici che hanno grado 1), mentre tutti gli altri (se ce ne sono) hanno grado 2.

I percorsi sono spesso importanti nel loro ruolo di sottografi di altri grafi, nel qual caso vengono chiamati percorsi in quel grafo. Un percorso è un esempio particolarmente semplice di albero , e infatti i percorsi sono esattamente gli alberi in cui nessun vertice ha grado 3 o più. Un'unione disgiunta dei percorsi è chiamato un bosco lineari .

I percorsi sono concetti fondamentali della teoria dei grafi, descritti nelle sezioni introduttive della maggior parte dei testi di teoria dei grafi. Vedi, ad esempio, Bondy e Murty (1976), Gibbons (1985) o Diestel (2005).

Come diagrammi Dynkin

In algebra , i grafici dei percorsi appaiono come i diagrammi di Dynkin di tipo A. In quanto tali, classificano il sistema di radici di tipo A e il gruppo di Weyl di tipo A, che è il gruppo simmetrico .

Guarda anche

Riferimenti

  • Bondy, JA ; Murty, USR (1976). Teoria dei grafi con applicazioni . Olanda settentrionale. pp.  12-21 . ISBN 0-444-19451-7.
  • Diestel, Reinhard (2005). Teoria dei grafi (3a ed.). Testi di laurea in matematica , vol. 173, Springer-Verlag. pp. 6-9. ISBN 3-540-26182-6.

link esterno