Wykres ścieżki — Path graph
Wykres ścieżki | |
---|---|
Wierzchołki | n |
Krawędzie | n − 1 |
Promień | ⌊ n / 2⌋ |
Średnica | n − 1 |
Automorfizmy | 2 |
Liczba chromatyczna | 2 |
Indeks chromatyczny | 2 |
Widmo | {2 cos ( k π / ( n + 1)); k = 1, ..., n } |
Nieruchomości |
Jednostka odległości Wykres dwudzielny Drzewo |
Notacja | |
Tabela wykresów i parametrów |
W matematycznej dziedzinie teorii wykres , A wykres ścieżki lub liniowy wykres przedstawia wykres, którego wierzchołki mogą być wyświetlane w kolejności v 1 , V, 2 , ..., v n , tak że krawędzie są { V i , v i + 1 }, gdzie i = 1, 2, …, n − 1. Równoważnie ścieżka z co najmniej dwoma wierzchołkami jest połączona i ma dwa wierzchołki końcowe (wierzchołki o stopniu 1), podczas gdy wszystkie pozostałe (jeśli występują) mają stopień 2.
Ścieżki często odgrywają ważną rolę jako podgrafy innych grafów, w takim przypadku nazywane są ścieżkami w tym grafie. Ścieżka jest szczególnie prostym przykładem drzewa , aw rzeczywistości ścieżki są dokładnie drzewami, w których żaden wierzchołek nie ma stopnia 3 lub wyższego. Unia rozłącznych ścieżek nazywany jest liniowy las .
Ścieżki są podstawowymi pojęciami teorii grafów, opisanymi we wstępnych sekcjach większości tekstów dotyczących teorii grafów. Zobacz na przykład Bondy i Murty (1976), Gibbons (1985) lub Diestel (2005).
Jak diagramy Dynkina
W algebrze grafy ścieżkowe pojawiają się jako diagramy Dynkina typu A. Jako takie klasyfikują system pierwiastkowy typu A i grupę Weyla typu A, która jest grupą symetryczną .
Zobacz też
- Ścieżka (teoria grafów)
- Drzewo gąsienicy
- Kompletny wykres
- Wykres zerowy
- Rozkład ścieżki
- Cykl (teoria grafów)
Bibliografia
- Bondy, JA ; Murty, ZSRR (1976). Teoria grafów z aplikacjami . Północna Holandia. s. 12–21 . Numer ISBN 0-444-19451-7.
- Diestel, Reinhard (2005). Teoria grafów (3rd ed.). Teksty magisterskie z matematyki , t. 173, Springer-Verlag. s. 6–9. Numer ISBN 3-540-26182-6.