Распечатать запись Распечатать запись

Регулярные графы

Это продолжение темы о графах, начало смотрите здесь.

Определение. Граф, степени всех вершин которого одинаковы, называется регулярным.

Задача 1. В некоторой компании любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Докажите, что в этой компании все имеют одинаковое число знакомых.

Показать решение

Задача 2. В лагере отдыхают 50 школьников. Известно, что среди любых школьников найдется по крайней мере один, знакомый с тремя остальными. Докажите, что найдется школьник, знакомый со всеми остальными школьниками.

Показать решение

Задача 3. На конгресс собрались ученые, среди которых есть знакомые друг с другом. Оказалось, что никакие двое ученых, имеющих равное число знакомых, не имеют общих знакомых. Докажите, что найдется ученый, имеющий ровно одного знакомого.

Показать решение

Задача 4. В трехмерном пространстве выбраны 8 точек так, что никакие три из них не лежат на одной прямой. Проведено 17 отрезков с концами в выбранных точках. Докажите, что найдутся три отрезка, образующие треугольник.

Показать решение

Источник: О.И. Мельников “Теория графов в занимательных задачах”, М.: Книжный дом “ЛИБРОКОМ”, 2011.

Оставьте свой отзыв

Добавить изображение