Trasový graf - Path graph - Wikipedia
| Trasový graf | |
|---|---|
 Dráhový graf na 6 vrcholech | |
| Vrcholy | n |
| Hrany | n − 1 |
| Poloměr | ⌊n / 2⌋ |
| Průměr | n − 1 |
| Automorfismy | 2 |
| Chromatické číslo | 2 |
| Chromatický index | 2 |
| Spektrum | {2 cos (k π / (n + 1)); k = 1, ..., n} |
| Vlastnosti | Jednotková vzdálenost Bipartitní graf Strom |
| Zápis | |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, a graf cesty nebo lineární graf je graf, jehož vrcholy lze uvést v objednávce proti1, proti2, …, protin takové, že hrany jsou {protii, protii+1} kde i = 1, 2, …, n - 1. Ekvivalentně je spojena cesta s alespoň dvěma vrcholy a má dva koncové vrcholy (vrcholy, které mají stupeň 1), zatímco všichni ostatní (pokud existují) mají stupeň 2.
Cesty jsou často důležité v jejich roli jako podgrafy dalších grafů, v takovém případě se nazývají cesty v tom grafu. Cesta je obzvláště jednoduchý příklad a strom a ve skutečnosti jsou cesty přesně stromy, ve kterých žádný vrchol nemá stupeň 3 nebo více. A disjunktní unie cest se nazývá a lineární les.
Cesty jsou základní pojmy teorie grafů popsané v úvodních částech většiny textů teorie grafů. Viz například Bondy a Murty (1976), Gibbons (1985) nebo Diestel (2005).
Jako Dynkinovy diagramy
v algebra, grafy cesty se zobrazí jako Dynkinovy diagramy typu A. Jako takové klasifikují kořenový systém typu A a Weylova skupina typu A, což je symetrická skupina.
Viz také
Reference
- Bondy, J. A.; Murty, USA (1976). Teorie grafů s aplikacemi. Severní Holandsko. str.12–21. ISBN 0-444-19451-7.
- Diestel, Reinhard (2005). Teorie grafů (3. vyd.). Postgraduální texty z matematiky, sv. 173, Springer-Verlag. s. 6–9. ISBN 3-540-26182-6.