СПРОСИ ПРОФИ

Елена Лиховцева

Пользователь Ask.profi.ru
Вопросов1
Ответов 0
Рейтинг 2

Вопросы:


👍
+2
👎

Задача про граф   3 ответа

В графе 100 черных вершин, 50 белых и есть еще зеленые. Каждая зеленая вершина смежна ровно с одной черно-белой парой, то есть ровно с одной черной вершиной и ровно с одной белой. Никакие три зеленые вершины не смежны с одной и той же черно-белой парой. Какое наибольшее количество зеленых вершин может быть в этом графе?

Я вроде придумала максимизирующую конструкцию, но не получается доказать ее максимальность...
ASK.PROFI.RU © 2020-2024