Последние новости
04.09.24
Объявление
09.06.24
Результаты Олимпиады
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
Графом называется рисунок, состоящий из точек (вершин), соединённых отрезками (рёбрами). При этом нам не важно, как именно нарисован граф, важно только, какие вершины как соединены.
Подграф, который получается из графа удалением одной вершины, назовём картой, а набор всех карт графа — колодой.
В задаче отборочного тура мы уже доказывали, что по колоде можно восстановить общее количество рёбер графа. Также легко доказать, что можно установить степени всех вершин (количество выходящих из неё рёбер): степень вершины, которой не хватает на карте — это в точности количество отсутствующих на ней рёбер.
Докажите, что граф, степени всех вершин которого чётны, однозначно восстанавливается по своей колоде.
В этой задаче в первую очередь оценивается текст решения. Картинки можно использовать для иллюстрации.
Обратите внимание! На сайте в домене .рф эта задача может отображаться некорректно. Воспользуйтесь другим сайтом
Рассмотрим графы в целом. Исходя из программы, я предполагаю, что построение графов, где две вершины может связывать два и более рёбер (если не ошибаюсь, они называются циклические (?), надеюсь, я не ошибаюсь), невозможно. В таком случае, если мы удаляем одну из вершин, то степени других вершин либо уменьшаются на 1, либо не изменяются. Однако если степень вершины уменьшилась на 1, то изменилась чётность степени вершины с чётной на нечётную. В таком случае, по любой произвольной карте колоды можно восстановить однозначно граф, так как нужно лишь добавить вершину, которая будет связана со всеми вершинами нечётной степени.