ЭДЗ № 2. Графы на плоскости

Пусть $n_2$, $n_3$, $n_5$ - числа площадей, из которых выходит 2, 3 и 5 дорог.

1. Площадь с 5 дорогами соединена с 5 другими, поэтому площадей не меньше 6. Берём $n=6$.
2. Условия задачи: все три случая встречаются ($n_3\ge 1$, $n_5\ge 1$); площадей с двумя дорогами больше, чем с тремя и чем с пятью ($n_2>n_3$, $n_2>n_5$); всего площадей 6 ($n_2+n_3+n_5=6$).
3. Сумма степеней $2n_2+3n_3+5n_5$ равна удвоенному числу дорог, то есть чётная. Так как $2n_2$ чётно, а 3 и 5 нечётны, число $n_3+n_5$ должно быть чётным.
4. Из $n_2>n_3\ge 1$ следует $n_2\ge 2$, поэтому $n_3+n_5\le 4$. Остаются два случая:
   • $n_3+n_5=4$: тогда $n_2=2$, но $n_3$ или $n_5$ не меньше 2. Условие $n_2>n_3$, $n_2>n_5$ нарушено.
   • $n_3+n_5=2$: тогда $n_3=1$, $n_5=1$, $n_2=4$.
5. Степени площадей: 5, 3, 2, 2, 2, 2. Дорог: $(5+3+4·2)/2=8$.
6. Строим граф по площадям:
   • Площадь 1 (степень 5): дороги ко всем остальным - 1-2, 1-3, 1-4, 1-5, 1-6.
   • Площадь 2 (степень 3): есть 1-2, добавляем 2-3 и 2-4.
   • Площадь 3 (степень 2): есть 1-3 и 2-3, больше дорог не нужно.
   • Площадь 4 (степень 2): есть 1-4 и 2-4, больше дорог не нужно.
   • Площадь 5 (степень 2): есть 1-5, добавляем 5-6.
   • Площадь 6 (степень 2): есть 1-6 и 5-6, больше дорог не нужно.

Матрица степеней: $D=\Gamma ·{\Gamma }^T-A$.

Граф можно нарисовать без пересечений рёбер (рисунок ниже), поэтому он планарный.

Сколько дорог можно перекрыть. В графе $n=6$ площадей и $m=8$ дорог. Чтобы между любыми площадями остался маршрут, оставшиеся дороги должны связывать все площади. Для этого нужно не меньше $n-1=5$ дорог, поэтому перекрыть можно не больше $m-(n-1)=8-5=3$ дорог.

Если оставить ровно 5 дорог, связный граф из 6 площадей не будет содержать циклов, то есть будет деревом. Такое дерево, содержащее все площади, называется остовным деревом графа. Значит, каждое решение - это остовное дерево, и решений столько, сколько у графа остовных деревьев.

Число остовных деревьев находим по матричной теореме Кирхгофа: оно равно определителю матрицы $L=D-A$, из которой вычеркнуты строка и столбец с одним любым номером. $D$ - матрица степеней и $A$ - матрица смежности из п. 2.

1. Вычитаем матрицы по элементам. На диагонали в $L$ остаются степени площадей, вне диагонали стоит −1, если площади соединены дорогой, и 0, если нет.
   −

   =
2. В $L$ вычёркиваем строку 1 и столбец 1. Получаем матрицу $M$ размера $5\times 5$.
   →
3. Определитель $M$ равен числу остовных деревьев.

Любое решение можно выбрать в списке. На рисунке перекрытые дороги показаны красным пунктиром.

Код Прюфера дерева с $n$ вершинами строится так: $n-2$ раза удаляем лист с наименьшим номером и записываем номер вершины, с которой он был соединён.

В списке остовы, которые не являются простой цепью. Звёзды (одна вершина соединена со всеми остальными) не показаны: в их коде все числа одинаковые, и переставлять нечего.

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