Двудольные графы — Страница 2 — Задачи на Графы

Задача 044

01.01.2025 от

Докажите, что у двудольного графа с четным числом вершин и четным числом ребер количество остовных деревьев четно. (Остовное дерево — это подграф исходного графа, содержащий все его вершины и являющийся деревом.)

Подсказка

Всего из дерева получается нечётное число графов, в которых добавлено ещё одно ребро.

Решение

Пусть $G$ — наш граф, $\mathrm{T}(G)$ — множество всех остовных деревьев графа $G$ , а М( $G$ ) — множество всех остовных подграфов графа $G$ , имеющих ровно один цикл. Рассмотрим произвольное дерево $T \subset \mathrm{~T}(G)$ . В нем нечетное число ребер, следовательно, количество не вошедших в $T$ ребер графа $G$ также нечетно. Если к дереву $T \subset \mathrm{~T}(G)$ добавить любое не вошедшее в него ребро графа $G$ , то получится граф из $\mathrm{M}(G)$ . Всего таким образом из дерева $T$ получается нечетное число графов из $\mathrm{M}(G)$ . Наоборот, рассмотрим любой граф $H \subset \mathrm{M}(G)$ и его единственный цикл $Z$ . Граф $H$ может быть получен добавлением ребра к тем деревьям, которые получаются из $H$ удалением одного из ребер цикла $Z$ . Так как граф $G$ двудольный, то в цикле $Z$ — четное число ребер, следовательно, у графа $H$ — четное число остовных деревьев-«»предков»». Отсюда следует, что в множестве $\mathrm{T}(G)$ четное число остовных деревьев.

Задача 046

01.01.2025 от

На бал пришли 30 юношей и 30 девушек. После вечера танцев оказалось, что все юноши танцевали с одним и тем же количеством девушек, а девушка Оля танцевала ровно с 15 юношами. Докажите, что какие-то две девушки танцевали с одним и тем же количеством юношей.

Подсказка

Решение

Отметим мальчиков синими точками, девочек — красными, а тех, кто танцевал друг с другом, соединим линиями. По условию из всех синих точек выходит поровну линий, и потому общее число линий делится на 30 . Из красных точек может выходить $0,1, \ldots, 29,30$ линий. Заметим, что $0+1+\ldots+29+30=15 \cdot 31$ . Чтобы не нашлось двух девочек, танцевавших с одним и тем же количеством юношей, надо вычесть из этой суммы число от 0 до 30 так, чтобы разность разделилась на 30 . Но единственное подходящее для этого число 15 по условию вычесть нельзя.

Задача 054

01.01.2025 от

В группе школьников некоторые знакомы между собой, а некоторые нет. Оказалось, что если какой-то школьник знаком хотя бы с 20 другими школьниками, то все его знакомые незнакомы между собой. Кроме того, если школьник незнаком хотя бы с 20 другими школьниками, то все его незнакомые знакомы между собой. Найдите максимальное возможное число школьников в такой группе.

Подсказка

Пример. Пусть в группе 20 девочек и 20 мальчиков. Все девочки знакомы со всеми мальчиками, но никакие девочки не знакомы друг с другом и никакие мальчики не знакомы друг с другом. Легко видеть, что такая группа удовлетворяет условию.

Решение

Ответ: 40 школьников.

Решение. Пример. Пусть в группе 20 девочек и 20 мальчиков. Все девочки знакомы со всеми мальчиками, но никакие девочки не знакомы друг с другом и никакие мальчики не знакомы друг с другом. Легко видеть, что такая группа удовлетворяет условию.

