|
Докажите, что если в доме есть одна наружная дверь, то в нем найдется комната с нечетным количеством дверей. Согласно подсказке сначала нужно построить подходящий граф, затем начать удалять все простые циклы до тех пор пока граф не превратится в лес, а затем использовать тот факт, что у любого дерева есть по меньшей мере 2 листа при условии что кол-во вершин не меньше двух. Как это все можно оформить математическим языком? задан 12 Окт '15 23:51 
Joaquín |
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
12 Окт '15 23:51
показан
891 раз
обновлен
13 Окт '15 3:00
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
@Vinster: тут всё ещё проще. Есть "лемма о рукопожатиях", согласно которой сумма всех валентностей (степеней) вершин конечного графа чётна. У нас есть одна внешняя вершина степени 1. Значит, найдётся ещё одна нечётная, а это и будет соответствовать комнате с нечетным количеством дверей. С удалением циклов тоже можно (тогда так и надо объяснять -- обычными словами), но это сложнее.
@falcao а если через циклы то каким должен быть этот подходящий граф?
@Vinster: вспомогательный граф строится в любом случае. Вершины -- комнаты, а также площадка перед входом. Рёбра соответствуют дверям. Рисуем вершины в виде точек, потом соединяем их, как если бы мы прошли через дверь.
@falcao но мы же не знаем сколько комнат в доме и как они связаны друг с другом. Мне кажется проще и логичнее доказать тем способом что вы посоветовали. Доказать от противного, то есть сделать предположение что в доме все все комнаты с четным кол-вом дверей. Обозначить комнату за вершину а дверь за ребро. По условию у нас есть одна вершина с одним ребром (входная дверь) далее используем тот факт что в любом графе сумма всех степеней четна. В нашем случае степень это кол-во дверей у комнаты. И так как у вас уже есть одна дверь в дом (нечетная степень) то по теореме найдется комната с неч. дв.
@Vinster: конечно, не знаем, но мы же ничего не рисуем, а только описываем. Комнат конечное число, и граф всё равно существует. Тот, кто знает план дома, его легко нарисует. Хотя мой способ и проще, но он относится всё равно к тому же графу, а иначе не к чему применять лемму.