Часть 1 вопросы страница 91, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого: вероятность и статистика

1. Что такое эйлеров путь и какие графы называют эйлеровыми?

Эйлеров путь — это путь, проходящий ровно один раз по каждому ребру графа. Граф, в котором существует эйлеров путь, называется эйлеровым.

2. Может ли эйлеров граф быть несвязным?

Нет, не может. Эйлеров путь проходит по всем рёбрам графа, а значит, он связывает все вершины, имеющие рёбра, между собой. Если бы граф был несвязным (имел хотя бы две компоненты связности с рёбрами), то путь не смог бы перейти из одной компоненты в другую, и какие-то рёбра остались бы непройденными. Следовательно, эйлеров граф обязательно связный.

3. Может ли в эйлеровом графе не быть вершин нечётной степени? Может ли быть только одна вершина нечётной степени; две; три или больше?

• Ноль вершин нечётной степени — да, может. Если все вершины имеют чётную степень, то эйлеров путь существует, причём начало и конец пути совпадают (как на рис. 33, б).

• Одна вершина нечётной степени — нет, не может. Сумма степеней всех вершин графа равна удвоенному числу рёбер, то есть всегда чётна. Если бы была ровно одна вершина с нечётной степенью, а все остальные — с чётной, то сумма степеней была бы нечётной. Противоречие. Значит, одна вершина нечётной степени невозможна ни в каком графе.

• Две вершины нечётной степени — да, может. Эйлеров путь начинается в одной из них и заканчивается в другой (как на рис. 33, а).

• Три или больше вершин нечётной степени — нет, не может. По теореме Эйлера, если в графе существует эйлеров путь, то в нём не больше двух вершин нечётной степени. Значит, при трёх и более вершинах нечётной степени граф не является эйлеровым.