Русская Википедия:(a, b)-разложение

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

(a, b)-разложение неориентированного графа — это разбиение рёбер на a + 1 множеств, каждое из которых представляет лес, за исключением одного, имеющего степень, не превосходящую b. Если этот граф тоже является лесом, такое разложение называется F(a, b)-разложением.

Граф с древесностью a является (a, 0)-разложимым. Любое (a, 0)-разложение или (a, 1)-разложение является a F(a, 0)-разложением или F(a, 1)-разложением соответственно.

Классы графов

  • Любой планарный граф является F(2, 4)-разложимым[1]
  • Любой планарный граф <math>G</math> с обхватом по меньшей мере <math>g</math> является
    • F(2, 0)-разложимым, если <math>g \geqslant 4</math>[2]
    • (1, 4)- разложимым, если <math>g \geqslant 5</math>Шаблон:Sfn.
    • F(1, 2)- разложимым, если <math>g \geqslant 6</math>[3].
    • F(1, 1)- разложимым, если <math>g \geqslant 8</math>[4] или если любой цикл <math>G</math> является либо треугольником, либо циклом с минимум 8 рёбрами, не принадлежащими треугольнику[5]
    • (1, 5)- разложимым, если <math>G</math> не имеет 4-циклов[6]
  • Любой внешнепланарный граф является F(2, 0)-разложимым[2] и (1, 3)- разложимым[7]

Примечания

Шаблон:Примечания

Литература

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Sfn0, гипотезу выдвинули Балог, Кохол, Плугар и Ю (Шаблон:Sfn0). Результат Гонкалвеса является улучшением результата Нэш-Вилльямса (Шаблон:Sfn0), затем Балога, Кохола, Плугара и Ю (Шаблон:Sfn0).
  2. ↑ 2,0 2,1 Вытекает из результатов Нэш-Вилльямса (Шаблон:Sfn0).
  3. ↑ Вытекает из результатов Монтасье, Оссоны де Мендез, Андре и Зу (Шаблон:Sfn0), результат которого улучшили Хи, Ху, Ли, Шао и др. (Шаблон:Sfn0), затем Кляйтман (Шаблон:Sfn0).
  4. ↑ Доказали Ванг и Занг (Шаблон:Sfn0) и (независимо) вытекает из результатов Монтасье, Оссоны де Мендез, Андре и Зу (Шаблон:Sfn0), которые улучшили Хи, Ху, Ли, Шао и др. (Шаблон:Sfn0) для обхвата 11, а затем Басса, Бёрнс, Кэмпбелл и др. (Шаблон:Sfn0) для обхвата 10 и Бородин, Косточка, Шейх и Ю (Шаблон:Sfn0) для обхвата 9.
  5. ↑ (Шаблон:Sfn0), хотя это явно в статье и не утверждается.
  6. ↑ Бородин, Иванова, Косточка, Шейх (Шаблон:Sfn0), которые улучшили результат Хи, Ху, Ли, Шао и др. (Шаблон:Sfn0), а также предыдущий результат (Шаблон:Sfn0).
  7. ↑ Доказали Гуан и Зу без явного указания результата (Шаблон:Sfn0).
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:(a,_b)-разложение&oldid=8524598