На рисунке изображён граф. Катя обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды. Начала она в верише C. В какой вершине Катя закончила…
На рисунке изображён граф. Катя обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды. Начала она в верише C. В какой вершине Катя закончила обводить граф?
Для решения этой задачи можно воспользоваться понятием степени вершины. По условию известно, что Катя начала обводить граф в вершине C.
В неориентированном графе степень вершины равна количеству инцидентных ей рёбер. Важным наблюдением является то, что если у вершины нечётная степень, то такая вершина обязательно будет начальной и конечной точкой пути. В то же время, чётная степень позволяет пройти через вершину как начать, так и закончить путь в ней, не нарушая условий задачи Кати.
Таким образом, чтобы понять, где Катя закончила обводить граф, необходимо найти вершину с нечётной степенью. Посмотрим на степени вершин графа:
- Вершина A: степень 3
- Вершина B: степень 4
- Вершина C: степень 4
- Вершина D: степень 3
- Вершина E: степень 2
Таким образом, у вершин A, C и D нечётные степени. Но так как Катя начала в вершине C, а это начало и конец пути, значит, она закончила обводить граф в вершине C.
Итак, Катя закончила обводить граф в вершине C.
