Задача по теории графов

[cmdeltatx]

N (N>2) друзей приобрели по одному велосипеду. На каждом велосипеде было осуществлено по одной поездке вдвоем, но ни одна пара друзей не ездила вместе дважды. Оказалось, что 1 человек проехал на 2 велосипедах только тогда, если владельцы этих двух велосипедов ездили вместе. Сколько раз мог выезжать каждый из друзей?

[Kid Kool]

2

[cmdeltatx]

Та я то знаю, что ответ - ровно 2 раза , только как это доказать?

[Kid Kool]

Рассмотрим граф из N вершин, каждая из которых соответствует паре человек-велосипед, им купленный. Вершина A соединена направленной дугой с B, если человек A ездил на велосипеде B. По условию, в каждую вершину входит ровно 2 дуги. Кроме того, если из вершины K выходят дуги к X, Y, то X и Y должны иметь общего потомка (назовем его Z). Заметим, что разным {X, Y} соответсвтуют разные Z, поскольку других предков, кроме X и Y, у Z нет.

Далее, пусть число выходящих дуг из K равно d > 2. Тогда каждой паре потомков K (X, Y) соответствуют различные Z. Следовательно, из каждого потомка выходит не менее 2-ч дуг. Теперь вместо потомков перейдем к рассмотрению вершин ранга r (длина минимального пути из K равна r). Индукцией по r несложно доказывается, что вершин ранга r не менее 3-х, и степень каждой из них не менее 2-x.

Если рассмотреть подграф G(K) - достижимые из K вершины, которых будет, скажем, m, то можно заметить следующее: из каждой вершины выходит не менее 2-х дуг, а из K - не менее 3-х, значит всего ребер не менее 2m+1. С другой стороны, в каждую вершину входит не более 2-х дуг, значит, ребер не более 2m. Противоречие.

Таким образом, из каждой вершины выходит не более 2-х дуг. А т.к. входит ровно две, то и выходит - тоже ровно две (посчитаем общее число ребер как выше). Пример такого графа оставляется как несложное упражнение читателю : )))

[cmdeltatx]

Спасибо огромное!