Составители:
Рубрика:
65
21.
Известно, что в компании каждый человек знаком не менее, чем с половиной
присутствующих. Докажите, что можно выбрать из компании четырех человек и
рассадить их за круглым столом так, что при этом каждый будет сидеть рядом со своими
знакомыми.
22.
Спортивные соревнования проводятся по круговой системе. Это означает, что каждая
пара игроков встречается между собой ровно один раз. Докажите, что в любой момент
времени найдутся хотя бы два игрока, проведшие одинаковое число встреч.
23.
Докажите, что в любом графе найдутся по крайней мере две вершины одинаковой
степени
24.
В футбольном турнире 20 команд сыграли 8 туров: каждая команда сыграла с 8 разными
командами. Докажите, что найдутся три команды, не сыгравшие между собой пока ни
одного матча.
25.
Про некоторую компанию известно, что каждый человек знаком в ней ровно с шестью
людьми и для любой группы из шести человек найдется член компании, знакомый с
каждым из этой шестерки. Сколько человек в компании?
26.
Докажите, что среди любых шести человек есть либо трое попарно знакомых, либо трое
попарно незнакомых.
27.
В международном фестивале участвовало несколько сотен делегатов из разных стран
мира. Выяснилось, что из любых трех делегатов по крайней мере двое смогут
объясниться между собой на каком-то языке. Докажите, что найдется тройка делегатов, в
которой каждый может объясниться с каждым.
Матрицы, ассоциированные с графом
28. Дана симметричная матрица размером n х n. В каждой строке расположено нечетное
число единиц, остальные элементы равны нулю. Элементы на главной диагонали равны
нулю. Доказать, что n является четным.
29.
Опишите матрицы смежности полных графов, вполне несвязных графов. Что можно
сказать о матрице простого графа и его дополнения?
30.
Изобразите матрицу смежности графа:
31.
Изобразите матрицу инцидентности графа.
Страницы
- « первая
- ‹ предыдущая
- …
- 63
- 64
- 65
- 66
- 67
- …
- следующая ›
- последняя »
