Útgráf

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

Nem tévesztendő össze a következővel: élgráf.

Ú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	${\displaystyle P_{n}}$

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 v₁, v₂, …, v_n sorrendben oly módon, hogy élei pontosan {v_i, v_i+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

• Út (gráfelmélet)
• Feszített út
• Hernyógráf
• Teljes gráf
• Nullgráf
• Útfelbontás
• Kör (gráfelmélet)

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