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

Это задача о графах, связанная с теорией Эйлеровых путей. Чтобы обойти граф, не отрывая карандаша и не проводя ребро дважды, нужно, чтобы количество вершин с нечетной степенью было равно 0 или 2.

Давайте определим степень каждой вершины (количество ребер, выходящих из нее):

• A: степень 3 (ребра А-B, A-F, A-E)
• B: степень 2 (ребра B-A, B-C)
• C: степень 2 (ребра C-B, C-D)
• D: степень 2 (ребра D-C, D-E)
• E: степень 3 (ребра E-A, E-D)
• F: степень 2 (ребра F-A) - *Ой, тут на рисунке F соединено только с A, но есть ещё один маленький контур AF, который можно рассматривать как одно ребро. Давайте считать, что F имеет степень 2 (AB, AF)*. Похоже, что F соединено с A дважды, если смотреть внимательно. Тогда степень F = 2.*

Пересчитаем степени вершин, учитывая, что петли (ребра, начинающиеся и заканчивающиеся в одной вершине) добавляют 2 к степени вершины, а ребро между двумя вершинами добавляет 1 к каждой из них.

На рисунке:

• A: ребра А-B, A-F, A-E. Степень = 3.
• B: ребра B-A, B-C. Степень = 2.
• C: ребра C-B, C-D. Степень = 2.
• D: ребра D-C, D-E. Степень = 2.
• E: ребра E-A, E-D. Степень = 2.
• F: ребро F-A, и кажется, есть еще петля или ребро FA. Если считать, что F соединено с A одним ребром, то степень F = 1. Если считать, что есть два ребра между F и A (как на рисунке), то степень F = 2. Но там изображен контур A-F, который, вероятно, является одним ребром.*

Давайте перерисуем и проанализируем еще раз:

Граф состоит из вершин A, B, C, D, E, F.

Ребра:

• (A, B)
• (A, E)
• (A, F)
• (B, C)
• (C, D)
• (D, E)

Теперь считаем степени вершин:

• A: 3 (AB, AE, AF)
• B: 2 (BA, BC)
• C: 2 (CB, CD)
• D: 2 (DC, DE)
• E: 2 (EA, ED)
• F: 1 (FA)

У нас есть две вершины с нечетной степенью: A (3) и F (1). Если в графе есть ровно две вершины с нечетной степенью, то Эйлеров путь существует и он начинается в одной из этих вершин и заканчивается в другой.

Нам дано, что Оля закончила обводить граф в вершине C. Это противоречит условию существования Эйлерова пути, так как C имеет четную степень (2). Возможно, я неправильно интерпретировал граф или условие.

Пересмотрим условие: