Конкурсная задача ММ105 (6 баллов)
Математик C загадал некий граф и сообщил математику A степени всех вершин,
а математику B - количество вершин и число связных компонент этого графа.
Дальше, как водится, состоялся обмен мнениями.
A: Знание степеней всех вершин графа не позволяет мне однозначно определить,
какой граф был загадан.
B: Зато я теперь в состоянии сделать это.
Сколько ребер было в загаданном графе?
Примечание:
Рассматриваются классические графы (неориентированные, без петель и кратных
ребер).
Решение
Приведу (немного подредактированное) решение Виктора Филимоненкова.
Пусть k - число компонент связности графа, n - число вершин, сообщенные В, а m - искомое число ребер. Напомню, что в любом графе справедливо соотношение n-k ≤ m ≤ C2n-k+1 (*). Напомню, также, что Kn - это полный n-вершинный граф.
1. n-k < 4. Действительно, иначе одна из компонент связности может содержать 5 вершин. Среди связных пятивершинных графов есть два неизоморфных графа с одним набором степеней вершин, это 1, 2, 2, 2, 3 (цикл длины 4 с «хвостом» длины 1 и цикл длины 3 с «хвостом» длины 2). Значит, В в этом случае не может исключить, что одна из компонент связности - один из таких пятивершинных графов, и его знаний количеств вершин и компонент связности не хватит для того, чтобы определить, какая именно эта компонента связности.
2. Коротким простым перебором легко убедиться, что при n-k < 3 граф однозначно восстанавливается по степеням вершин.
3. При n-k = 3 на основании (*) возможны следующие наборы ненулелвых степеней вершин
(кроме них, в графе может присутствовать произвольное количество изолированных вершин):
1) 1,1,1,1,1,1 - 1 граф;
2) 1,1,1,1,2 - 1 граф;
3) 1,1,2,2,2 - 2 графа (3.a граф с компонентами K3 и K2, 3.б - цепь);
4) 1,1,1,3 - 1 граф;
5) 1,1,2,2 - 1 граф;
6) 1,2,2,3 - 1 граф;
7) 2,2,2,2 - 1 граф;
8) 2,2,3,3 - 1 граф;
9) 3,3,3,3 - 1 граф.
Таким образом, только в случае 3 A имел право на свою реплику. Отметим, что
граф из пункта граф 3.б соответствует соотношению n-k = 4, а этом случае, как было
показано, B не может однозначно определить заганный граф. Поэтому был загадан
граф из пункта 3.a, имеющий (как, впрочем, и граф из 3.б) 4 ребра.
Ответ: 4 ребра.
Обсуждение
Отмечу, что условие задачи не позволяет однозначно восстановить загаданный граф. Ведь, кроме компонент K3 и K2, в графе может содержаться несколько компонент K1.
Награды
За правильное решение задачи ММ105 Виктор Филимоненков, Кирилл Веденский и Анатолий Казмерчук получают по 6 призовых баллов, а Николай Дерюгин (почему-то сразу же положивший n = 5) - 3 балла.
Эстетическая оценка задачи - 4.3 балла