Лапы и минимальные по включению барьеры в графе

Определение:

Лапой (англ. paw) называется индуцированный подграф графа [math]G[/math], изоморфный двудольному графу [math]K_{1,\;3}[/math].

Лапа

Определение:

Центром лапы (англ. paw center) называется вершина степени три в лапе.

Определение:

Минимальным по включению барьером (англ.minimum barrier) называется барьер минимальной мощности.

Теорема:

Пусть [math]B[/math] — минимальный по включению барьер графа [math]G[/math], тогда каждая вершина [math]B[/math] — центр лапы в [math]G[/math].

Доказательство:

[math]\triangleright[/math]

Предположим, что [math]x\in B[/math] не является центром лапы. Тогда [math]x[/math] смежна не более чем с двумя компонентами связности графа [math]G \setminus B[/math]. Введём обозначение [math]B' = B\setminus x[/math]. Найдём соотношение между [math]\mathrm{odd}[/math][math](G\setminus B')\ [/math] и [math]\mathrm{odd}(G\setminus B)\ [/math]. Для этого рассмотрим всевозможные случаи количества компонент связности в графе [math]G \setminus B[/math], с которыми смежна [math]x[/math], и посмотрим на их четности (компоненты в [math]B[/math], с которыми смежна [math]x[/math], нас не интересуют). [math]x[/math] смежна с двумя компонентами связности графа [math]G \setminus B[/math]. [math]x[/math] смежна с двумя компонентами связности из [math]G \setminus B[/math] a) Одна компонента четная, другая — нечетная. Тогда [math]\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 [/math] b) Обе компоненты чётные: [math]\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 [/math] c) Обе компоненты нечётные: [math]\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 [/math] [math]x[/math] смежна с одной компонентой связности графа [math]G \setminus B[/math]. a) Эта компонента чётная: [math]\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 [/math] b) Эта компонента нечётная: [math]\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 [/math] [math]x[/math] не смежна ни с какой компонентой связности графа [math]G \setminus B[/math]: [math]\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ + 1 [/math] Рассмотрев случаи, видим, что для любого из них выполнено: [math]\mathrm{odd}(G\setminus B')\ \geqslant \mathrm{odd}(G\setminus B)\ - 1 [/math] [math]B[/math] — барьер [math] \Leftrightarrow \mathrm{odd}(G\setminus B) - |B| = \mathrm{def}(G) [/math] Тогда [math]\mathrm{odd}(G\setminus B')\ \geqslant |B| - 1 + \mathrm{def}(G)[/math] То есть [math]\mathrm{odd}(G\setminus B') - |B'|\ \geqslant \mathrm{def}(G)[/math] Тогда возможны два случая: Если выполняется равенство [math] \mathrm{odd}(G\setminus B') - |B'|\ = \mathrm{def}(G) [/math], то, по определению, [math]B'[/math] является барьером. Но [math]|B'| \lt |B| [/math], а значит, [math]B[/math] не является минимальным по включению барьером [math]\Rightarrow[/math] противоречие условию теоремы. Если [math]\mathrm{odd}(G\setminus B') - |B'|\ \gt \mathrm{def}(G)[/math], то [math]\mathrm{odd}(G\setminus B') - |B'|\ \gt \mathrm{def}(G) = \mathrm{odd}(G\setminus B) - |B|\[/math], что противоречит теореме Бержа. В обоих случаях мы пришли к противоречию, значит, наше предположение неверно и [math]\forall x\in B[/math] является центром лапы в [math]G[/math].

[math]\triangleleft[/math]

Утверждение (D.P.Sumner, M.Las Vergnas, следствие из теоремы):

Пусть [math]G[/math] — связный граф, не содержащий лапы, [math]v(G)[/math] чётно. Тогда [math]G[/math] имеет совершенное паросочетание.

[math]\triangleright[/math]

Пусть [math]B[/math] — минимальный по включению барьер графа [math]G[/math]. Тогда, по предыдущей теореме имеем [math]B = \varnothing [/math]. По условию [math]G[/math] — связный граф с чётным числом вершин [math]\Rightarrow [/math] [math]\mathrm{odd}(G\setminus \varnothing )\ = 0 [/math]. [math]B[/math] — барьер [math]\Leftrightarrow \mathrm{def}(G) = \mathrm{odd}(G\setminus \varnothing) - |\varnothing|\ = 0 [/math]. Значит, количество вершин, не покрытых максимальным паросочетанием, равно 0, то есть существует совершенное паросочетание.

[math]\triangleleft[/math]

См. также

• Декомпозиция Эдмондса-Галлаи
• Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
• Теорема Татта о существовании полного паросочетания

Источники информации

• Карпов Д. В. - Теория графов, стр 55