дано: Связный конечный граф, в котором ровно две вершины имеют нечётную степень.
найти: Показать, что любой эйлеров путь в этом графе должен начинаться в одной из этих вершин и заканчиваться в другой.
решение:
1. Эйлеров путь - это маршрут по графу, который проходит через каждое ребро ровно один раз. Он может начинаться и заканчиваться в разных вершинах, если в графе есть вершины с нечётной степенью.
2. Общее свойство степеней вершин:
- Если у вершины нечётная степень, то она является "входной" или "выходной" точкой для эйлерова пути. Это происходит потому, что при входе в вершину (через одно из рёбер) требуется выйти из неё (через другое ребро).
- Если у вершины чётная степень, то она может свободно быть частью пути, не являясь его начальной или конечной точкой.
3. В нашем случае:
- В графе ровно две вершины имеют нечётную степень.
- Следовательно, одна из этих двух вершин должна быть начальной точкой, а другая - конечной.
4. Поскольку мы начинаем путь в одной из нечётных вершин (откуда должны выйти), и завершаем его в другой нечётной вершине (куда должны войти), это подтверждает, что любой эйлеров путь начинается в одной из этих двух вершин и заканчивается в другой.
ответ: Если в связном конечном графе есть ровно две вершины с нечётной степенью, то любой эйлеров путь в этом графе начинается в одной из этих вершин и заканчивается в другой.