Можно ли подобрать компанию, в которой у каждого было бы ровно 5 друзей, а у каждого двух - ровно два общих друга? А если у каждого должно быть 6 друзей?

Добавлена: 01.05.2026
Обновлена: 01.05.2026
Предмет: Логика
Автор: Кэмп

#Математическая логика
#Теория множеств

Условие:

Можно ли подобрать компанию, в которой у каждого было бы ровно 5 друзей, а у каждого двух - ровно два общих друга?
А если у каждого должно быть 6 друзей?

Решение:

Рассмотрим задачу с точки зрения теории графов. Будем представлять компанию в виде графа, вершины которого – люди, а ребро между двумя вершинами означает, что эти люди друзья. Задача требует построить такой граф, что каждый узел имеет степень k (k = 5 в пункте а) и k = 6 в пункте б)) и для любых двух различных вершин число общих соседей равно постоянной c =
2.

Чтобы начать, посчитаем число вершин n с использованием двойного счета количества троек вершин, где одна вершина является общим соседом для пары других.

Если у каждого узла степень k, то у него есть C(k...

Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит

Попробуй решить по шагам

Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение

Какое из следующих утверждений верно относительно существования графа, где каждая вершина имеет степень k, и любые две вершины имеют ровно c общих соседей?

Такой граф всегда существует, если количество вершин n, вычисленное по формуле n = k(k-1)/c + 1, является целым числом.

Существование такого графа зависит от дополнительных условий, таких как целочисленность мультипликаторов собственных значений матрицы смежности, помимо формулы для n.

Такой граф не может существовать, так как условие о постоянном числе общих соседей для любых двух вершин слишком строго.