(a, b)-разложение

13.12.2020

(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)-разложимым
  • Любой планарный граф G {displaystyle G} с обхватом по меньшей мере g {displaystyle g} является
    • F(2, 0)-разложимым, если g ⩾ 4 {displaystyle ggeqslant 4}
    • (1, 4)- разложимым, если g ⩾ 5 {displaystyle ggeqslant 5} .
    • F(1, 2)- разложимым, если g ⩾ 6 {displaystyle ggeqslant 6} .
    • F(1, 1)- разложимым, если g ⩾ 8 {displaystyle ggeqslant 8} или если любой цикл G {displaystyle G} является либо треугольником, либо циклом с минимум 8 рёбрами, не принадлежащими треугольнику
    • (1, 5)- разложимым, если G {displaystyle G} не имеет 4-циклов
  • Любой внешнепланарный граф является F(2, 0)-разложимым и (1, 3)- разложимым


Имя:*
E-Mail:
Комментарий:
Информационный некоммерческий ресурс fccland.ru © 2020
При цитировании и использовании любых материалов ссылка на сайт обязательна