| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén egy gráf könyvbe ágyazása (book embedding) a gráfok síkba ágyazásának általánosítása ugyanazon egyenes által határolt gyűjteményébe, vagyis „könyvbe” történő beágyazásra. Általában elvárt, hogy a gráf csúcsai ezen a határoló egyenesen (a könyv „gerincén”) feküdjenek, az élek pedig a saját félsíkjukon belül maradjanak. Egy gráf könyvvastagsága (book thickness) az a legkisebb félsík-szám, amivel a gráfnak még lehetséges könyvbe ágyazása. Nevezik a gráf „lapszámának” vagy „oldalszámának” (pagenumber), „halomszámának” (stacknumber) vagy „rögzített külvastagságának” (fixed outerthickness) is. A könyvbe ágyazás segítségével egyéb gráfinvariánsokat is definiáltak, köztük a lapszélességet vagy oldalszélességet (pagewidth) és a könyv-metszési számot (book crossing number). Egy n csúcsú gráf könyvvastagsága legfeljebb , teljes gráfok esetén pedig pontosan ennyi. Az egy könyvvastagságú gráfok a külsíkgráfok. A legfeljebb kettő könyvvastagságú gráfok a szubhamiltoni gráfok; a síkbarajzolható gráfok könyvvastagsága legfeljebb négy. Minden minorzárt gráfcsaládnak, különösen a korlátos faszélességgel vagy génusszal rendelkezőknek korlátos a könyvvastagsága. Egy konkrét gráf könyvvastagságának eldöntése , akár ismert a csúcsok sorrendje a könyv gerince mentén, akár nem. A könyvbe ágyazások tanulmányozásának egyik motivációja a -tervezés, melyben a beágyazás csúcsai egy elektronikus áramkör komponenseit, az élek pedig az azokat összekötő huzalozást jelképezik.A könyvbe ágyazás a is szerepet kap, ahol a gráfok standard lerajzolási módjai közül kettő, az és a is a könyvbe ágyazás segítségével szerkeszthetők meg. A a gyalogos és járművel történő közlekedés kiinduló és célpontjai, melyek közlekedési lámpáknál találkoznak és lépnek interakcióba egymással matematikailag egy gráf csúcsaiként modellezhetők, ahol az élek különböző kiindulási és célpontokat kötnek össze. Egy ilyen gráf könyvbe ágyazása segíthet olyan időbeosztás tervezésében, ahol a forgalom a lehető legkevesebb lámpaváltással halad át a kereszteződésen.A bioinformatika területén az RNS feltekeredett szerkezetével kapcsolatos problémákban az egylapos könyvbe ágyazások a klasszikus formáit, a kétlaposak pedig a testesítik meg.A könyvbe ágyazás további felhasználási területei az absztrakt algebra és a . Több nyitott kérdés van a könyvvastagsággal kapcsolatban. Nem ismert, hogy tetszőleges gráf könyvvastagságát korlátozza-e felosztásainak könyvvastagsága.Nem ismert egy gráf háromlapos könyvbe ágyazása létezésének a számítási bonyolultsága: nem tudjuk róla, hogy polinom időben megoldható lenne, sem azt, hogy NP-nehéz-e. És bár a síkbarajzolható gráf egyikének a könyvvastagsága sem haladja meg a négyet, eddig nem sikerült találni olyan síkbarajzolható gráfot, aminek a könyvvastagsága elérné a négyes értéket. (hu)
- A matematika, azon belül a gráfelmélet területén egy gráf könyvbe ágyazása (book embedding) a gráfok síkba ágyazásának általánosítása ugyanazon egyenes által határolt gyűjteményébe, vagyis „könyvbe” történő beágyazásra. Általában elvárt, hogy a gráf csúcsai ezen a határoló egyenesen (a könyv „gerincén”) feküdjenek, az élek pedig a saját félsíkjukon belül maradjanak. Egy gráf könyvvastagsága (book thickness) az a legkisebb félsík-szám, amivel a gráfnak még lehetséges könyvbe ágyazása. Nevezik a gráf „lapszámának” vagy „oldalszámának” (pagenumber), „halomszámának” (stacknumber) vagy „rögzített külvastagságának” (fixed outerthickness) is. A könyvbe ágyazás segítségével egyéb gráfinvariánsokat is definiáltak, köztük a lapszélességet vagy oldalszélességet (pagewidth) és a könyv-metszési számot (book crossing number). Egy n csúcsú gráf könyvvastagsága legfeljebb , teljes gráfok esetén pedig pontosan ennyi. Az egy könyvvastagságú gráfok a külsíkgráfok. A legfeljebb kettő könyvvastagságú gráfok a szubhamiltoni gráfok; a síkbarajzolható gráfok könyvvastagsága legfeljebb négy. Minden minorzárt gráfcsaládnak, különösen a korlátos faszélességgel vagy génusszal rendelkezőknek korlátos a könyvvastagsága. Egy konkrét gráf könyvvastagságának eldöntése , akár ismert a csúcsok sorrendje a könyv gerince mentén, akár nem. A könyvbe ágyazások tanulmányozásának egyik motivációja a -tervezés, melyben a beágyazás csúcsai egy elektronikus áramkör komponenseit, az élek pedig az azokat összekötő huzalozást jelképezik.A könyvbe ágyazás a is szerepet kap, ahol a gráfok standard lerajzolási módjai közül kettő, az és a is a könyvbe ágyazás segítségével szerkeszthetők meg. A a gyalogos és járművel történő közlekedés kiinduló és célpontjai, melyek közlekedési lámpáknál találkoznak és lépnek interakcióba egymással matematikailag egy gráf csúcsaiként modellezhetők, ahol az élek különböző kiindulási és célpontokat kötnek össze. Egy ilyen gráf könyvbe ágyazása segíthet olyan időbeosztás tervezésében, ahol a forgalom a lehető legkevesebb lámpaváltással halad át a kereszteződésen.A bioinformatika területén az RNS feltekeredett szerkezetével kapcsolatos problémákban az egylapos könyvbe ágyazások a klasszikus formáit, a kétlaposak pedig a testesítik meg.A könyvbe ágyazás további felhasználási területei az absztrakt algebra és a . Több nyitott kérdés van a könyvvastagsággal kapcsolatban. Nem ismert, hogy tetszőleges gráf könyvvastagságát korlátozza-e felosztásainak könyvvastagsága.Nem ismert egy gráf háromlapos könyvbe ágyazása létezésének a számítási bonyolultsága: nem tudjuk róla, hogy polinom időben megoldható lenne, sem azt, hogy NP-nehéz-e. És bár a síkbarajzolható gráf egyikének a könyvvastagsága sem haladja meg a négyet, eddig nem sikerült találni olyan síkbarajzolható gráfot, aminek a könyvvastagsága elérné a négyes értéket. (hu)
|
