3. На рисунке изображён граф. Марта обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды. С какой вершины Марта начала обводить граф, если она закончила его обводить в вершине А?

Question

Вопрос:

Фото задания: 3. На рисунке изображён граф. Марта обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды.…

3. На рисунке изображён граф. Марта обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды. С какой вершины Марта начала обводить граф, если она закончила его обводить в вершине А?

Accepted Answer

Краткое пояснение:

Правило: Граф можно обойти, не отрывая карандаша и не проводя ребро дважды, если он содержит не более двух вершин с нечетной степенью. Если таких вершин две, обход начинается с одной из них и заканчивается в другой.

Пошаговое решение:

Определяем степень каждой вершины (количество ребер, исходящих из нее):
- A: 3 (нечетная)
- B: 2 (четная)
- C: 4 (четная)
- D: 2 (четная)
- E: 1 (нечетная)
- F: 2 (четная)
- G: 2 (четная)
- H: 2 (четная)
- K: 2 (четная)
- L: 2 (четная)
В графе две вершины с нечетной степенью: A (3) и E (1).
Так как Марта закончила обводить граф в вершине А, а таких вершин может быть только две, то она должна была начать с вершины E.

Ответ: E