Давайте рассмотрим еще одну забавную симпатичную задачу на применение
теоремы Холла.
Разумеется, у нас есть двудольный граф.
Так, дан двудольный граф.
Давайте считать, что он не имеет изолированных вершин,
то есть вершин степени 0.
Вершин, которые вообще ни с какими ребрами дело не имеют, в этом графе нет.
Двудольный граф без изолированных вершин,
без изолированных вершин.
И давайте считать, что каждая вершина из верхней доли,
если она соединена ребром с какой-то вершиной из нижней доли,
то она имеет степень не меньшую, чем степень вот этой нижней вершины.
Ну то есть если a из
A, b из B и (a,
b) — ребро,
то степень вершины a больше либо равняется степени вершины b.
Вот давайте так считать.
Ну я надеюсь, что все понимают уже сейчас, что A — это верхняя доля,
B — это нижняя доля.
Утверждается, что в этом случае существует паросочетание в этом графе,
которое покрывает все вершины доли A.
Значит, докажем или докажите, что существует
паросочетание, покрывающее
[БЕЗ_ЗВУКА] все вершины доли A,
верхней доли, нашей условной верхней доли.
Такое паросочетание.
Ну понятно, если мы желаем это доказать, значит, наверное,
нам стоит попробовать проверить условие Холла.
То самое, которое, собственно,
наличие такого паросочетания в теореме Холла как раз и гарантирует.
Значит, почему выполнено условие Холла?
Ну вот давайте это проверим.
Рассмотрим произвольное множество S,
находящееся внутри верхней доли.
Наша цель показать, что количество соседей в нашем графе, которые расположены,
естественно, внутри множества B, никак не меньше, чем мощность этого множества S.
Докажем, что мощность N(S),
то есть количество соседей, находящихся в B, не меньше, чем мощность S.
Введем следующее обозначение: вот пусть у нас
есть какое-то ребро e, пусть у нас есть какое-то ребро e.
Я немножко тороплюсь, на самом деле, прежде чем вводить это обозначение,
давайте сделаем вот что.
Давайте рассмотрим граф G',
который является индуцированным, порожденным подграфом исходного графа G,
и порожден он множествами S и N(S), ну что вполне естественно.
Вот у нас есть верхняя доля, в ней расположено наше произвольное множество S,
и есть множество соседей этого множества S, расположенных в нижней доле N(S).
И вот мы рассматриваем индуцированный подграф нашего исходного графа.
Ну можно это нарисовать, как обычно.
Не знаю, может быть, даже я и не буду сейчас это рисовать, не так важно.
И вот теперь, собственно, введем обещанное обозначение.
Это я, было, поторопился.
Вот у нас есть какое-то ребро этого графа.
Давайте для этого ребра (ребра, идущего из S в N(S),
понятное дело), давайте для этого ребра введем обозначение dS(e)
— это будет степень той вершины этого ребра, которая находится в множестве S.
Степень той вершины ребра e,
которая находится в множестве S.
Ну и аналогично dN(S) от e — это степень той вершины ребра e, которая,
наоборот, находится в нижней доле, то есть в множестве соседей множества S.
Смотрите, что замечательно: понятно,
что d(S) от e просто по определению равняется степени вот этой самой вершины.
Давайте степень той вершины v, которая находится в множестве S.
Степень v имеется в виду в исходном графе G.
В исходном графе G степень этой вершины в точности такая же,
как вот в этом нашем новом индуцированном подграфе.
Просто потому, что в исходном графе изначально из S только в N(S) ребра и шли.
А вот d с индексом N(S) от e эта
величина уже не превосходит степени в
исходном графе той вершины w, которая
была расположена в нижней доле и служила концом и служит концом нашего ребра e.
То есть dS(e) в точности равняется deg v, а вот dN(S) от (e) она может быть меньше.
Ну понятно: в нижней доле могут быть не только соседи вот этого множества,
но и соседи каких-то еще вершин.
Поэтому степени могли понизиться внутри вот этого вот графа,
по сравнению со степенями исходного графа.
Но для нас это только сейчас будет хорошо.
Сейчас вы это увидите.
Давайте сначала распишем величину мощность S.
Очень симпатично ее распишем, воспользовавшись тем, — внимание!
— что в нашем графе по определению нет изолированных вершин.
Я утверждаю, что мощность S можно посчитать следующим образом: мы суммируем
по все ребрам e (ну по всем ребрам, имеется в виду, вот этого графа G',
которые в нем присутствуют) величину 1 поделить на d с индексом S(e).
Вот это выглядит как-то очень неожиданно, на первый взгляд: как это, сумма каких-то
дробей вдруг окажется равной целому числу, которая есть мощность нашего множества S?
Но в действительности все очень просто.
Смотрите, что такое dS от (e) по определению?
Ну давайте я все-таки нарисую какую-то картинку.
Вот у нас есть ребро e из одной доли в другую.
Вот это ребро e.
Вот это вершина v, вот это вершина w.
Давайте подумаем, сколько раз величина dS от (e) встречается в этой сумме?
Величина dS от (e) — это, внимание!
— это степень вот этой вершины v.
То есть эта величина соответствует и нашему ребру e, и еще какому-то ребру e',
которое так же примыкает к вершине v и идет вниз, и еще какому-то ребру.
То есть вот это вот слагаемое, равное 1 поделить на dS от (e),
оно в нашем суммировании встречается столько раз, сколько есть ребер,
выходящих из вершины v, которая служит концом вот именно этого ребра e.
Ну а сколько выходит ребер?
Естественно, степень этой вершины.
То есть это слагаемое встречается в этой сумме столько раз,
какова степень вот этой конкретной вершины.
Ну в знаменателе-то эта самая степень и стоит.
То есть мы складываем вот эту дробь столько раз, чему равен ее знаменатель.
Естественно, мы получаем 1.
И теперь мы единицу, очевидно, получаем столько раз,
сколько у нас есть вершин вот в этой верхней дольке, которую мы обозначаем S.
Ну значит, получается в точности мощность S.
То есть это очень простая вещь, которая на первый взгляд казалось неожиданной.
С другой стороны, смотрите, мы знаем, что dS от (e),
dS от (e)...
так, это величина, которая...
Сейчас секундочку, я пойму.
Которая...
Так, dS от (e) — это степень вот этой вот вершины v.
Отлично!
У нас есть еще одно условие в нашей задаче,
которое меня чуть-чуть затормозило.
Извините, сейчас мы его как раз и используем.
Смотрите, если у нас есть какое-то ребро, то по условию нашей задачи степень верхней
вершины не меньше, чем степень нижней вершины.
Внимание, это в исходном графе.
Но в нашем графе G' неравенство продолжается в нужную сторону.
Степень исходной вершины больше либо равна вот этой вот степени.
То есть мы получаем, мы получаем, что
dS от (e) больше либо
равна d с индексом N от (S) от (e).
Понятно, да?
dS от (e) больше либо равняется dN от (S) от (e).
Потому что dS от (e) — это степень вершины v,
она больше либо равна по условию, чем степень вершины w, которая,
в свою очередь, больше либо равна, нежели dN от (S) от (e).
То есть мы получаем здесь знак неравенства,
поскольку все написано в знаменателе в другую сторону.
Это будет сумма по e 1 поделить на dN от (S) от (e).
А это ровно потому же рассуждению,
которое мы только что провели вот в этом месте, ровно с помощью такого же
рассуждения оказывается равным мощности множества N от (S).
Ну и мы доказали, что мощность множества N от (S) больше либо равна мощности S,
что нам и требовалось.
Все, условие Холла есть, и значит есть паросочетание,
которое покрывает все вершины верхней доли.