Útgráf
Ebben a cikkben mindent részletesen megvizsgálunk, ami a Útgráf-hez kapcsolódik. Történelmi eredetétől napjaink relevanciájáig, különféle szempontjain és alkalmazásain keresztül. A Útgráf nagyon fontos téma, és felkeltette a szakértők és a nagyközönség érdeklődését. Ennek mentén elmélyülünk jelentésében, hatásában és időbeli alakulásában. Hasonlóképpen elemezzük a különböző perspektívákat és megközelítéseket, amelyeket megadtak, valamint a különböző területeken gyakorolt következményeket és következményeket. Olvasson tovább, és fedezzen fel mindent, amit tudnia kell a Útgráf-ről és a modern világra gyakorolt hatásáról.
- Ez a szócikk az útgráfnak nevezett gráfcsaládról szól. A bármilyen gráfban előforduló utakkal az út (gráfelmélet) cikk foglalkozik
| Útgráf | |
 | |
| Útgráf 6 csúccsal | |
| Csúcsok száma | n |
| Élek száma | n−1 |
| Sugár | ⌊n / 2⌋ |
| Átmérő | n−1 |
| Kromatikus szám | 2 |
| Élkromatikus szám | 2 |
| Automorfizmusok | 2 |
| Génusz | 0 |
| Spektrum | {2 cos(k π / (n + 1)); k = 1, ..., n} |
| Egyéb | Egységtávolsággráf Gyufagráf Páros gráf Fa ½-szívós |
| Jelölés | |
A gráfelmélet területén az útgráf (path graph) vagy lineáris gráf olyan gráf, melyek csúcsai felsorolhatók v1, v2, …, vn sorrendben oly módon, hogy élei pontosan {vi, vi+1}, ahol i = 1, 2, …, n − 1. Ezzel ekvivalens megfogalmazásban a legalább 2 csúcsból álló útgráf összefüggő, van két véghelyzetű csúcsa 1 fokszámmal, bármely más csúcs fokszáma pedig 2.
Az útgráfok fontosak más gráfok részeiként, ilyen esetekben egyszerűen a gráfban lévő útnak nevezik őket. Az útgráfok a fák nagyon egyszerű változatai, pontosan olyan fák, melyekben egyik csúcs fokszáma sem magasabb 2-nél.
Az útgráfok és utak a gráfelmélet alapvető koncepciói közé tartoznak, a legtöbb gráfelméleti könyv bevezető részében foglalkoznak velük. Lásd pl. Bondy and Murty (1976), Gibbons (1985) vagy Diestel (2005).
Útgráfok mint Dynkin-diagramok
Az algebra területén az útgráfok „A” típusú Dynkin-diagramokként jelennek meg. Ilyenformában az A típusú gyökrendszert és az A típusú Weyl-csoportot osztályozzák, ami a szimmetrikus csoport.
Kapcsolódó szócikkek
Jegyzetek
- Bondy, J. A.; Murty, U. S. R.. Graph Theory with Applications [archivált változat]. North Holland, 12–21. o. (1976). ISBN 0-444-19451-7. Hozzáférés ideje: 2016. június 12. [archiválás ideje: 2010. április 13.]
- Diestel, Reinhard. Graph Theory, 3rd, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, 6–9. o. (2005). ISBN 3-540-26182-6
További információk
- Weisstein, Eric W.: Path Graph (angol nyelven). Wolfram MathWorld