Таблицы Брадиса

В некой компании п юношей.

В некой компании п юношей.

Элементы математики в задачах - Г. А. Мерзон

Задача 23. Равносильна ли двудольность неориентированного графа отсутствию циклов нечетной длины?

Решение. Равносильна. Если граф двудольный, то все циклы, очевид­но, имеют четную длину. Докажем в другую сторону. Будем раскраши­вать вершины графа в два цвета так, чтобы ребра были лишь между вершинами разных цветов (начав с произвольной вершины). Если какая-то вершина оказалась раскрашена таким образом в два цвета, то это означает, что в графе есть цикл нечетной длины, что неверно. Поэтому все вершины можно правильным образом раскрасить в два цвета, а это то же самое, что разбить на две доли.

Задача 24. Любое ли дерево двудольно?

Теория графов 2                                    219

Решение. Да, поскольку дерево — это граф, в котором нет никаких циклов вообще, там нет и циклов нечетной длины.

Задача 25* (теорема Холла). В некой компании п юношей. При каждом к = 1,2,..., п для любых к юношей в этой компании найдется не менее к девушек, знакомых хотя бы с одним из рассматриваемых к юношей. Можно ли просватать всех юношей за знакомых девушек?

Является ли это условие необходимым?

Иными словами, верно ли, что в двудольном неориентированном графе (с п вершинами в первой доле) существует паросочетание размера п тогда и только тогда, когда для каждого набора из к вершин первой доли с ними соединены хотя бы к вершин второй доли?

Решение. Докажем по индукции, что это верно. База (п = 1) очевидна, докажем шаг индукции. Если X — множество вершин из первой доли, то через а(X) будем обозначать множество вершин, соединенных с X.

Предположим сперва, что выполнено условие |а(X)| > |X| для всех X,

0 < |X | < п. Тогда выкинем из графа произвольную пару вершин А и В, соединенную ребром, и заметим, что для оставшегося графа также выполнены условия теоремы, а значит, можно применить предполо­жение индукции.