299
правок
Изменения
→Случай двудольного графа
}}
===Случай двудольного графа===
Здесь мы будем рассматривать двудольный граф G, как
G={V1{G),V2{G),E(G))t
где Vi(G) и V2{G) — разбиение множества Есршин V[G) на дте дели, а рёбра соединяют вершины из разных долей
Определение 10.7. Пусть H,G — двудольные графы. Инъективное стображение ip : V(H) —> V{G) назовём погружением, если онс удовлетворяет дтум ус л с вням.
1° рШН)) с V1(G), ip(V2(H)) с V2(G) 2° (p(u)tp(v) е E(G) тогда и только тогда когда uv е Е(Н) В этсм случае будем гсЕсрить, что двудольный граф Н погружён в ДЕудольный граф G и использовать обозначение <р(Н) — G(ip(V(H)))
Замечание 1С.4. Отметим, чте если сушестЕует погружение у> двудольного графа Н в двудольный граф G тс индуцированный подграф р(Н) графа G изоморфен Н
Напомним, чте для множества X через Хк мы обозначаем мнежество Есех fc-элементных подмножеств множества X.
Определение 10.8. Назсьём особым двудольный граф вида
Я = (V, Vk, Е(Н)), где Е(Н) = {xY\x Е V, Y Е Vk, х Е Y}.
Лемма 10.2. Любой двудольный граф может быть погружен в особый двудольный граф.
Доказательство. Рассмотрим произвольный двудольный граф Р пусть
Vl(P) = {°ь • ■ ■ ап}: ЩР) = {h, ■ ■ ■ Ьт}. положим
V = {ад,. . . , Хп, ?/!,..., уп, Z\, ..., zm}.
Построим погружение Р в ссобый двудольный граф Н — (V, Vn+1,E)
Изначально полежим (р(щ) — Xi Попробуем псстрсить такое множество Yj Е Vn+1. чте ip(bj) = Yj. По определению погружения и множества Е{Н). делжве выполняться условие
У^{хи...,хп} = ч>Ц1р{Ь5)). [ИР]
Условие (1С.5) оставляет незаполненными п+1 — dp(bj) > 1 элементов множества Yj (единственное ограничение эти элементы не могут быть вершинами ад,... ,хп). Поместим е Yj элемент-индекс Zj (чтобы Yj ^ Yi ПРН 3 Ф Р, и дополним ироизЕСльнс элементами из yi,...,yn нтсбы в множестве Yj былс рсЕнс п+1 элементов. □
Лемма 1С.З. Для любого аоуаолъного графа Н сугьестеует такой двудольный граф G, что для любой раскраски рёбер G в два цвета обязательно существует погруженьс ip графа Н в граф G в котором все рёбра р(Н) одноцветны
Замечание 10.5. Разумеется, указанный е уел сени леммы 1С.З граф G будет рамсееЕСким графем для Я. Утверждение леммы белее сильное: мы дополнительно требуем, чтобы ьсе вершины одной дели Я можно было погрузить в одну долю графа G.
Доказательство. Венду леммы 1С.2 дестаточне доказать утверждение для оссбогс двудольного графа Я = (V, Vk, Е{Н)). Пусть \V\ — п Докажем чте рамсееЕСким графем для Я будет ссобый двудольный граф G=(U,U2k-\E(G)), где
\U\ = r2k-1{2C%k_1;kn + k- l,...,kn + k- 1). ЦСД
Рассмотрим произвольную раскраску рёбер графа G в два иЕета 1 и 2, Каждое множсстес Y Е U2k~1 смежне как Есршнна особого двудольного графа G с 2к — 1 вершиной, хотя бы к из этих рёбер имеет одинаксЕый иЕет Еыберем и зафиксируем для каждого мвсжества Y его подмножество S(Y). состсяшее из к вершин доли U соединённых с Y рёбрами сдинакоЕСго иЕета. Пусть с(У) 6 {1,2} — это пест рёбер соединяющий Y с вершинами из S(Y).
Можно считать, что элементы U упорядочены Тогда элементы каждого множестЕа Y е и2к~г будут упорядочены. Обозначим через <т(У) мисжество номеров к элементсЕ множества S(Y) в порядке элементов мисжества Y Тогда ег(У) может привимать рсЕвс С^_х значений
Покрасим множсстес t/2fe_1 (тс есть все (2к — 1)-элементные подмножества [/) в2Скк_1 пестов: цветем подмножества У будет нара (ег(У),с(У)) Из выбора размера мвсжества U (см. условие (1С.6)) следует, что существует такое ЕСдмножестЕС W с U. что |1У| = кп + к — 1 и Есе псд-мвсжества У с \У2к~г имеют одинаковый цвет (сг(У),с(У)) (не умаляя сбшнссти будем считать, что ег(У) = а. с(У) = 1(. Мы найдём погружение графа Н е G(W). все рёбра е котором покрашены в исходной раскраске в цвет 1 и тем самым докажем лемму.
Занумеруем элементы множестЕа W ь порядке их следования в U пусть W = {гщ,..., Wkn+k-i}- ВЕедем обозначения
tj = wkj, T = {tu...,tn}, V — {аь ..., ап}.
Положим (р((ц) = U. Остаётся корректно определить ip(Z) для каждого мвсжества Z eVk. Прежде чем построить (p(Z) = У 6 и2к~х мы положим S(Y) = {(р(х) : х G Z}. Из определения погружения понятно, что тогда должно выполняться условие S(Y) — У П Т. а следовательно, нам нужно дополнить множество У ешё к — 1 элементами, не входящими в мвсжество Т. Мы сделаем это так, чтобы множестве порядксЕ номеров элементов множества S(Y) среди элементсЕ множества У было <т(У) = о так как U = wki. не входящих е Т элементов W хватит, чтобы обеспечить это.
Так как по ьыберу мвсжества W мы имеем сг(У) = о. мнежество S(Y) Еыбрано корректно и, опять же е силу ьыбера W. ьсе рёбра особого ДЕудольнсго графа G между Еершинами из S(Y) — {(р(х) : х е Z} и У = ip(Z) покрашены в нвет 1. В завершение остается лишь добавить, что при Z ф Z' мы во построению имеем S(jp(Z)) ф S((p(Z')), поэтому '•p(Z) ф (p(Z'). Таким образом искомое погружение вестроено. □
===Случай произвольного графа===
