Задачи на графы 1 На плоскости расположено конечное число точек, из которых никакие 3 не лежат на одной прямой. Некоторые пары точек соединены отрезками. Докажите, что существуют две точки, из которых выходит одно и то же число отрезков.
Задачи на графы 1 На плоскости расположено конечное число точек, из которых никакие 3 не лежат на одной прямой. Некоторые пары точек соединены отрезками. Докажите, что существуют две точки, из которых выходит одно и то же число отрезков.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Предположим, что утверждение неверно. То есть, из каждой точки выходит разное число отрезков. Рассмотрим точку с наименьшим числом выходящих из нее отрезков. Пусть из нее выходит k отрезков. Так как из всех точек выходит разное число отрезков, то все остальные точки соединены ровно с k+1 точкой. Так как никакие три точки не лежат на одной прямой, образуется правильный многоугольник со всеми точками, за исключением точки, из которой выходит k отрезков. Таким образом, все k+1 вершин правильного многоугольника лежат на одной окружности. Противоречие, так как правильный многоугольник с нечетным числом вершин не может лежать на одной окружности. Следовательно, изначальное предположение неверно и существуют две точки, из которых выходит одинаковое число отрезков.