толщина графа oor Hongaars

толщина графа

Vertalings in die woordeboek Russies - Hongaars

gráf vastagsága

мера планаризуемости графа

a síkgráfok minimális száma, melyekbe adott gráf élei felbonthatók

voorbeelde

Книжная толщина данного графа G не превышает 1 тогда и только тогда, когда G внешнепланарен.
Adott G gráf könyvvastagsága pontosan akkor nem nagyobb egynél, ha G egy külsíkgráf.

1-планарные графы имеют ограниченную книжную толщину, но некоторые 1-планарные графы, включая K2,2,2,2, имеют книжную толщину по меньшей мере четыре.
Az 1-síkbaágyazható gráfok könyvvastagsága korlátos, bár néhány 1-síkbarajzolható gráf, pl. a K2,2,2,2 könyvvastagsága legalább négy.

Любой стягивающий минор графа ограниченной книжной толщины является разреженным графом, у которого отношение рёбер к вершинам ограничено константной, которая зависит только от глубины минора и книжной толщины.
Egy korlátos könyvvastagságú gráf minden sekély minora ritka gráf, ahol az él/csúcs arányt korlátozó konstans kizárólag a minor mélységétől és a könyvvastagságtól függ.

Важными вехами в дальнейшем развитии книжного вложения является доказательство Михалисом Яннакакисом в конце 1980-х, что книжная толщина планарных графов не превосходит четырёх, и открытие в конце 1990-х тесной связи между книжным вложением и биоинформатикой.
A terület fejlődésének további mérföldköve volt az 1980-as évek végén Mihalis Yannakakis bizonyítása, miszerint a síkbarajzolható gráfok könyvvastagsága legfeljebb négy, valamint az 1990-es évek végén a bioinformatika és a könyvbe ágyazások közötti szoros kapcsolódások felfedezése.

Однако существуют графы с книжной толщиной три, не имеющие сепараторы сублинейного размера.
Léteznek azonban olyan, három könyvvastagságú gráfok, melyek nem rendelkeznek szublineáris méretű szeparátorral.

Толщина книжного вложения максимального планарного графа равна двум тогда и только тогда, когда гамильтонов путь существует.
Egy maximális síkbarajzolható gráfban a könyvvastagság pontosan akkor kettő, ha a gráfnak van Hamilton-köre.

По той же причине задача проверки, удовлетворяет ли граф с ограниченной книжной толщиной заданной формуле логики первого порядка, является разрешимой относительно фиксированного параметра.
Ugyanezen okból, a korlátos könyvvastagságú gráfokon annak vizsgálata, hogy a gráfra igaz-e egy elsőrendű nyelven megfogalmazott formula, rögzített paraméter mellett kezelhető.

Аналогично граф G имеет книжную толщину θ, если его можно нарисовать в полуплоскости с вершинами на границе полуплоскости и раскрасить рёбра в θ цветов без пересечений рёбер одного цвета.
Hasonlóan, a G gráf könyvvastagsága θ, ha lerajzolható egy félsíkba úgy, hogy csúcsai a félsík határán legyenek, élei pedig θ színnel legyenek színezve azonos színű élek találkozása nélkül.

Графы с древесной шириной k имеют книжную толщину, не превосходящую k + 1 и эта граница достигается для k > 2..
A k faszélességű gráfok könyvvastagsága legfeljebb k + 1 és ez a korlát k > 2-re éles.

Концепция толщины возникла в гипотезе Фрэнка Харари 1962 года: любой граф с 9 вершинами либо сам, либо его дополнение, является непланарным.
A vastagság fogalmát Frank Harary egy 1962-es sejtésében vezette be: eszerint bármely 9 csúcsú gráfra igaz, hogy vagy ő, vagy komplementere nem síkba rajzolható.

Однако даже графы с ограниченной степенью графа существенно более сильное требование ограничения роста, может иметь неограниченную книжную толщину.
De még a korlátos fokszámú gráfoknak – ami a korlátos expanziónál sokkal szigorúbb követelmény – is lehet korlátlan könyvvastagsága.

Несмотря на существование примеров, подобных вышеприведённому, Бланкеншип и Опоровски высказали гипотезу, что книжная толщина подразбиений не может быть существенно меньше, чем у исходного графа.
Az ilyen példák létezése ellenére, (Blankenship & Oporowski 1999) sejtése szerint a felosztás könyvvastagsága nem lehet sokkal kisebb az eredeti gráfénál.