This HTML5 document contains 26 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
wikipedia-huhttp://hu.wikipedia.org/wiki/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-huhttp://hu.dbpedia.org/resource/
prop-huhttp://hu.dbpedia.org/property/
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n4http://hu.dbpedia.org/resource/Sablon:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n11http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Könyvbe_ágyazás
rdfs:label
Könyvbe ágyazás
dct:subject
n11:Topologikus_gráfelmélet
dbo:wikiPageID
1603904
dbo:wikiPageRevisionID
23135957
prop-hu:wikiPageUsesTemplate
n4:Megoldatlan n4:Mvar n4:Harvtxt n4:Fordítás n4:Math n4:Reflist n4:Harvs
prop-hu:authorlink
Donald Knuth
prop-hu:first
Donald
prop-hu:last
Knuth
prop-hu:year
1968
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.
prov:wasDerivedFrom
wikipedia-hu:Könyvbe_ágyazás?oldid=23135957&ns=0
dbo:wikiPageLength
65174
foaf:isPrimaryTopicOf
wikipedia-hu:Könyvbe_ágyazás
Subject Item
dbpedia-hu:Sorba_ágyazás
dbo:wikiPageRedirects
dbpedia-hu:Könyvbe_ágyazás
Subject Item
dbpedia-hu:Sorba_állítási_szám
dbo:wikiPageRedirects
dbpedia-hu:Könyvbe_ágyazás
Subject Item
dbpedia-hu:Könyvbe_rajzolás
dbo:wikiPageRedirects
dbpedia-hu:Könyvbe_ágyazás
Subject Item
dbpedia-hu:Könyvbeágyazás
dbo:wikiPageRedirects
dbpedia-hu:Könyvbe_ágyazás
Subject Item
dbpedia-hu:Könyvmetszési_szám
dbo:wikiPageRedirects
dbpedia-hu:Könyvbe_ágyazás
Subject Item
dbpedia-hu:Könyvvastagság
dbo:wikiPageRedirects
dbpedia-hu:Könyvbe_ágyazás
Subject Item
wikipedia-hu:Könyvbe_ágyazás
foaf:primaryTopic
dbpedia-hu:Könyvbe_ágyazás