| dbo:abstract
|
- 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). (hu)
- 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). (hu)
|