Оценка. Предположим, что у какого-то школьника $A$ есть хотя бы 21 знакомый $B_{1}, B_{2}, \ldots, B_{21}$ . По условию, все его знакомые незнакомы. Но тогда у школьника $B_{1}$ есть 20 незнакомых $B_{2}, \ldots, B_{21}$ и они незнакомы друг с другом. Противоречие. Следовательно, у каждого школьника не более 20 знакомых и, аналогично, не более 20 незнакомых. Тогда школьников всего не более 41. Осталось доказать, что невозможен случай, когда школьников ровно 41 . Пусть так. Тогда у школьника $A$ ровно 20 знакомых $B_{1}, B_{2}, \ldots, B_{20}$ и ровно 20 незнакомых $C_{1}, C_{2}, \ldots, C_{20}$ . Причем все $B_{i}$ попарно незнакомы, а все $C_{i}$ попарно знакомы. У $B_{1}$ также должно быть ровно 20 знакомых, которые незнакомы между собой. Он уже знает $A$ и не знает никого из $B_{i}$ . Следовательно, он знаком с хотя бы 19 школьниками из $C_{i}$ . Но $C_{i}$ попарно знакомы. Противоречие.

Задача 067

01.01.2025 от

Дано натуральное число п. Назовём словом последовательность из $n$ нулей и единиц, а маской — последовательность из п нулей, единии, и звёздочек. Слово соответствует маске, если оно получено из неё заменой звёздочек на нули и единицы. Рассмотрим набор масок $\mathcal{M}$ , удовлетворяющий следующим двум условиям:

(1) каждое слово соответствует ровно одной маске, и

(2) для каждой из п позиций найдётся маска из $\mathcal{M}$ , в которой в этой позиции стоит не звездочка.

Найдите наименьшее возможное количество масок в таком наборе $\mathcal{M}$ .

Подсказка

Рассмотрим двудольный граф $G$ , в котором вершинами одной из долей будут номера позиций в слове длины $n$ , вершинами второй из долей будут маски, а рёбрами соединим каждую маску с теми позициями, на которых стоит не звездочка. Пусть доля $V_{1}$ это вершины $\{1,2 \ldots, n\}$ , соответствующие номерам позиций, а доля $V_{2}$ это вершины $\left\{u_{1}, u_{2} \ldots, u_{k}\right\}$ , соответствующие маскам.

Решение

Докажем, что в графе $G$ для доли $V_{1}$ выполнено условие леммы Холла. Предположим противное. Рассмотрим в $V_{1}$ минимальное по включению множество $A$ , для которого условие леммы Холла не выполнено. То есть у вершин из $A$ количество соседей меньше, чем $|A|$ , а для любого подмножества $B$ множества $A$ количество соседей у вершин из $B$ хотя бы $|B|$ . Отсюда следует, что у $A$ ровно $|A|-1$ соседних вершин. Без ограничения общности будем считать, что $A=\{1, \ldots, s+1\}$ , а $\left\{u_{1}, \ldots, u_{s}\right\}$ это соседние вершины множества $A$ . Тогда для множества $\{1, \ldots, s\}$ выполнена лемма Холла. Пусть без ограничения общности существует паросочетание $\left(1, u_{1}\right),\left(2, u_{2}\right), \ldots,\left(s, u_{s}\right)$ . Значит, в словах $u_{1}$ , $u_{2}, \ldots, u_{s}$ на $1,2, \ldots, s$ местах соответственно стоят не звёздочки (пусть без ограничения общности там стоят нули). Рассмотрим маски $u_{s+1}, \ldots, u_{k}$ . По построению в этих масках на местах с 1 по $s$ стоят звёздочки. Так как каждое слово можно получить из масок ровно одним способом, то из масок $u_{s+1}, \ldots, u_{k}$ получаются не все слова. Значит, существует множество слов $\underbrace{* * \ldots * *}_{s} \alpha$ (на первых $s$ позициях стоит что угодно, а затем идёт слово $\alpha$ длины $n-s$ ), которое нельзя получить из масок $u_{s+1}, \ldots, u_{k}$ . Тогда слово $\underbrace{1 \ldots 1}_{s} \alpha$ нельзя получить ни из какой маски. Противоречие.

