Лапы и минимальные по включению барьеры в графе — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 54 промежуточные версии 6 участников) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
− | |definition='''Лапой''' называется индуцированный подграф графа <tex>G</tex>, изоморфный двудольному графу <tex>K_{1, | + | |id = claw |
− | }} | + | |neat = 1 |
+ | |definition = '''Лапой''' (англ. ''claw'') называется индуцированный подграф графа <tex>G</tex>, [[ Основные определения теории графов#isomorphic_graphs | изоморфный]] [[ Основные определения теории графов#defBiparateGraph | двудольному ]] графу <tex>K_{1, 3}</tex>. | ||
+ | }} [[ Файл:Lapa.png|180px|thumb|right|Лапа ]] | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
{{Определение | {{Определение | ||
− | |definition=''' | + | |id = claw_center |
+ | |neat = 1 | ||
+ | |definition ='''Центром лапы''' (англ. ''claw center'') называется вершина [[ Основные определения теории графов#def_graph_degree_1 | степени ]] три в лапе. | ||
}} | }} | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
{{Определение | {{Определение | ||
− | |definition=''' | + | |id = minimum_barrier |
+ | |neat = 1 | ||
+ | |definition = '''Минимальным по включению [[ Декомпозиция Эдмондса-Галлаи#barrier | барьером ]] '''(англ.''minimal 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= | + | |proof = Предположим, что <tex>x\in B</tex> не является центром лапы. Тогда <tex>x</tex> смежна не более чем с двумя [[Отношение связности, компоненты связности#def2 | компонентами связности]] графа <tex>G \setminus B</tex>. <br> |
− | + | Пусть <tex>B' = B\setminus \{ x \}</tex>. <br> | |
− | Найдём соотношение между <tex>\mathrm{odd}(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>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 \setminus B</tex> : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </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>B</tex> {{---}} барьер <tex> \Leftrightarrow \mathrm{odd}(G\setminus B) - |B| = \mathrm{def}(G) </tex> <br> | + | Для любого из случаев выполнено: <tex>\mathrm{odd}(G\setminus B')\ \geqslant \mathrm{odd}(G\setminus B)\ - 1 </tex>. <br> |
− | Тогда <tex>\mathrm{odd}(G\setminus B')\ \geqslant |B| - 1 + \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') - |B'|\ \geqslant \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'|\ \geqslant \mathrm{def}(G) </tex>. <br> | ||
Тогда возможны два случая: | Тогда возможны два случая: | ||
− | #Если выполняется равенство <tex>\mathrm{odd}(G\setminus B') - |B'|\ = \mathrm{def}(G)</tex>, то, по определению <tex>B'</tex> является барьером. <br> | + | # Если выполняется равенство <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>. | ||
}} | }} | ||
+ | |||
{{Утверждение | {{Утверждение | ||
− | |id=proposal1 | + | |id = proposal1 |
− | |author=D.P.Sumner | + | |author = D.P.Sumner, M.Las Vergnas |
− | |about=следствие из теоремы | + | |about = следствие из теоремы |
− | |statement=Пусть <tex>G</tex> {{---}} | + | |statement = Пусть <tex>G</tex> {{---}} связный граф, не содержащий лапы, <tex>v(G)</tex> чётно. Тогда <tex>G</tex> имеет [[ Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#perfect_matching | совершенное паросочетание ]]. |
|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{odd}(G\setminus \varnothing) - |\varnothing|\ | + | <tex>B</tex> {{---}} барьер и он пуст <tex>\Leftrightarrow \mathrm{def}(G) = \mathrm{odd}(G\setminus \varnothing) - |\varnothing|\ = 0 </tex>. Значит, количество вершин, не покрытых [[ Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#maximal_matching | максимальным паросочетанием ]], равно <tex>0</tex>, то есть в <tex>G</tex> существует совершенное паросочетание. |
}} | }} | ||
==См. также== | ==См. также== | ||
− | * [[ | + | * [[ Декомпозиция Эдмондса-Галлаи ]] |
− | + | * [[ Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях ]] | |
− | * [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]] | + | * [[ Теорема Татта о существовании полного паросочетания ]] |
+ | * [[ Теорема Самнера — Лас Вергнаса ]] | ||
== Источники информации == | == Источники информации == | ||
− | * Карпов В. | + | * Карпов Д. В. {{---}} Теория графов, стр 55 |
+ | * Ловас Л., Пламмер М. {{---}} Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии, стр 165-166 | ||
− | [[Категория: Алгоритмы и структуры данных]] | + | [[ Категория: Алгоритмы и структуры данных ]] |
+ | [[ Категория: Задача о паросочетании ]] |
Текущая версия на 19:32, 4 сентября 2022
Теорема: |
Пусть — минимальный по включению барьер графа , тогда каждая вершина — центр лапы в . |
Доказательство: |
Предположим, что компонентами связности графа .
Для любого из случаев выполнено:
|
Утверждение (D.P.Sumner, M.Las Vergnas, следствие из теоремы): |
Пусть совершенное паросочетание . — связный граф, не содержащий лапы, чётно. Тогда имеет |
Пусть |
См. также
- Декомпозиция Эдмондса-Галлаи
- Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
- Теорема Татта о существовании полного паросочетания
- Теорема Самнера — Лас Вергнаса
Источники информации
- Карпов Д. В. — Теория графов, стр 55
- Ловас Л., Пламмер М. — Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии, стр 165-166