СПРОСИ ПРОФИ
👍
+2
👎 23

Задача про граф

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

Я вроде придумала максимизирующую конструкцию, но не получается доказать ее максимальность...
👍
0
👎 0
Или я что-то не понимаю или задача тривиальна.

Сколько у нас всего пар черно-белых вершин? понятно, что их [m]50\cdot 100 = 5000[/m]. К каждой такой паре присоединим по две зеленый вершины, итого мы добавили 10000 зеленый вершин и условие выполнено. Пусть как-то удалось добавить больше, тогда по принципу Дирихле найдется черно-белая пара, к которой присоединено не менее трех зеленых вершин. Противоречие.
👍
0
👎 0
Большое спасибо Вам за ответ. Я неудачно сформулировала условие. Вместо "Никакие три зеленые вершины не смежны с одной и той же черно-белой парой" я хотела написать "Для любой зеленой вершины хотя бы одна вершина из ее черно-белой пары смежна максимум с одной другой зеленой вершиной".
  #3   28 фев 2017 22:27   Ответить
👍
+1
👎 1
> Вместо
> Никакие три зеленые вершины не смежны с одной и той же черно-белой парой
> я хотела написать
> Для любой зеленой вершины хотя бы одна вершина из ее черно-белой пары смежна максимум с одной другой зеленой вершиной

Немного ошиблись, с кем не бывает...

Теперь я хочу знать, откуда эта задача, т.к. я имею подозрения, что Вы пытаетесь переформулировать какую-то задачу с какой-то олимпиады.

Задайте свой вопрос по высшей математике
профессионалам

Сейчас онлайн 75 репетиторов по высшей математике
Получите ответ профи быстро и бесплатно

Другие вопросы на эту тему:

👍
0
👎 05

Комбинаторика: рассадка людей за столом   5 ответов

За длинным столом рассаживают p мужчин и q женщин.
Сколько есть возможных положений, где все мужчины сидят вместе?

Я взяла для примера 3-х мужчин и 2-х женщин, для того, чтобы было легче расписать всевозможные получающиеся комбинации.
И действительно получается 36 различных случаев рассадить мужчин рядом друг с другом, но вот формула p!*(q+1)! = 3!*3! = 36 хотя конечно же и правильная, только как-то тяжело логически усваивается у меня…
  20 июн 2017 16:27  
👍
0
👎 010

Задача по комбинаторике   10 ответов

На полке стоят N книг.сколькими способами можно взять M из них так,что бы никакие две не стояли рядом?
👍
0
👎 02

Теория вероятности, комбинаторика.   2 ответа

Задача.
В урне имеется 36 шаров, из них 20 — красных, 14- зеленых, 2-синих. Вытаскиваем наугад 7, какова вероятность того, что как минимум 2 шара будут одинаковыми.

Не знаю как учесть, что остальные шары могут быть любыми.
Запуталась с формулами, получаю не правдоподобно маленькую вероятность, около 1/30. При решении использую формулу сочетания.
  03 дек 2013 17:38  
👍
0
👎 05

Помогите решить задачку   5 ответов

каждая из 2 команд по 5 спортсменов проходит по отдельности жеребьевку для присвоения спортсменам номеров от 1 до 5.Два брата входят в состав разных команд.Определить:
1.один из братьев получит номер 2 ,а другой 7 и наоборот:первый 7,второй 2.
2.братья получат однаковые номера
3.сумма полученных ими номеров будет не более 7
  15 апр 2011 22:59  
ASK.PROFI.RU © 2020-2023