Вот тебе утешение: вместо куба мог и бриллиантик использовать. Лучше ты многогранник не сделаешь, дальше уже надо выходить из плоскости и извращаться :)
Речь идет о клубе, значит все джентльмены обязаны знать (представлены) председателя клуба (выборная должность), который выносит решение о принятии в клуб. В задании уже ошибка.
Получается топографическая "звезда" PC - Hub - PC. Где РС члены клуба, Hub председатель. Два PC - один отдельный VLAN, а значит таких VLAN ов может быть до бесконечности.
Не более трех, на счет не менее ни чего не сказано.
> По правилам клуба джентльменов любые два члена клуба должны быть или знакомы друг с
> другом, или иметь общего знакомого в этом клубе. Оказалось, что у каждого члена клуба не более
> трех знакомых в этом клубе. Какое наибольшее число джентльменов может быть в этом клубе?
А я не совсем понял условие. Вот эти трое знакомых они все с прямой связью или допускается связь через кого-то? И обязательно ли у каждого должно быть по три знакомых, допускается ли меньшее количество?
Так как в постановке задачи нужно только сообщить максимальное число членов, то достаточно пункта 1. А показывать сам граф и не требовалось.
Кстати задача лего формулируется в теории графов:
Постоить граф с максимальным числом вершин при соблюдении условий:
1. Степень вершины не более трех
2. Кртачайший путь между любыми двумя вершинами не больше 2 ребер
это олимпиадное задание для второго класса средней школы. т.е. нужно его решить в доступной второкласснику форме. поэтому все и старались решить визуально, в первую очередь.
> допускается, но мы ищем максимум. Т.е. у каждого максимум три прямых знакомых и связь второго уровня с остальными.
Что за связь второго уровня? тут про это нет:
> По правилам клуба джентльменов любые два члена клуба должны быть или знакомы друг с
> другом, или иметь общего знакомого в этом клубе. Оказалось, что у каждого члена клуба не более
> трех знакомых в этом клубе. Какое наибольшее число джентльменов может быть в этом клубе?
> между противоположными вершинами у тебя по 5 "знакомых". а должен быть 1.
Каждый кружок имеет не более трёх касаний. Ну и знакомые знакомых не обязательно должны быть сами знакомы, да и про то что общий знакомый должен быть только 1 - в задаче не сказано.
> Каждый кружок имеет не более трёх касаний. Ну и знакомые знакомых не обязательно должны быть сами знакомы, да и про то что общий знакомый должен быть только 1 - в задаче не сказано.
Не выполняется условие:
>любые два члена клуба должны быть или знакомы друг с другом, или иметь общего знакомого в этом клубе
А зачем вы соединяете в основании всё по кругу? Рядом стоящие элементы имеют связь через родителя. Нам, как всегда, поможет звезда (увы, красной её сделать не получается)
Не нравится, что я первый это придумал, но не смог до конца реализовать. Не нравится, что ты просто украл мою идею.
Не нравится что все лавры и всенародная любовь и уважение достанутся тебе, а не мне.
Не нравится, что ты так понятно и красиво нарисовал то, что я никак не мог выразить.
И воообще, мне всё не нравится!!! На твоем месте должен был быть я!
Для второклассника объяснение решение может быть таким.
1. Рисуем квадрат, - вершины - джентльмены. Их 4. Связи - знакомства: по сторонам квадрата и двум непересекающимся диагоналям. Получаем, что у каждого есть по 3 знакомых (условие не больше трех выполняется), и каждый знаком с каждым (условие, что любые двое должны быть знакомы или между собой или через общего знакомого тоже выполняется).
2. На каждой стороне квадрата вставляем вершину - т.е. получаем, что "углы" квадрата знакомы не между собой, а через одного знакомого - те самые новые вершины. Придется добавить еще две линии-связи между новыми вершинами. Условие не больше трех мы продолжаем выполнять - т.к. новых связей для старых вершин мы не добавили, а у новых вершин как раз получили по 3 связи. Условие знакомства любых двух через одного общего знакомого сохранили. Так мы получили 8 джентльменов.
3. И еще двух мы можем добавить, если добавим две вершины на стартовых двух диагоналях и, соединив эти две вершины между собой. Получаем тех самых 10 джентльменов и твой рисунок.
@Illais ну да, это один из вариантов как надо думать чтобы такое построить и проверить.
Но вообще конструктивно прав @CoPBaHeu - в начале надо брать дерево высоты 2, оно там 100% есть, а дальше соединять как попало, какой-то вариант подойдёт. Если всё перебрали и жопа - значит 10 нельзя, но внезапно мы нашли решение, значит всё хорошо :) Аналогично можно решать для 3 кругов, 4 кругов и.т.д. только там начнётся веселье - верхняя граница уже не будет достижима. Общего решения без перебора нету :(
> Итак, полное решение:
>
>
> 1) Больше 10 сделать нельзя это точно, потому что в первом кругу должно быть 3 чела, а у каждого из них может быть еще только 2 друга, поэтому во втором кругу должно быть максимум 6. 1+3+6 = 10.
Первый ответ достаточен КМК. В условии "Оказалось, что у каждого члена клуба не более трех знакомых в этом клубе." Все зачем то пытаются построить полносвязанный граф.
>
> Первый ответ достаточен КМК. В условии "Оказалось, что у каждого члена клуба не более трех знакомых в этом клубе." Все зачем то пытаются построить полносвязанный граф.
Не достаточен, потому что надо ещё найти эту 10-ку, а как я сказал выше, если в условии там не через двоих дружба а через троих или четверых, то верхняя оценка уже становится недостижимой, тупо по перебору.
Это вообще случайно что когда строим граф то приходится использовать все рёбра чтобы достичь 10-ки :)
Сейчас, сейчас
надзор »
[censored]