На рисунке изображён граф. Пётр обвёл этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Пётр начал обводить граф, если он…
На рисунке изображён граф. Пётр обвёл этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Пётр начал обводить граф, если он закончил его обводить в вершине 3 3
Для решения данной задачи, где Пётр обвел граф не отрывая карандаша от бумаги и не проводя по ребру дважды, можно воспользоваться следующим методом:
Найти вершину в графе, у которой нечетная степень. Такая вершина обязательно существует, так как если все вершины в графе имеют четную степень, то можно было бы пуститься в обход от любой вершины и вернуться обратно к ней без повторения ребер, что противоречит условию задачи.
Начнем обход графа с вершины, у которой нечетная степень, и продолжим обход, пока не посетим все ребра.
Таким образом, чтобы найти, с какой вершины Пётр начал обводить граф, нужно исследовать степени вершин в графе. Определим нечетные степени вершин:
- Вершина 1: 3 ребра инцидентны
- Вершина 2: 2 ребра инцидентны
- Вершина 3: 3 ребра инцидентны
Таким образом, вершина 1 имеет нечетную степень, и Пётр начал обводить граф с вершины 1.
