Конкурсная задача ММ257 (9 баллов)

Задача ММ257 сюжетно связана с ММ237

Студент математического факультета Вася Пупкин пропустил (по уважительной причине) занятие по дискретной математике. Однокурсники рассказали, что на занятии рассматривался некий граф. Но ни один из них не зафиксировал этот граф ни с помощью гаджетов, ни на бумагу. Впрочем, Васины однокурсники, утверждают, что это не страшно, поскольку они и так помнят этот граф. В подтверждение своих слов они наперебой кинулись вспоминать характеристики графа:
Аня: В графе было ровно 3 связных компоненты.
Ваня: Причем во всех связных компонентах графа имелись циклы.
Даня: А еще среди связных компонент не было изоморфных.
Маня: Число ребер в одной из компонент было равно половине общего числа ребер.
Саня: При этом число ребер было равно сумме количеств вершин и связных компонент.
Таня: В графе была всего одна вершина степени 3.
Зина: А всего в графе было не более 13 вершин.
Лина: И при этом не было висячих вершин.
Нина: А степень одной из вершин не менее чем на 2 превосходила степень каждой из остальных вершин.
Фаина: Зина, Лина и Нина правы.
Услышавший эти реплики преподаватель сказал, что память подвела ровно одного человека.
Сможет ли Вася (умница и отличник) однозначно восстановить граф?

Решение

Привожу решения Виктора Филимоненкова и Анатолия Казмерчука.

Обсуждение

Сразу несколько участников покритиковали ведущего за то, что он не уточнил, что имеет в виду под «графом». Сначала меня удивила такая реакция: ведь в предудыщих марафонских турнирах графы фигурировали десятки раз и подобных вопросов не возникало. Задумавшись я понял, что в большинстве предыдущих задач структура графа, возникающего на том или ином множестве, вводилась прямо в условии. Впрочем, в ряде задач (ММ105, ММ116, ММ146, ММ153, ММ156) так же как и в ММ257 рассматривались абстрактные графы, но к неоднозначности это не приводило. А меожет, и приводило… Давно это было, 100 задач назад. В общем, на будущее: под графом я всегда имею в виду классический граф: непустое (обычно конечное) множество вершин и множество ребер, каждое из которых есть двухэлементое множество вершин. Это не значит, что я зарекаюсь использовать будущих задачах, орграфы, мультиграфы, гиперграфы, бинарные отношения и даже матроиды. Но когда я буду использовать такие структуры, я отдельно заострю на этом внимание.

Составляя задачу, я вдохновлялся ММ237. И начал с того, что продублировал реплику Фаины. Дальнейшие реплики подбирались так, чтобы, с одной стороны, не было лишних, а с другой - граф определялся однозначно. Вроде, удалось. Хотя задача понравилась далеко не всем. Но мне понравилась. Поэтому я, все же, намерен в одном из грядущих конкурсов заставить Васю и его друзей обсудить новый математический объект.

У тех, кто отозвался, задача затруднений не вызвала. Единственный балл изъят за излишнее увлечение сестрой таланта.

Награды

За решение задачи ММ257 участники Марафона получают следующие призовые баллы:
Анатолий Казмерчук - 10
Константин Шамсутдинов - 9
Владислав Франк - 9
Денис Овчинников - 9
Виктор Филимоненков - 9
Олег Полубасов - 8.

Эстетическая оценка задачи - 4.3 балла