Лапы и минимальные по включению барьеры в графе — различия между версиями
Scuuter (обсуждение | вклад) (definition fixed?) |
|||
(не показано 13 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
− | |id = | + | |id = claw |
|neat = 1 | |neat = 1 | ||
− | |definition = '''Лапой''' (англ. '' | + | |definition = '''Лапой''' (англ. ''claw'') называется индуцированный подграф графа <tex>G</tex>, [[ Основные определения теории графов#isomorphic_graphs | изоморфный]] [[ Основные определения теории графов#defBiparateGraph | двудольному ]] графу <tex>K_{1, 3}</tex>. |
}} [[ Файл:Lapa.png|180px|thumb|right|Лапа ]] | }} [[ Файл:Lapa.png|180px|thumb|right|Лапа ]] | ||
Строка 11: | Строка 11: | ||
{{Определение | {{Определение | ||
− | |id = | + | |id = claw_center |
|neat = 1 | |neat = 1 | ||
− | |definition ='''Центром лапы''' (англ. '' | + | |definition ='''Центром лапы''' (англ. ''claw center'') называется вершина [[ Основные определения теории графов#def_graph_degree_1 | степени ]] три в лапе. |
}} | }} | ||
Строка 21: | Строка 21: | ||
{{Определение | {{Определение | ||
+ | |id = minimum_barrier | ||
|neat = 1 | |neat = 1 | ||
− | + | |definition = '''Минимальным по включению [[ Декомпозиция Эдмондса-Галлаи#barrier | барьером ]] '''(англ.''minimal barrier'') называется барьер, который перестанет быть барьером при исключении из него любой вершины. | |
− | |definition = '''Минимальным по включению [[ Декомпозиция Эдмондса-Галлаи#barrier | барьером ]] '''(англ.'' | ||
}} | }} | ||
− | + | ||
{{Теорема | {{Теорема | ||
− | |id = | + | |id = theorem_about_claw |
|statement = Пусть <tex>B</tex> {{---}} минимальный по включению барьер графа <tex>G</tex>, тогда каждая вершина <tex>B</tex> {{---}} центр лапы в <tex>G</tex>. | |statement = Пусть <tex>B</tex> {{---}} минимальный по включению барьер графа <tex>G</tex>, тогда каждая вершина <tex>B</tex> {{---}} центр лапы в <tex>G</tex>. | ||
− | |proof = Предположим, что <tex>x\in B</tex> не является центром лапы. Тогда <tex>x</tex> смежна не более чем с двумя компонентами связности графа <tex>G \setminus B</tex>. <br> | + | |proof = Предположим, что <tex>x\in B</tex> не является центром лапы. Тогда <tex>x</tex> смежна не более чем с двумя [[Отношение связности, компоненты связности#def2 | компонентами связности]] графа <tex>G \setminus B</tex>. <br> |
− | + | Пусть <tex>B' = B\setminus \{ x \}</tex>. <br> | |
Найдём соотношение между [[ Теорема Татта о существовании полного паросочетания#odd | <tex>\mathrm{odd}</tex> ]]<tex>(G\setminus B')\ </tex> и <tex>\mathrm{odd}(G\setminus B)\ </tex>. <br> | Найдём соотношение между [[ Теорема Татта о существовании полного паросочетания#odd | <tex>\mathrm{odd}</tex> ]]<tex>(G\setminus B')\ </tex> и <tex>\mathrm{odd}(G\setminus B)\ </tex>. <br> | ||
Для этого рассмотрим всевозможные случаи количества компонент связности в графе <tex>G \setminus B</tex>, с которыми смежна <tex>x</tex>, и посмотрим на их четности (компоненты в <tex>B</tex>, с которыми смежна <tex>x</tex>, нас не интересуют). <br> | Для этого рассмотрим всевозможные случаи количества компонент связности в графе <tex>G \setminus B</tex>, с которыми смежна <tex>x</tex>, и посмотрим на их четности (компоненты в <tex>B</tex>, с которыми смежна <tex>x</tex>, нас не интересуют). <br> | ||
# <tex>x</tex> смежна с двумя компонентами связности графа <tex>G \setminus B</tex>.[[ Файл:GraphsForLaps.png|300px|thumb|right|<tex>x</tex> смежна с двумя компонентами связности графа <tex>G \setminus B</tex> ]] <br> | # <tex>x</tex> смежна с двумя компонентами связности графа <tex>G \setminus B</tex>.[[ Файл:GraphsForLaps.png|300px|thumb|right|<tex>x</tex> смежна с двумя компонентами связности графа <tex>G \setminus B</tex> ]] <br> | ||
− | #: | + | #:* Одна компонента чётная, другая {{---}} нечетная. Тогда <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex>. <br> |
− | #: | + | #:* Обе компоненты чётные: <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex>. <br> |
− | #: | + | #:* Обе компоненты нечётные: <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex>. <br> |
#<tex>x</tex> смежна с одной компонентой связности графа <tex>G \setminus B</tex>. <br> | #<tex>x</tex> смежна с одной компонентой связности графа <tex>G \setminus B</tex>. <br> | ||
− | #: | + | #:* Эта компонента чётная: <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex>. <br> |
− | #: | + | #:* Эта компонента нечётная: <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex>. <br> |
− | # <tex>x</tex> не смежна ни с какой компонентой связности графа <tex>G | + | # <tex>x</tex> не смежна ни с какой компонентой связности графа <tex>G \setminus B</tex>. <br> |
− | + | #: <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex>. <br> | |
+ | Для любого из случаев выполнено: <tex>\mathrm{odd}(G\setminus B')\ \geqslant \mathrm{odd}(G\setminus B)\ - 1 </tex>. <br> | ||
<tex>B</tex> {{---}} барьер <tex> \Leftrightarrow \mathrm{odd}(G\setminus B) - |B| = \mathrm{def}(G) </tex>. <br> | <tex>B</tex> {{---}} барьер <tex> \Leftrightarrow \mathrm{odd}(G\setminus B) - |B| = \mathrm{def}(G) </tex>. <br> | ||
Тогда <tex> \mathrm{odd}(G\setminus B')\ \geqslant |B| - 1 + \mathrm{def}(G) </tex>. <br> | Тогда <tex> \mathrm{odd}(G\setminus B')\ \geqslant |B| - 1 + \mathrm{def}(G) </tex>. <br> | ||
− | То есть <tex> \mathrm{odd}(G\setminus B') - |B'|\ | + | То есть <tex> \mathrm{odd}(G\setminus B') - |B'|\ \geqslant \mathrm{def}(G) </tex>. <br> |
Тогда возможны два случая: | Тогда возможны два случая: | ||
− | # Если выполняется равенство <tex> \mathrm{odd}(G\setminus B') - |B'|\ = | + | # Если выполняется равенство <tex> \mathrm{odd}(G\setminus B') - |B'|\ = \mathrm{def}(G) </tex>, то, по определению, <tex>B'</tex> является барьером. <br> |
#: Но <tex>|B'| < |B| </tex>, а значит, <tex>B</tex> не является минимальным по включению барьером <tex>\Rightarrow</tex> противоречие условию теоремы. <br> | #: Но <tex>|B'| < |B| </tex>, а значит, <tex>B</tex> не является минимальным по включению барьером <tex>\Rightarrow</tex> противоречие условию теоремы. <br> | ||
− | # Если <tex>\mathrm{odd}(G\setminus B') - |B'|\ > \mathrm{def}(G)</tex>, то | + | # Если <tex>\mathrm{odd}(G\setminus B') - |B'|\ > \mathrm{def}(G)</tex>, то есть <tex>\mathrm{odd}(G\setminus B') - |B'|\ > \mathrm{odd}(G\setminus B) - |B|\</tex>. <br> |
− | + | #: Тогда, по [[ Декомпозиция Эдмондса-Галлаи#Th_Berge| теореме Бержа]], <tex>\mathrm{def}(G) \ne \mathrm{odd}(G\setminus B) - |B|\</tex> <tex>\Rightarrow</tex> противоречие. <br> | |
В обоих случаях мы пришли к противоречию, значит, наше предположение неверно и <tex>\forall x\in B</tex> является центром лапы в <tex>G</tex>. | В обоих случаях мы пришли к противоречию, значит, наше предположение неверно и <tex>\forall x\in B</tex> является центром лапы в <tex>G</tex>. | ||
}} | }} | ||
Строка 64: | Строка 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 | максимальным паросочетанием ]], равно 0, то есть в <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> существует совершенное паросочетание. |
}} | }} | ||
Строка 75: | Строка 76: | ||
== Источники информации == | == Источники информации == | ||
* Карпов Д. В. {{---}} Теория графов, стр 55 | * Карпов Д. В. {{---}} Теория графов, стр 55 | ||
+ | * Ловас Л., Пламмер М. {{---}} Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии, стр 165-166 | ||
[[ Категория: Алгоритмы и структуры данных ]] | [[ Категория: Алгоритмы и структуры данных ]] | ||
[[ Категория: Задача о паросочетании ]] | [[ Категория: Задача о паросочетании ]] |
Версия 17:27, 24 декабря 2017
Теорема: |
Пусть — минимальный по включению барьер графа , тогда каждая вершина — центр лапы в . |
Доказательство: |
Предположим, что компонентами связности графа .
Для любого из случаев выполнено:
|
Утверждение (D.P.Sumner, M.Las Vergnas, следствие из теоремы): |
Пусть совершенное паросочетание . — связный граф, не содержащий лапы, чётно. Тогда имеет |
Пусть |
См. также
- Декомпозиция Эдмондса-Галлаи
- Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
- Теорема Татта о существовании полного паросочетания
Источники информации
- Карпов Д. В. — Теория графов, стр 55
- Ловас Л., Пламмер М. — Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии, стр 165-166