Задача 037 — Задачи на Графы

Каждые два города страны Гельбии соединены односторонним авиарейсом. Региональные бароны превратили страну в федерацию двух республик с общей столицей (каждый город, кроме столицы, принадлежит ровно одной из республик, а столица — обеим). Министерство путей сообщения посчитало количество $N$ маршрутов, проходящих по каждому городу всей страны по одному разу (не возвращающихся в исходный город), а также аналогичные количества $N_{1}$ и $N_{2}$ для каждой из республик. Докажите, что $N \geq N_{1} N_{2}$ .

Подсказка

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

Решение

Построим ориентированный граф, вершины которого соответствуют городам, а рёбра — дорогам. Пусть вершина $w$ соответствует столице, $A$ и $B$ — графы, соответствующие республикам. Сначала сформулируем несложную лемму.

Пусть $P$ и $Q$ — два непересекащихся пути в полном ориентированном графе Т. Тогда существует путь $R$ на вершинах этих двух путей, в котором все вершины пути $P$ следуют в порядке пути $P$ , а все вершины пути $Q$ следуют в порядке пути $Q$ . Этот факт нетрудно доказать индукцией по длине пути $Q$ , вставляя по очереди его вершины в путь $P$ . Отметим, что лемма верна и для случая, когда один из путей $P$ и $Q$ или они оба — пустые (из 0 вершин). Назовём путь $R$ из леммы склейкой путей $P$ и $Q$ .

Рассмотрим любые гамильтоновы пути $P$ графа $A$ и $Q$ графа $B$ . Эти пути, очевидно, имеют вид $P=P_{1} w P_{2}$ и $Q=Q_{1} w Q_{2}$ (возможно, какие-то из участков $P_{1}, P_{2}, Q_{1}$ и $Q_{2}$ — пустые). По лемме существует путь $R_{1}$ — склейка $P_{1}$ и $Q_{1}$ и путь $R_{2}$ — склейка $P_{2}$ и $Q_{2}$ . Отметим, что если путь $R_{1}$ непустой, то он кончается либо последней вершиной пути $P_{1}$ , либо последней вершиной пути $Q_{1}$ , то есть, из последней вершины пути $R_{1}$ выходит ребро в $w$ . Аналогично, либо путь $R_{2}$ — пустой, либо из $w$ выходит стрелка в первую вершину пути $R_{2}$ . Тогда $R=R_{1} w R_{2}$ — гамильтонов путь в графе $T$ , в котором вершины подграфа $A$ следуют в порядке пути $P$ , а вершины подграфа $B$ следуют в порядке пути $Q$ . Каждой паре гамильтоновых путей ( $P, Q$ ) очевидно, соответствует свой путь $R$ .