Лапы и минимальные по включению барьеры в графе — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 5 промежуточных версий 5 участников) | |||
Строка 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'') называется барьер, который перестанет быть барьером при исключении из него любой вершины. |
}} | }} | ||
Строка 65: | Строка 65: | ||
|proof= Пусть <tex>B</tex> {{---}} минимальный по включению барьер графа <tex>G</tex>. Тогда, по предыдущей теореме имеем <tex>B = \varnothing </tex>.<br> | |proof= Пусть <tex>B</tex> {{---}} минимальный по включению барьер графа <tex>G</tex>. Тогда, по предыдущей теореме имеем <tex>B = \varnothing </tex>.<br> | ||
По условию <tex>G</tex> {{---}} связный граф с чётным числом вершин <tex>\Rightarrow </tex> <tex>\mathrm{odd}(G\setminus \varnothing )\ = 0 </tex>. <br> | По условию <tex>G</tex> {{---}} связный граф с чётным числом вершин <tex>\Rightarrow </tex> <tex>\mathrm{odd}(G\setminus \varnothing )\ = 0 </tex>. <br> | ||
− | <tex>B</tex> {{---}} барьер <tex>\Leftrightarrow \mathrm{def}(G) = \mathrm{odd}(G\setminus \varnothing) - |\varnothing|\ = 0 </tex>. Значит, количество вершин, не покрытых [[ Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#maximal_matching | максимальным паросочетанием ]], равно <tex>0</tex>, то есть в <tex>G</tex> существует совершенное паросочетание. | + | <tex>B</tex> {{---}} барьер и он пуст <tex>\Leftrightarrow \mathrm{def}(G) = \mathrm{odd}(G\setminus \varnothing) - |\varnothing|\ = 0 </tex>. Значит, количество вершин, не покрытых [[ Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#maximal_matching | максимальным паросочетанием ]], равно <tex>0</tex>, то есть в <tex>G</tex> существует совершенное паросочетание. |
}} | }} | ||
Строка 73: | Строка 73: | ||
* [[ Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях ]] | * [[ Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях ]] | ||
* [[ Теорема Татта о существовании полного паросочетания ]] | * [[ Теорема Татта о существовании полного паросочетания ]] | ||
+ | * [[ Теорема Самнера — Лас Вергнаса ]] | ||
== Источники информации == | == Источники информации == |
Текущая версия на 19:32, 4 сентября 2022
Теорема: |
Пусть — минимальный по включению барьер графа , тогда каждая вершина — центр лапы в . |
Доказательство: |
Предположим, что компонентами связности графа .
Для любого из случаев выполнено:
|
Утверждение (D.P.Sumner, M.Las Vergnas, следствие из теоремы): |
Пусть совершенное паросочетание . — связный граф, не содержащий лапы, чётно. Тогда имеет |
Пусть |
См. также
- Декомпозиция Эдмондса-Галлаи
- Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
- Теорема Татта о существовании полного паросочетания
- Теорема Самнера — Лас Вергнаса
Источники информации
- Карпов Д. В. — Теория графов, стр 55
- Ловас Л., Пламмер М. — Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии, стр 165-166