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

Материал из Викиконспекты
Перейти к: навигация, поиск
НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.


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




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




Определение:
Минимальным по включению барьером (англ.minimal 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], нас не интересуют).

  1. [math]x[/math] смежна с двумя компонентами связности графа [math]G \setminus B[/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')\ = \mathrm{odd}(G\setminus B)\ + 1 [/math].
    • Обе компоненты нечётные: [math]\mathrm{odd}(G\setminus B')\ = \mathrm{odd}(G\setminus B)\ - 1 [/math].
  2. [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')\ = \mathrm{odd}(G\setminus B)\ - 1 [/math].
  3. [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].
Тогда возможны два случая:

  1. Если выполняется равенство [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] противоречие условию теоремы.
  2. Если [math]\mathrm{odd}(G\setminus B') - |B'|\ \gt \mathrm{def}(G)[/math], то есть [math]\mathrm{odd}(G\setminus B') - |B'|\ \gt \mathrm{odd}(G\setminus B) - |B|\[/math].
    Тогда, по теореме Бержа, [math]\mathrm{def}(G) \ne \mathrm{odd}(G\setminus B) - |B|\[/math] [math]\Rightarrow[/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]. Значит, количество вершин, не покрытых максимальным паросочетанием , равно [math]0[/math], то есть в [math]G[/math] существует совершенное паросочетание.
[math]\triangleleft[/math]

См. также

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

  • Карпов Д. В. — Теория графов, стр 55
  • Ловас Л., Пламмер М. — Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии, стр 165-166
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Лапы_и_минимальные_по_включению_барьеры_в_графе&oldid=83243»