Следовательно, для доли $V_{1}$ выполнено условие леммы Холла. Рассмотрим любое паросочетание, покрывающее долю $V_{1}$ . Пусть это паросочетание $\left(1, u_{1}\right),\left(2, u_{2}\right), \ldots,\left(n, u_{n}\right)$ , а в словах $u_{1}, u_{2}, \ldots, u_{n}$ на $1,2, \ldots, n$ местах соответственно стоят нули. Тогда чтобы получить слово $11 \ldots 11$ нам нужна ещё хотя бы одна маска. Откуда и получаем оценку на $n+1$ .

Задача 071

01.01.2025 от

В графстве Липшир имеется 100 селений, некоторые из которых соединены дорогами (между двумя селениями может быть не более одной дороги). Древний закон не допускает, чтобы дорога соединяла два селения, каждое из которых соединено со всеми остальными. Какое наибольшее количество дорог может быть в графстве?

Подсказка

Каждые два селения, не соединенные дорогой, соединим телеграфным проводом. По закону в графстве нет двух селений, каждое из которых соединено с остальными селениями дорогами.

Решение

Ответ: $\frac{1}{2} \cdot 100 \cdot 98=4900$ .
Решение. Оценка. Каждые два селения, не соединенные дорогой, соединим телеграфным проводом. По закону в графстве нет двух селений, каждое из которых соединено с остальными селениями дорогами. Значит, по крайней мере из 99 селений выходит хотя бы один телеграфный провод. Тогда имеется не менее 50 проводов, и количество дорог не больше разности чисел $\frac{1}{2} \cdot 100 \cdot 99=4950$ (число дорог в полном графе) и 50 (число проводов, которые заменяют собой некоторые «несостоявшиеся» дороги). Пример. Разобьем селения произвольным образом на пары, каждое селение соединим дорогами со всеми остальными, кроме парного ему.

Задача 073

01.01.2025 от

В дереве T 80 вершин. Набор из 39 независимых ребер (не имеющих общих вершин) будем называть толстым паросочетанием. Известно, что дерево $T$ имеет 820 различных толстых паросочетаний. Докажите, что $T$ — путь.

Подсказка

Будем доказывать индукцией по $n$ , что дерево на $2 n$ вершинах имеет не более $C_{n+1}^{2}$ (толстых) паросочетаний с $n-1$ независимыми рёбрами. Как выглядит дерево, если $n \geqslant 3$ и толстых паросочетаний ровно $C_{n+1}^{2}$ ? А при $n=2$ ?

Решение

Решение. Будем доказывать индукцией по $n$ , что дерево на $2 n$ вершинах имеет не более $C_{n+1}^{2}$ (толстых) паросочетаний с $n-1$ независимыми рёбрами. Причём если $n \geqslant 3$ и толстых паросочетаний ровно $C_{n+1}^{2}$ , то дерево является путем. А при $n=2$ граф является или путем, или «графом-ёжиком».

При $n=2$ существуют только такие деревья. Докажем переход. Пусть $T$ — дерево на $2 n$ вершинах, $n \geqslant 3$ . Так как дерево — это двудольный граф, его вершины можно разбить на две доли $V_{1}$ и $V_{2}$ . Заметим, что любое толстое паросочетание содержит по $n-1$ вершин из долей $V_{1}$ и $V_{2}$ . Следовательно, раз уж толстые паросочетния вообще существуют, возможны три случая, два из которых симметричны.
1. $\left|V_{1}\right|=n+1,\left|V_{2}\right|=n-1$ или $\left|V_{1}\right|=n-1,\left|V_{2}\right|=n+1$ . Разберём первый случай, второй доказывается аналогично. Заметим, что в любом толстом паросочетании не участвуют 2 вершины из доли $V_{1}$ . Количество способов выбрать две вершины из $V_{1}$ равно $C_{n+1}^{2}$ . Значит, толстых паросочетаний не более $C_{n+1}^{2}$ . Предположим, что их ровно $C_{n+1}^{2}$ . Тогда для любых двух вершин $u, v \in V_{1}$ существует толстое паросочетание, не содержащее вершины $u$ и $v$ . Но такого не может быть. Действительно, количество рёбер в дереве равно $2 n-1$ , а $\left|V_{2}\right|=n-1$ . Так как $n \geqslant 3$ , в доле $V_{2}$ есть вершина $x$ степени не более 2. Тогда без вершин из $V_{1}$ , среди которых есть все соседи $x$ , толстое паросочетания построить невозможно, противоречие.
2. $\left|V_{1}\right|=n,\left|V_{2}\right|=n$ . Подвесим граф за вершину. Пусть $v$ — висячая вершина последнего уровня, а $u$ — её сосед на предыдущем уровне. Без ограничения общности будем считать, что $v \in V_{1}$ . Если у вершины $u$ есть ещё одна соседняя висячая вершина $w$ , то любое толстое паросочетание не содержит одну из вершин $w$ или $v$ , и одну из вершин $V_{2}$ . Тогда толстых паросочетаний не больше $2 n<C_{n+1}^{2}$ при $n \geqslant 3$ .

