4
|
Задача 866. Разбиение графапостоянный адрес задачи: http://www.diofant.ru/problem/2543/показать код для вставки на свой сайт >> |
Задачу решили:
40
всего попыток:
81
поделиться задачей:
|
|
|
Задача опубликована:
11.03.13 08:00
Прислал:
nauru
(Сергей Меньшов)
Источник:
Кубок Колмогорова 2007
Вес:
1
сложность:
4
класс:
8-10
баллы: 100
Темы:
комбинаторика
|
|
Лучшее решение:
Sam777e
|
Вершины графа G можно единственным образом разбить на 5 групп так, что никакие две вершины из одной группы не смежны. Количество вершин в графе - 2012. Найдите минимальное число ребер в этом графе.
Если Вы не можете ее решить, значит Вы не можете ее решить :-)
Обсуждение
Правила >>
Допускаются ли группы, содержащие лишь 1-единственную вершину? - К тому же имеются и другие вопросы - например: что такое "разбиение? графа на..."
Поскольку здесь "Кубок Колмогорова 2007", не хотелось бы бесполезно "растекаться мыслями по дереву!" (поговорка среди умных людей... которые были, в частности, и организаторами всяческих "олимпиад")
Для полной ясности, к задаче 866 предлагается некий вариант условия, к примеру: "Вершины графа G можно единственным образом РАСКРАСИТЬ с помощью 5-ти цветов так, что никакие две вершины одного и того же цвета (если таковые найдутся!) не смежны..."
1. В условии сказано, что вершины можно разбить на 5 групп, т.е. количество вершин, попавших в группу, может быть любым ненулевым, в т.ч., 1.
2. Нигде в условии не написано о разбиении графа.
Exercise is liike this:
1. In G graph we have 2012 points;
2. We are dividing G graph into 5 groups, so that in each group, there is no edges.
3. To create G graph there is only 1 variant.
4. Find minimal value of edges.
Do I have mistake?
1, 2, 4 - да, это условия и вопрос задачи.
3. Ну, если Вы так считаете, попробуйте это доказать (или опровергнуть).