Таблицы Брадиса

Например, для компании из пяти

Например, для компании из пяти

Элементы математики в задачах - Г. А. Мерзон

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

134                                    Теория графов 1

попарно знакомых людей. Если же все Сашины знакомые незнакомы друг с другом, то они образуют тройку попарно незнакомых людей этой компании.

Ш Эта задача — важный частный случай теоремы Рамсея, первый пример содержательного рассуждения на графах. Важно научиться логически стройно проводить доказательства на графах.

Задача 5. Пусть в некоторой компании среди любых трех человек найдутся два друга. Обязательно ли эту компанию можно разбить на две группы, так что всякие два человека из одной группы — друзья?

Ответ. Нет, не обязательно.

Решение. Например, для компании из пяти человек, знакомых «по кругу» (А с Б, Б с В, В с Г, Г с Д, Д с А), условие задачи выполнено, а разбить ее указанным способом на две группы невозможно.

Задача 6. Найти наибольшее возможное количество ребер в графе с п вершинами, если известно, что среди произвольных трех его вершин есть две, не соединенные ребром.

Решение. Немного поэкспериментировав, можно обнаружить, что п нарисованных на бумаге точек удается соединить наибольшим ко­личеством отрезков, как просят в задаче (то есть так, чтобы среди произвольных трех всегда были бы две, не соединенные ребром), следующим образом: надо поделить множество точек на две «при­мерно равные» группы и затем соединить каждую точку из первой группы со всеми точками второй группы. Поясним, что мы имеем ввиду, когда говорим «примерно равные»: если точек было 2к, то мы разбиваем на две группы по к точек в каждой; если же у нас была нарисована 2к + 1 точка, то в одной группе должно быть к точек, а в другой к +1.