Пусть у вершины $u$ нет соседних висячих вершин, кроме $v$ . Разобьём толстые паросочетания $T$ на два типа, первый тип — не содержащие $v$ , второй тип — содержащие ребро $u v$ . Паросочетаний первого типа не более $n$ , так как они не содержат $v$ и одну из вершин $V_{2}$ , коих $n$ . Все паросочетания второго типа образуют толстое паросочетание дерева $T^{\prime}=T-u-v$ , причём в $T^{\prime}$ поровну вершин в долях. По предположению индукции в дереве $T^{\prime}$ не более $C_{n}^{2}$ толстых паросочетаний. Значит, в $T$ не более $C_{n}^{2}+n=C_{n+1}^{2}$ толстых паросочетаний. Более того, если в дереве $T$ ровно $C_{n+1}^{2}$ толстых паросочетаний, то паросочетаний первого типа ровно $n$ , второго — ровно $C_{n}^{2}$ , а дерево $T^{\prime}$ — это путь $a_{1} a_{2} \ldots a_{2 n-2}$ . Если сосед $u$ — это $a_{1}$ или $a_{2 n-2}$ , то $T$ — путь. Иначе из соображения чётности одна из вершин $a_{2}$ и $a_{2 n-3}$ лежит в доле $V_{2}$ дерева $T$ (пусть $a_{2}$ ). Но тогда при удалении вершин $v$ и $a_{2}$ дерево не имеет паросочетания. Следовательно, паросочетаний первого типа меньше $n$ , противоречие. Индукционный переход доказан.

Задача 081

01.01.2025 от

В городе есть несколько мальчиков и девочек, некоторые пары знакомы. Оказалось, что в любом множестве $D$ из 8 девочек найдётся (возможно, пустое) подмножество $D^{\prime}$ такое, что любой мальчик, знакомый со всеми девочками из $D^{\prime}$ , знаком ещё хотя бы с одной девочкой из $D$ . Докажите, что в любом множестве $M$ из 300 мальчиков найдётся (возможно, пустое) подмножество $M^{\prime}$ такое, что любая девочка, знакомая со всеми мальчиками из $M^{\prime}$ , знакома ещё хотя бы с одним мальчиком из $M$ .

Подсказка

Решение

Заметим, что $D_{1} \subset D$ может быть взято за $D^{\prime}$ тогда и только тогда, когда ни для какого мальчика множество его знакомых в $D$ не совпадает с $D_{1}$ . Аналогично с $M$ и $M^{\prime}$ . Предположим, что нашлось множество из $M$ мальчиков, в котором нельзя выделить $M^{\prime}$ , удовлетворяющее условию. Тогда для любого $M_{1} \subset M$ найдется девочка, которая в множестве $M$ знакома в точности с мальчиками из $M_{1}$ . Выберем в $M_{1} 300$ мальчиков, из них — 256 , и каждому мальчику сопоставим своё четырёхзначное двоичное число. Выберем 8 девочек так, чтобы $i$ -ая девочка знала в множестве $M$ в точности тех мальчиков, которым сопоставлено число с 1 в $i$ -ом разряде (мальчиков, которым ничего не сопоставлено, все эти девочки не знают). Тогда легко видеть, что в выбранном множестве девочек никакое подмножество нельзя назначить $D^{\prime}$ . Действительно, если $i_{1}, \ldots, i_{k}$ — номера девочек в подмножестве, то мальчик, которому сопоставлено число с единицами в разрядах $i_{1}, \ldots, i_{k}$ и нулями во всех остальных разрядах, из восьми выбранных девочек знает в точности $i_{1}, \ldots, i_{k}$ .

