Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

№105

Конкурсная задача ММ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 балла


 

 


Страница: [[marathon:problem_105]]

marathon/problem_105.txt · Последние изменения: 2019/04/03 19:49 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006