Útgráf forrásának megtekintése

:''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''
{{más|élgráf}}

{{gráf infobox
 | név     = Útgráf
 | kép    = Path-graph.svg
 | képaláírás = Útgráf 6 csúccsal
 | névadó = 
 | csúcsok = ''n''
 | élek    = ''n''&minus;1
 | sugár   = ⌊''n'' / 2⌋
 | átmérő = ''n''&minus;1
 | derékbőség = 
 | automorfizmusok = 2
 | kromatikus szám = 2
 | élkromatikus szám  = 2
 | génusz = 0
 | spektrum = {2 cos(''k'' π / (''n''&nbsp;+&nbsp;1)); ''k'' = 1, ..., ''n''}
 | egyéb = [[Egységtávolsággráf]]<br/>[[Gyufagráf]]<br/>[[Páros gráf]]<br/>[[Fa (gráfelmélet)|Fa]]<br/>[[gráf szívóssága|½-szívós]]
 | jelölés = <math>P_n</math>
}}
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''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub> sorrendben oly módon, hogy élei pontosan {{nobreak|{''v''<sub>''i''</sub>, ''v''<sub>''i''+1</sub>}}}, 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ám (gráfelmélet)|fokszámmal]], bármely más csúcs fokszáma pedig 2.

Az útgráfok fontosak más gráfok [[Gráfelméleti fogalomtár#Részgráfok|részeiként]], ilyen esetekben egyszerűen a gráfban lévő [[Út (gráfelmélet)|útnak]] nevezik őket. Az útgráfok a [[fa (gráfelmélet)|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-diagram]]okként jelennek meg. Ilyenformában az A típusú [[gyökrendszer]]t és az A típusú [[Weyl-csoport]]ot 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]]
*[[Útszélesség|Útfelbontás]]
*[[Kör (gráfelmélet)]]

== Jegyzetek ==

*{{cite book
 |author        = [[John Adrian Bondy|Bondy, J. A.]]; [[U. S. R. Murty|Murty, U. S. R.]]
 |title         = Graph Theory with Applications
 |year          = 1976
 |publisher     = North Holland
 |isbn          = 0-444-19451-7
 |pages         = 12–21
 |url           = http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
 |accessdate    = 2016-06-12
 |archívurl    = https://web.archive.org/web/20100413104345/http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
 |archívdátum = 2010-04-13
 |archiveurl    = https://web.archive.org/web/20100413104345/http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
 |archivedate   = 2010-04-13
}}
*{{cite book
 | author = Diestel, Reinhard
 | title = Graph Theory
 | edition = 3rd
 | url = http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
 | publisher = [[Graduate Texts in Mathematics]], vol. 173, Springer-Verlag
 | year = 2005
 | isbn = 3-540-26182-6
 | pages = 6–9}}

== További információk ==
* {{MathWorld | urlname=PathGraph | title=Path Graph }}

[[Kategória:Fák (gráfelmélet)]]
[[Kategória:Gráfcsaládok]]
[[Kategória:Parametrikus gráfcsaládok]]