Főmenü megnyitása
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

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.

Útgráf
Útgráf 6 csúccsal
Útgráf 6 csúccsal

Csúcsok száma n
Élek száma n−1
Sugárn / 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

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-diagramokSzerkesztés

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ócikkekSzerkesztés

JegyzetekSzerkesztés

További információkSzerkesztés