Изменения

|id = pawclaw|neat = 1 |definition='''Лапой''' (англ. ''pawclaw'') называется индуцированный подграф графа <tex>G</tex>, [[ Основные определения теории графов#isomorphic_graphs | изоморфный ]] [[ Основные определения теории графов#defBiparateGraph | двудольному ]] графу <tex>K_{1,\;3}</tex>.}} [[Файл:Lapa.png|170px180px|thumb|leftright|Лапа]]  

|id = paw centerclaw_center|neat = 1 |definition='''Центр Центром лапы''' (англ. ''paw claw center'') {{---}} называется вершина [[ Основные определения теории графов#def_graph_degree_1 | степени 3 ]] три в лапе.

|neat = 1 |definition='''Минимальный Минимальным по включению [[Декомпозиция Эдмондса-Галлаи#barrier | барьербарьером ]] '''(англ.''minimum minimal barrier'') {{---}} называется барьер минимальной мощности, который перестанет быть барьером при исключении из него любой вершины.

|id=th1theorem_about_claw|statement=Пусть <tex>B</tex> {{---}} минимальный по включению барьер графа <tex>G</tex>, тогда каждая вершина <tex>B</tex> {{---}} центр лапы в <tex>G</tex>.|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>Для этого рассмотрим возможные всевозможные случаи количества компонент связности в графе <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>#:a) * Одна четнаякомпонента чётная, другая {{- --}} нечетная. Тогда <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex> . <br>#:b) * Обе компоненты чётные : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex> . <br>#:c) * Обе компоненты нечётные : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 </tex> . <br>#<tex>x</tex> смежна с одной компонентой связности графа <tex>G \setminus B</tex>.<br>#:a) Она * Эта компонента чётная : <tex>\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 </tex> . <br>#:b) Она * Эта компонента нечётная : <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>\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>\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>|B'| < |B| </tex>, а значит, <tex>B</tex> не является минимальным по включению барьером <tex>\Rightarrow</tex> противоречие условиютеоремы. <br>#Если <tex>\mathrm{odd}(G\setminus B') - |B'|\ > \mathrm{def}(G)</tex>, то <br>#:есть <tex>\mathrm{odd}(G\setminus B') - |B'|\ > \mathrm{def}(G) = \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>

|id=proposal1. |author=D.P.Sumner, M.Las Vergnas|about=следствие из теоремы|statement=Пусть <tex>G</tex> {{---}} связный граф, не содержащий лапы, <tex>v(G)</tex> чётно. Тогда <tex>G</tex> имеет [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#perfect_matching | совершенное паросочетание]].

<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

[[Категория: Алгоритмы и структуры данных]][[Категория:Задача о паросочетании]]