| dbo:abstract
|
- A matematika, azon belül a topologikus gráfelmélet, illetve a területén egy irányítatlan gráf láncmentes beágyazása (linkless embedding) a gráf az euklideszi térbe történő oly módon, hogy a gráf semelyik két köre nincs összeláncolva. Egy lapos beágyazás (flat embedding) olyan beágyazás, melynek minden köre olyan topologikus körlemez határán található, melynek belső része a gráftól diszjunkt. Egy láncmentesen beágyazható gráf (linklessly embeddable graph) olyan gráf, ami rendelkezik láncmentes vagy lapos beágyazással; ezek a gráfok a síkbarajzolható gráfok háromdimenziós analógiájának tekinthetők. Komplementer módon, egy eredendően láncolt gráf (intrinsically linked graph) olyan gráf, melynek nem létezik láncmentes beágyazása. A lapos beágyazások automatikusan láncmentesek, de ez fordítva nem igaz. A K6 teljes gráfnak, a Petersen-gráfnak és a többi öt tagjának nincs láncmentes beágyazása. Egy láncmentesen beágyazható gráf minden gráfminora is láncmentesen beágyazható, ami a láncmentesen beágyazható gráfokból elérhető gráfokra is igaz. A láncmentesen beágyazható gráfok tiltott minorai a , és közéjük tartoznak a síkbarajzolható gráfok és a csúcsgráfok is. Felismerésük és lapos beágyazásuk előállítása elvégezhető. (hu)
- A matematika, azon belül a topologikus gráfelmélet, illetve a területén egy irányítatlan gráf láncmentes beágyazása (linkless embedding) a gráf az euklideszi térbe történő oly módon, hogy a gráf semelyik két köre nincs összeláncolva. Egy lapos beágyazás (flat embedding) olyan beágyazás, melynek minden köre olyan topologikus körlemez határán található, melynek belső része a gráftól diszjunkt. Egy láncmentesen beágyazható gráf (linklessly embeddable graph) olyan gráf, ami rendelkezik láncmentes vagy lapos beágyazással; ezek a gráfok a síkbarajzolható gráfok háromdimenziós analógiájának tekinthetők. Komplementer módon, egy eredendően láncolt gráf (intrinsically linked graph) olyan gráf, melynek nem létezik láncmentes beágyazása. A lapos beágyazások automatikusan láncmentesek, de ez fordítva nem igaz. A K6 teljes gráfnak, a Petersen-gráfnak és a többi öt tagjának nincs láncmentes beágyazása. Egy láncmentesen beágyazható gráf minden gráfminora is láncmentesen beágyazható, ami a láncmentesen beágyazható gráfokból elérhető gráfokra is igaz. A láncmentesen beágyazható gráfok tiltott minorai a , és közéjük tartoznak a síkbarajzolható gráfok és a csúcsgráfok is. Felismerésük és lapos beágyazásuk előállítása elvégezhető. (hu)
|
