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


Содержание

156

Kонкурсная задача ММ156 (ТГ-3) (5 баллов)

На занятии по дискретной математике на доске был изображен некоторый граф. Вася Пупкин записал в тетрадку количество вершин и ребер каждой связной компоненты графа, а также степени вершин самой большой (по количеству вершин) компоненты. Но само изображение графа он срисовать забыл. Кроме того, он забыл, за какую именно из вышеперечисленных характеристик отвечает каждое из записанных чисел. Сможет ли Вася решить домашнее задание «Найти диаметры каждой связной компоненты», если у него в тетрадке записаны числа: 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 6, 9?

Решение

Приведу решение Евгения Гужавина:

Из анализа чисел последовательности видно, что:

1. В самой большой компоненте связности (КС) чётное число вершин, т.к. количество чисел в последовательности чётно.
2. Число 9 может обозначать только число рёбер одной из КС. Действительно, если это количество вершин КС, то количество рёбер в этой КС должно быть не менее 8, а если это степень одной из вершин самой большой КС, то количество вершин в этой КС должно быть не менее 10, но таких чисел в заданной последовательности нет.
3. КС с 9-ю рёбрами должна иметь не менее 5-ти вершин, т.к. для полного графа (3·4)/2 < 9 < (4·5)/2. Из пункта 1 следует, что это число 6.

Теперь известно, что граф имеет три КС и в большей из них шесть вершин и девять рёбер. Для того, чтобы найти пары чисел (количество вершин, количество рёбер) оставшихся КС, используем тот факт, что количество рёбер графа равно полусумме степеней вершин. В нашем случае сумма оставшихся десяти чисел последовательности равна 31, значит нужно проверить все группы по четыре числа, дающие в сумме 13:
(1,4,4,4) не подходит - четыре вершины и одно ребро;
(2,3,4,4) подходит - (3,2),(4,4);
(2,2,4,5) не подходит - две вершины и два ребра;
(1,3,4,5) не подходит - три вершины и одно ребро;
(2,3,3,5) не подходит - пять вершин и три ребра;
(3,3,3,4) подходит - (3,3),(4,3).

В итоге имеем два варианта разделения чисел заданной последовательности: {(3,2),(4,4),(6,9),(1,2,3,3,4,5)} и {(3,3),(4,3),(6,9),(1,2,2,4,4,5)}.
Покажем, что для второго варианта невозможно построить граф. Для этого рассмотрим самую большую КС. Видно, что шестая (по порядку) вершина смежна всем остальным, т.к. её степень равна пяти. Удалим все рёбра инцидентные этой вершине, получим следующую последовательность степеней вершин нового графа (0,1,1,3,3,0). Повторим проделанное для пятой (по порядку) вершины, получим последовательность (0,0,0,2,0,0) - петля в четвёртой вершине, что невозможно.
Проверим первый вариант: (1,2,3,3,4,5) → (0,1,2,2,3,0) → (0,0,1,1,0,0).
Теперь можно ответить на поставленный в задаче вопрос - не сложно увидеть, что диаметр каждой из трёх КС равен двум.

Обсуждение

Легко убедиться, кто трехвершинная и шестивершинная компоненты определены условиями задачи однозначно, а для четырехвершинной существуют два варианта. Некоторые участники остановились на этом моменте, другие ограничились констатацией факта, что диаметр каждой компоненты определен однозначно. В связи с этим я испытывал затруднения, оценивая решение, в котором утверждалось, что существует более одного графа, со степенями вершин 1, 2, 3, 3, 4, 5. С одной стороны, это не так, а с другой - никак не влияет на ответ. Я думаю наиболее проницательные читатели догадаются, стал ли снижать оценку за этот промах.

Удовлетворю любопытство одного из участников Марафона: расскажу, как я сочинял задачу ММ156. Каюсь, я делал это совершенно неправильно. Мне просто было интересно, что получится при таком подходе. Сначала я сочинил текст условия. Но без вопроса, что надо найти. А затем написал «от фонаря», не имея в виду ни одного конкретного графа, 12 чисел (даже то, что их именно 12 выяснилось позже, когда я их пересчитал). Затем провел анализ, наподобие тех, что проводили участники, решившие задачу. Я полагал, что для получения содержательной задачи придется сделать несколько попыток. Однако первый же набор чисел привел к ситуации, когда граф определен неоднозначно, но количество компонент и их диаметры можно восстановить.

Награды

За правильное решение задачи ММ155 Виктор Филимоненков, Олег Полубасов, Сергей Половинкин, Алексей Волошин, Евгений Машеров, Евгений Гужавин, Дмитрий Пашуткин, Николай Дерюгин и Анатолий Казмерчук получают по 5 призовых баллов.

Эстетическая оценка - 4.7 балла

Разбор задачи ММ156 подготовил Владимир Лецко


 

 


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

marathon/problem_156.txt · Последние изменения: 2016/10/10 10:10 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006