на рисунке изображён граф.Катя обвела его не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды. Начала она в вершине B.В какой вершине Катя закончила обводить…
На рисунке изображён граф.Катя обвела его не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды. Начала она в вершине B.В какой вершине Катя закончила обводить граф?
Для решения этой задачи, нам нужно понять некоторые основные свойства графов:
Степень вершины: В графе степень вершины обозначает количество рёбер, исходящих из данной вершины.
Свойство закона Хэндшейка: Сумма степеней всех вершин графа равна удвоенному числу рёбер в графе.
Теперь, посмотрим на граф на заданном изображении:
Начало: Катя начала рисовать граф в вершине B.
Характер движения: Поскольку Катя не отрывала карандаш от листа бумаги и не проходила ни одно ребро дважды, значит она обходила каждую вершину только один раз. Это означает, что при возвращении в вершину, в которой она начала рисовать, обводка завершится.
Свойство закона Хэндшейка: Поскольку сумма степеней всех вершин графа равна удвоенному числу рёбер в графе, и каждая вершина, кроме B, должна иметь четную степень, чтобы Катя могла вернуться в вершину B.
Исходя из этого, можем сделать вывод, что Катя завершила обвод графа в вершине B.
Таким образом, вершина, в которой Катя закончила обводить граф, - вершина B.
