👍 +2 👎 |
Задача про графВ графе 100 черных вершин, 50 белых и есть еще зеленые. Каждая зеленая вершина смежна ровно с одной черно-белой парой, то есть ровно с одной черной вершиной и ровно с одной белой. Никакие три зеленые вершины не смежны с одной и той же черно-белой парой. Какое наибольшее количество зеленых вершин может быть в этом графе?
Я вроде придумала максимизирующую конструкцию, но не получается доказать ее максимальность...
комбинаторика дискретная математика высшая математика математика обучение
Елена Лиховцева
|
👍 0 👎 |
Или я что-то не понимаю или задача тривиальна.
Сколько у нас всего пар черно-белых вершин? понятно, что их [m]50\cdot 100 = 5000[/m]. К каждой такой паре присоединим по две зеленый вершины, итого мы добавили 10000 зеленый вершин и условие выполнено. Пусть как-то удалось добавить больше, тогда по принципу Дирихле найдется черно-белая пара, к которой присоединено не менее трех зеленых вершин. Противоречие. |
👍 0 👎 |
Большое спасибо Вам за ответ. Я неудачно сформулировала условие. Вместо "Никакие три зеленые вершины не смежны с одной и той же черно-белой парой" я хотела написать "Для любой зеленой вершины хотя бы одна вершина из ее черно-белой пары смежна максимум с одной другой зеленой вершиной".
|
👍 +1 👎 |
> Вместо
> Никакие три зеленые вершины не смежны с одной и той же черно-белой парой > я хотела написать > Для любой зеленой вершины хотя бы одна вершина из ее черно-белой пары смежна максимум с одной другой зеленой вершиной Немного ошиблись, с кем не бывает... Теперь я хочу знать, откуда эта задача, т.к. я имею подозрения, что Вы пытаетесь переформулировать какую-то задачу с какой-то олимпиады. |
👍 0 👎 |
Комбинаторика: рассадка людей за столом
|
👍 0 👎 |
Задача по комбинаторике
|
👍 0 👎 |
Теория вероятности, комбинаторика.
|
👍 0 👎 |
Помогите решить задачку
|