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

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
{{Русская Википедия/Панель перехода}}
{{Русская Википедия/Панель перехода}}
{{DISPLAYTITLE:(''a'', ''b'')-разложение}}
{{DISPLAYTITLE:(''a'', ''b'')-разложение}}
Строка 171: Строка 170:
[[Категория:Инварианты графов]]
[[Категория:Инварианты графов]]
[[Категория:Объекты теории графов]]
[[Категория:Объекты теории графов]]
{{#set:
Текст статьи={{DISPLAYTITLE:(''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)-разложимым<ref>{{sfn0|Gonçalves|2009}}, гипотезу выдвинули Балог, Кохол, Плугар и Ю ({{sfn0|Balogh, Kochol, Pluhár, Yu|2005}}). Результат Гонкалвеса является улучшением результата Нэш-Вилльямса ({{sfn0|Nash-Williams|1964}}), затем Балога, Кохола, Плугара и Ю ({{sfn0|Balogh, Kochol, Pluhár, Yu|2005}}).</ref>
* Любой [[планарный граф]] <math>G</math> с [[Обхват (теория графов)|обхватом]] по меньшей мере <math>g</math> является
** F(2, 0)-разложимым, если <math>g \geqslant 4</math><ref name=NW>Вытекает из результатов Нэш-Вилльямса ({{sfn0|Nash-Williams|1964}}).</ref>
** (1, 4)- разложимым, если <math>g \geqslant 5</math>{{sfn|He, Hou, Lih, Shao и др.|2002}}.
** F(1, 2)- разложимым, если <math>g \geqslant 6</math><ref>Вытекает из результатов Монтасье, Оссоны де Мендез, Андре и Зу ({{sfn0|Montassier, Ossona de Mendez, André, Zhu|2012}}), результат которого улучшили Хи, Ху, Ли, Шао и др. ({{sfn0|He, Hou, Lih, Shao и др.|2002}}), затем Кляйтман ({{sfn0|Kleitman|2008}}).</ref>.
** F(1, 1)- разложимым, если <math>g \geqslant 8</math><ref>Доказали Ванг и Занг ({{sfn0|Wang, Zhang|2011}}) и (независимо) вытекает из результатов Монтасье, Оссоны де Мендез, Андре и Зу ({{sfn0|Montassier, Ossona de Mendez, André, Zhu|2012}}), которые улучшили Хи, Ху, Ли, Шао и др. ({{sfn0|He, Hou, Lih, Shao и др.|2002}}) для обхвата 11, а затем Басса, Бёрнс, Кэмпбелл и др. ({{sfn0|Bassa, Burns, Campbell и др.|2010}}) для обхвата 10 и Бородин, Косточка, Шейх и Ю ({{sfn0|Borodin, Kostochka, Sheikh, Yu (a)|2008}}) для обхвата 9.</ref> или если любой цикл <math>G</math> является либо треугольником, либо циклом с минимум 8 рёбрами, не принадлежащими треугольнику<ref>({{sfn0|Borodin, Ivanova, Kostochka, Sheikh (b)|2009}}), хотя это явно в статье и не утверждается.</ref>
** (1, 5)- разложимым, если <math>G</math> не имеет 4-циклов<ref>Бородин, Иванова, Косточка, Шейх ({{sfn0|Borodin, Ivanova, Kostochka, Sheikh (a)|2009}}), которые улучшили результат Хи, Ху, Ли, Шао и др. ({{sfn0|He, Hou, Lih, Shao и др.|2002}}), а также предыдущий результат ({{sfn0|Borodin, Kostochka, Sheikh, Yu (b)|2008}}).</ref>
* Любой [[внешнепланарный граф]] является F(2, 0)-разложимым<ref name=NW /> и (1, 3)- разложимым<ref>Доказали Гуан и Зу без явного указания результата ({{sfn0|Guan, Zhu|1999}}).</ref>
== Примечания ==
{{примечания}}
== Литература ==
* {{статья
|автор=Crispin St. John Alvah Nash-Williams
|ref=Nash-Williams
|заглавие=Decomposition of finite graphs into forests
|издание=[[Journal of the London Mathematical Society]]
|том=39
|выпуск=1
|год=1964
|страницы=12
|doi=10.1112/jlms/s1-39.1.12
|mr=0161333
}}
* {{статья
|автор=Guan D. J., Zhu X.
|ref=Guan, Zhu
|год = 1999
|заглавие=Game chromatic number of outerplanar graphs
|ссылка= http://onlinelibrary.wiley.com/doi/10.1002/%28SICI%291097-0118%28199901%2930:1%3C67::AID-JGT7%3E3.0.CO;2-M/abstract
|издание=Journal of Graph Theory
|том=30
|выпуск =1
|страницы=67–70
|doi=10.1002/(sici)1097-0118(199901)30:1<67::aid-jgt7>3.0.co;2-m
}}
* {{статья
|автор= Wenjie He, Xiaoling Hou, Ko-Wei Lih, Jiating Shao, Weifan Wang, Xuding Zhu
|ref =He, Hou, Lih, Shao и др.
|год=2002
|заглавие=Edge-partitions of planar graphs and their game coloring numbers
|ссылка=http://onlinelibrary.wiley.com/doi/10.1002/jgt.10069/abstract
|издание=Journal of Graph Theory
|том=41
|страницы = 307–311
|doi = 10.1002/jgt.10069
}}
* {{статья
|ref =Balogh, Kochol, Pluhár, Yu
|автор= József Balogh, Martin Kochol, András Pluhár, Xingxing Yu
|год=2005
|заглавие=Covering planar graphs with forests
|ссылка= http://www.sciencedirect.com/science/article/pii/S0095895604001273
|издание=Journal of Combinatorial Theory, Series B
|том=94
|выпуск=1
|страницы= 147–158
|doi=10.1016/j.ejc.2007.06.020
}}
* {{статья
|ref =Borodin, Kostochka, Sheikh, Yu (a)
|автор = Oleg V. Borodin, Alexandr V. Kostochka, Naeem N. Sheikh, Gexin Yu
|год=2008
|заглавие=Decomposing a planar graph with girth 9 into a forest and a matching
|ссылка=http://www.sciencedirect.com/science/article/pii/S0195669807001151
|издание=European Journal of Combinatorics
|том=29
|выпуск=5
|страницы=1235–1241
|doi= 10.1016/j.ejc.2007.06.020
}}
* {{статья
|ref =Borodin, Kostochka, Sheikh, Yu (b)
|автор = Oleg V. Borodin, Alexandr V. Kostochka, Naeem N. Sheikh, Gexin Yu
|год=2008
|заглавие=''M''-Degrees of Quadrangle-Free Planar Graphs
|ссылка=http://www.math.uiuc.edu/~kostochk/docs/2012/jgt09bsy.pdf
|издание=Journal of Graph Theory
|том=60
|выпуск=1
|страницы=80–85
|doi= 10.1002/jgt.20346
}}
* {{статья
|автор = Daniel J. Kleitman
|ref = Kleitman
|год=2008
|заглавие=Partitioning the Edges of a Girth 6 Planar Graph into those of a Forest and those of a Set of Disjoint Paths and Cycles
|издание=Manuscript
}}
* {{статья
|автор = Daniel Gonçalves
|ref = Gonçalves
|год=2009
|заглавие=Covering planar graphs with forests, one having bounded maximum degree
|ссылка=http://www.sciencedirect.com/science/article/pii/S0095895608000774
|издание=Journal of Combinatorial Theory, Series B
|том=99
|выпуск=2
|страницы=314–322
|doi= 10.1016/j.jctb.2008.07.004
}}
* {{статья
|ref=Borodin, Ivanova, Kostochka, Sheikh (a)
|автор =Oleg V. Borodin, Anna O. Ivanova, Alexandr V. Kostochka, Naeem N. Sheikh
|год=2009
|заглавие=Decompositions of Quadrangle-Free Planar Graphs
|ссылка=http://www.math.uiuc.edu/~kostochk/docs/2012/dmgt09bis.pdf
|издание=Discussiones Mathematicae Graph Theory
|том=29
|страницы=87–99
|doi=10.7151/dmgt.1434
}}
* {{статья
|ref=Borodin, Ivanova, Kostochka, Sheikh (b)
|автор =Oleg V. Borodin, Anna O. Ivanova, Alexandr V. Kostochka, Naeem N. Sheikh
|год=2009
|заглавие=Planar graphs decomposable into a forest and a matching
|ссылка=http://www.sciencedirect.com/science/article/pii/S0012365X07010771
|издание=Discrete Mathematics
|том=309
|выпуск=1
|страницы=277–279
| doi=10.1016/j.disc.2007.12.104
}}
* {{статья
|ref =Bassa, Burns, Campbell и др.
|автор = Bassa A., Burns J., Campbell J., Deshpande A., Farley J., Halsey L., Ho S.-Y., Kleitman, D., Michalakis S., Persson P.-O., Pylyavskyy P., Rademacher L., Riehl, A., Rios M., Samuel J., Tenner B.E., Vijayasarathy A., Zhao L.
|год=2010
|заглавие=Partitioning a Planar Graph of Girth 10 into a Forest and a Matching
|ссылка=http://onlinelibrary.wiley.com/doi/10.1111/j.1467-9590.2009.00468.x/abstract
|издание=European Journal of Combinatorics
|том=124
|выпуск=3
|страницы=213–228
| doi          = 10.1111/j.1467-9590.2009.00468.x
}}
* {{статья
|ref =Wang, Zhang
|автор = Yingqian Wang, Qijun Zhang
|год=2011
|заглавие=Decomposing a planar graph with girth at least 8 into a forest and a matching
|ссылка=http://www.sciencedirect.com/science/article/pii/S0012365X1100029X
|издание=Discrete Mathematics
|том=311
|выпуск=10—11
|страницы=844–849
|doi= 10.1016/j.disc.2011.01.019
}}
* {{статья
|автор = Mickaël Montassier, Patrice Ossona de Mendez, Raspaud André, Xuding Zhu
|ref = Montassier, Ossona de Mendez, André, Zhu
|год = 2012
|заглавие = Decomposing a graph into forests
|ссылка = http://www.sciencedirect.com/science/article/pii/S0095895611000438
|издание = Journal of Combinatorial Theory, Series B
|том = 102
|выпуск = 1
|страницы = 38–52
|doi = 10.1016/j.jctb.2011.04.001
}}
[[Категория:Инварианты графов]]
[[Категория:Объекты теории графов]]
}}
{{Навигационная таблица/Портал/Русская Википедия}}
{{Навигационная таблица/Портал/Русская Википедия}}
[[Категория:Русская Википедия]]
[[Категория:Русская Википедия]]

Текущая версия от 23:10, 10 июля 2023

(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