Ответ:
Решение:
Для того чтобы обойти граф, не отрывая карандаша и не проводя ни одно ребро дважды, необходимо, чтобы граф был связным и имел не более двух вершин с нечетной степенью. Если в графе есть вершины с нечетной степенью, то обход должен начинаться в одной из них и заканчиваться в другой. Если все вершины имеют четную степень, то обход может начаться и закончиться в одной и той же вершине.
Подсчитаем степень каждой вершины (количество ребер, исходящих из нее):
- Степень вершины А: 2 (нечетная)
- Степень вершины B: 2 (четная)
- Степень вершины C: 2 (четная)
- Степень вершины D: 3 (нечетная)
- Степень вершины E: 2 (четная)
- Степень вершины F: 2 (четная)
- Степень вершины O: 4 (четная)
В графе две вершины с нечетной степенью: А и D.
Поскольку Катя начала обходить граф в вершине Д (вершина с нечетной степенью), она должна закончить обход в другой вершине с нечетной степенью.
Ответ: А
Решение:
Для того чтобы обойти граф, не отрывая карандаша и не проводя ни одно ребро дважды, необходимо, чтобы граф был связным и имел не более двух вершин с нечетной степенью. Если в графе есть вершины с нечетной степенью, то обход должен начинаться в одной из них и заканчиваться в другой. Если все вершины имеют четную степень, то обход может начаться и закончиться в одной и той же вершине.
Подсчитаем степень каждой вершины (количество ребер, исходящих из нее):
- Степень вершины А: 2 (нечетная)
- Степень вершины B: 2 (четная)
- Степень вершины C: 2 (четная)
- Степень вершины D: 3 (нечетная)
- Степень вершины E: 2 (четная)
- Степень вершины F: 2 (четная)
- Степень вершины O: 4 (четная)
В графе две вершины с нечетной степенью: А и D.
Поскольку Катя начала обходить граф в вершине Д (вершина с нечетной степенью), она должна закончить обход в другой вершине с нечетной степенью.
Ответ: А
