| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén a Halin-gráfok olyan síkbarajzolható gráfok, melyek egy fa leveleinek körré történő összehúzásával állíthatók elő.A fának legalább négy csúcsból kell állnia, a csúcsok egyikének sem lehet pontosan két szomszédja; le kell rajzolni az euklideszi síkba úgy, hogy élei ne messék egymást (ezt nevezik síkba ágyazásnak), a kör pedig ennek a beágyazásnak a leveleit köti össze az óramutató járása szerint. Így a kör alkotja a Halin-gráf külső tartományát, benne egy fával. A Halin-gráfok német matematikusról kapták nevüket, aki 1971-ben tanulmányozta őket, bár a 3-reguláris Halin-gráfokat – melyekben minden csúcs fokszáma pontosan három – már egy évszázaddal korábban vizsgálta. Ezek poliédergráfok, tehát minden Halin-gráf előáll egy konvex poliéder csúcsaiból és éleiből; ezeket a poliédereket „tető nélküli poliédereknek” (roofless polyhedra) vagy „kupoláknak” (domes) nevezik. Minden Halin-gráfban található az összes csúcson átmenő, ún. Hamilton-kör, ahogy a csúcsok számáig bezárólag szinte az összes lehetséges hosszúságú kör is. A Halin-gráfok felismerhetők. Mivel faszélességük alacsony, az általános gráfokon nehéznek számító feladatok közül többet – például a Hamilton-körök keresését – gyorsan meg lehet oldani rajtuk. (hu)
- A matematika, azon belül a gráfelmélet területén a Halin-gráfok olyan síkbarajzolható gráfok, melyek egy fa leveleinek körré történő összehúzásával állíthatók elő.A fának legalább négy csúcsból kell állnia, a csúcsok egyikének sem lehet pontosan két szomszédja; le kell rajzolni az euklideszi síkba úgy, hogy élei ne messék egymást (ezt nevezik síkba ágyazásnak), a kör pedig ennek a beágyazásnak a leveleit köti össze az óramutató járása szerint. Így a kör alkotja a Halin-gráf külső tartományát, benne egy fával. A Halin-gráfok német matematikusról kapták nevüket, aki 1971-ben tanulmányozta őket, bár a 3-reguláris Halin-gráfokat – melyekben minden csúcs fokszáma pontosan három – már egy évszázaddal korábban vizsgálta. Ezek poliédergráfok, tehát minden Halin-gráf előáll egy konvex poliéder csúcsaiból és éleiből; ezeket a poliédereket „tető nélküli poliédereknek” (roofless polyhedra) vagy „kupoláknak” (domes) nevezik. Minden Halin-gráfban található az összes csúcson átmenő, ún. Hamilton-kör, ahogy a csúcsok számáig bezárólag szinte az összes lehetséges hosszúságú kör is. A Halin-gráfok felismerhetők. Mivel faszélességük alacsony, az általános gráfokon nehéznek számító feladatok közül többet – például a Hamilton-körök keresését – gyorsan meg lehet oldani rajtuk. (hu)
|
