|
||||||||||||||||||
|
Содержание№105Конкурсная задача ММ105 (6 баллов)
Математик C загадал некий граф и сообщил математику 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 на основании (*) возможны следующие наборы ненулелвых степеней вершин
(кроме них, в графе может присутствовать произвольное количество изолированных вершин): Ответ: 4 ребра. Обсуждение Отмечу, что условие задачи не позволяет однозначно восстановить загаданный граф. Ведь, кроме компонент K3 и K2, в графе может содержаться несколько компонент K1. Награды За правильное решение задачи ММ105 Виктор Филимоненков, Кирилл Веденский и Анатолий Казмерчук получают по 6 призовых баллов, а Николай Дерюгин (почему-то сразу же положивший n = 5) - 3 балла. Эстетическая оценка задачи - 4.3 балла
|
|||||||||||||||||
|
||||||||||||||||||
|