Задача Задача №3101823
А
А
Как провела этот граф, не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды. Начала она в вершине С. В какой вершине Катя закончила обводить граф
Для решения данной задачи, нам дано следующее условие: граф был обведен Катей, не поднимая карандаш. Изначально, карандаш был опущен на вершине C.
Чтобы разобраться, в какой вершине Катя закончила обводить граф, нужно понять особенности обхода вершин.
Четные и нечетные степени вершин графа:
- В неориентированных графах, степень вершины равна количеству инцидентных ей ребер.
- Если у вершины четная степень, то можно вернуться в нее по какому-либо ребру и продолжить обход графа.
- Если у вершины нечетная степень, то вернуться в нее по какому-либо ребру и продолжить обход графа не получится.
Остовные деревья:
- Граф, в котором обойдены все вершины, но не проходя дважды по одному и тому же ребру, называется остовным деревом.
Учет степеней вершин:
- Если каждая вершина графа имеет четную степень, то Катя может обойти граф, вернувшись в начальную вершину.
- Если какая-то вершина имеет нечетную степень, то Катя закончит обводить граф в вершине с нечетной степенью.
Исходя из этого, если граф неориентированный и у каждой вершины четная степень (то есть исходя из вершины С), то Катя закончит обводить граф в исходной вершине, в вершине C.
