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

Тогда все вершины графа являются

Тогда все вершины графа являются

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

Решение. Рассмотрим следующий граф: одна группа вершин — это школьники, вторая — задачи, а любое ребро соединяет какую-то за­дачу и решившего ее школьника. Тогда все вершины графа являются двухвалентными. Если выйти из произвольной вершины и пойти по произвольному пути, то легко видеть, что мы рано или поздно

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

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

Определение 5. Граф называется двудольным, если его вершины можно разбить на две группы (называемые долями) так, чтобы все ребра (или дуги) были между различными долями.

Паросочетанием называется такой набор ребер графа, что каждая вершина графа является концом не более одного ребра из набора. Паросочетание называется совершенным, если каждая вершина яв­ляется концом ровно одного ребра паросочетания.

Раскраска вершин графа называется правильной, если никакие две вершины одного цвета не соединены ребром. Граф называется к- дольным, если правильная раскраска его вершин возможна к цветами и не менее.

Задача 22. Какие графы из задач 1, 2 и 3 первого листка про графы являются двудольными? А сколькодольными являются остальные?

Решение. В двудольном графе обязательно четное число вершин — это поможет при разборе вариантов.

В задаче 1 все графы являтся трехдольными. В задаче 2 мы раз­берем для краткости лишь графы с четырьмя вершинами. Граф без ребер однодольный, граф с одним ребром и оба графа с двумя реб­рами двудольные. Среди графов с тремя ребрами два двудольных и один трехдольный. Из графов с четырьмя ребрами один двудольный, а второй — трехдольный. Граф с пятью ребрами трехдольный, а с шестью — четырехдольный (все вершины разных цветов). В задаче 3 граф стран СНГ является трехдольным, граф чисел от 2 до 15 четы­рехдольный.