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

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