Лапы и минимальные по включению барьеры в графе — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 4 промежуточные версии 4 участников) | |||
Строка 2: | Строка 2: | ||
|id = claw | |id = claw | ||
|neat = 1 | |neat = 1 | ||
− | |definition = '''Лапой''' (англ. ''claw'') называется индуцированный подграф графа <tex>G</tex>, [[ Основные определения теории графов#isomorphic_graphs | изоморфный ]] [[ Основные определения теории графов#defBiparateGraph | двудольному ]] графу <tex>K_{1, 3}</tex>. | + | |definition = '''Лапой''' (англ. ''claw'') называется индуцированный подграф графа <tex>G</tex>, [[ Основные определения теории графов#isomorphic_graphs | изоморфный]] [[ Основные определения теории графов#defBiparateGraph | двудольному ]] графу <tex>K_{1, 3}</tex>. |
}} [[ Файл:Lapa.png|180px|thumb|right|Лапа ]] | }} [[ Файл:Lapa.png|180px|thumb|right|Лапа ]] | ||
Строка 23: | Строка 23: | ||
|id = minimum_barrier | |id = minimum_barrier | ||
|neat = 1 | |neat = 1 | ||
− | |definition = '''Минимальным по включению [[ Декомпозиция Эдмондса-Галлаи#barrier | барьером ]] '''(англ.'' | + | |definition = '''Минимальным по включению [[ Декомпозиция Эдмондса-Галлаи#barrier | барьером ]] '''(англ.''minimal barrier'') называется барьер, который перестанет быть барьером при исключении из него любой вершины. |
}} | }} | ||
Строка 73: | Строка 73: | ||
* [[ Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях ]] | * [[ Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях ]] | ||
* [[ Теорема Татта о существовании полного паросочетания ]] | * [[ Теорема Татта о существовании полного паросочетания ]] | ||
+ | * [[ Теорема Самнера — Лас Вергнаса ]] | ||
== Источники информации == | == Источники информации == |
Текущая версия на 19:32, 4 сентября 2022
Теорема: |
Пусть — минимальный по включению барьер графа , тогда каждая вершина — центр лапы в . |
Доказательство: |
Предположим, что компонентами связности графа .
Для любого из случаев выполнено:
|
Утверждение (D.P.Sumner, M.Las Vergnas, следствие из теоремы): |
Пусть совершенное паросочетание . — связный граф, не содержащий лапы, чётно. Тогда имеет |
Пусть |
См. также
- Декомпозиция Эдмондса-Галлаи
- Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
- Теорема Татта о существовании полного паросочетания
- Теорема Самнера — Лас Вергнаса
Источники информации
- Карпов Д. В. — Теория графов, стр 55
- Ловас Л., Пламмер М. — Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии, стр 165-166