Задача 098

01.01.2025 от

В графе на 20 вершинах степень каждой вершины не более 3 . Какое наибольшее количество циклов длины 4 может быть в этом графе?

Подсказка

Возьмём любое ребро графа. Пусть оно входит в какой-либо цикл длины 4. Выбросим из этого цикла ребро, не имеющее с нашим общих вершин. Получится маршрут длины 3, где взятое нами ребро является средним из трёх, и цикл по этому маршруту восстанавливается однозначно.

Решение

Ответ: 27. Решение. Напомним, что через $K_{3,3}$ обозначается полный двудольный граф на 6 вершинах, то есть граф, три вершины которого можно покрасить в один цвет, а три — в другой так, что любые две одноцветные вершины будут соединены ребром, а любые две разноцветные — нет. В графе $K_{3,3} 9$ циклов длины 4, потому что цвета вершин в цикле чередуются, и по две вершины каждого цвета в $K_{3,3}$ можно выбрать $3 \times 3=9$ способами. Отсюда получается пример на 27 циклов: достаточно взять три графа $K_{3,3}$ , а из двух оставшихся вершин рёбер не проводить.

Покажем, что больше 27 циклов длины 4 в нашем графе не бывает Возьмём любое его ребро. Пусть оно входит в какой-либо цикл длины 4. Выбросим из этого цикла ребро, не имеющее с нашим общих вершин. Получится маршрут длины 3, где взятое нами ребро является средним из трёх, и цикл по этому маршруту восстанавливается однозначно. Но каждый из двух концов взятого нами ребра принадлежит, кроме него, максимум ещё двум рёбрам. Поэтому в нашем графе есть максимум $2 \times 2=4$ маршрута длины 3 , где взятое нами ребро является средним из трёх. Таким образом, через каждое ребро нашего графа проходит не более 4 циклов длины 4.

Назовём ребро хорошим, если оно входит ровно в 4 цикла длины 4 . Покажем, что если в компоненте связности нашего графа есть хотя бы одно хорошее ребро, то эта компонента имеет вид $K_{3,3}$ . В самом деле, в этом случае из каждой вершины нашего ребра должно выходить ещё 2 ребра, и каждый из вторых концов рёбер, выходящих из одной вершины, должен соединяться с каждым из вторых концов рёбер, выходящих из другой вершины. Получается $K_{3,3}$ , а наружу рёбра из него не ведут, потому что степень каждой вершины $K_{3,3}$ и так уже равна 3.

Пусть в нашем графе ровно $k \leq 2$ компонент связности вида $K_{3,3}$ . Тогда в нём $20-6 k$ вершин, входящих в «плохие» компоненты, где через каждое ребро проходит не более 3 циклов длины 4. В этих компонентах не более $3 \times(20-6 k) / 2=30-9 k$ рёбер и, стало быть, не более $3 \times(30-9 k) / 4=(90-27 k) / 4$ циклов длины 4, а всего в графе этих циклов не больше, чем $9 k+(90-27 k) / 4=22,5+9 k / 4 \leq 22,5+18 / 4=27$ . Если же в графе 3 компоненты связности вида $K_{3,3}$ , то в этих компонентах 27 циклов длины 4 , а две оставшиеся вершины, не будучи связанными с остальными 18 -ю, новых циклов длины 4 добавить не могут. Итак, циклов длины 4 у нас всегда не более 27.