Вопросы после параграфа §11 на странице 53, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Путь в графе, проходящий ровно по одному разу через каждое ребро, называется эйлеровым путём; замкнутый эйлеров путь, у которого начало и конец совпадают, называется эйлеровым циклом.
Связный граф называется эйлеровым, если в нём существует эйлеров путь. Именно эйлеровы графы можно обвести «одним росчерком пера»: не отрывая карандаша от бумаги и не проводя ни одну линию дважды.
Ответ: эйлеров путь — это путь, проходящий ровно по одному разу через каждое ребро графа; эйлеровым называется связный граф, в котором такой путь существует.
Нет, не может: связность входит в само определение — эйлеровым называется связный граф, в котором есть эйлеров путь.
Требование связности не лишнее. Соседние вершины пути соединены ребром, поэтому весь путь целиком лежит в одной компоненте связности: два ребра из разных компонент одним путём не обойти, и эйлерова пути в таком графе нет вовсе. А если все рёбра лежат в одной компоненте, а остальные вершины изолированы, то путь через все рёбра найтись может, но эйлеровым такой граф не называют — он не связен.
Ответ: нет, не может: по определению эйлеров граф связен.
Вершин нечётной степени может не быть вовсе. Пример — треугольник \(ABC\) с рёбрами \(AB\), \(BC\), \(CA\): степень каждой вершины равна 2, граф связный, а путь \(ABCA\) проходит по каждому ребру ровно один раз — это эйлеров цикл.
Ровно одной вершины нечётной степени не бывает ни в одном графе: сумма степеней всех вершин равна удвоенному числу рёбер и потому чётна, а при единственной вершине нечётной степени она оказалась бы нечётной. Значит, вершин нечётной степени всегда чётное число.
Две вершины нечётной степени быть могут. Пример — цепь \(ABC\) из рёбер \(AB\) и \(BC\): степени вершин \(A\) — 1, \(B\) — 2, \(C\) — 1, и путь \(ABC\) проходит по каждому ребру ровно один раз.
Трёх и более вершин нечётной степени в эйлеровом графе быть не может: связный конечный граф является эйлеровым тогда и только тогда, когда в нём не больше двух вершин нечётной степени.
Ответ: вершин нечётной степени в эйлеровом графе может не быть вовсе (тогда в нём есть эйлеров цикл), а может быть ровно две; ровно одна вершина нечётной степени невозможна ни в каком графе, а трёх и более в эйлеровом графе не бывает.
Путь в графе, проходящий ровно по одному разу через каждое ребро, называется эйлеровым путём. Если эйлеров путь замкнутый, то есть его начало и конец совпадают, то он называется эйлеровым циклом.
Связный граф называется эйлеровым, если в нём существует эйлеров путь.
Именно эйлеровы графы можно обвести «одним росчерком пера»: не отрывая карандаша от бумаги и не проводя ни одну линию дважды. Например, в треугольнике \(ABC\) путь \(ABCA\) проходит по каждому из трёх рёбер ровно один раз, поэтому треугольник — эйлеров граф.
Ответ: эйлеров путь — это путь, проходящий ровно по одному разу через каждое ребро графа; эйлеровым называется связный граф, в котором такой путь существует.
Нет, не может: связность входит в само определение — эйлеровым называется связный граф, в котором есть эйлеров путь.
Требование связности здесь не лишнее. Пусть в графе есть два ребра, лежащие в разных компонентах связности. Соседние вершины пути соединены ребром, поэтому весь путь целиком лежит в одной компоненте связности, и одним путём эти два ребра не обойти — эйлерова пути в таком графе нет вовсе.
Остаётся случай, когда все рёбра лежат в одной компоненте, а остальные вершины изолированы. Путь через все рёбра тогда найтись может, но эйлеровым такой граф не называют: он не связен.
Ответ: нет, не может: по определению эйлеров граф связен.
Вершин нечётной степени может не быть вовсе. Пример — треугольник \(ABC\) с рёбрами \(AB\), \(BC\), \(CA\): степень каждой вершины равна 2, граф связный, а путь \(ABCA\) проходит по каждому ребру ровно один раз. Это эйлеров цикл, и граф эйлеров.
Ровно одной вершины нечётной степени не бывает ни в одном графе — не только в эйлеровом. Сумма степеней всех вершин равна удвоенному числу рёбер, то есть чётна. Если бы вершина нечётной степени была ровно одна, то сумма степеней всех вершин оказалась бы нечётной. Значит, вершин нечётной степени всегда чётное число, и одна такая вершина невозможна.
Две вершины нечётной степени быть могут. Пример — цепь \(ABC\) из двух рёбер \(AB\) и \(BC\): степени вершин \(A\) — 1, \(B\) — 2, \(C\) — 1, нечётных ровно две, и путь \(ABC\) проходит по каждому ребру ровно один раз.
Трёх и более вершин нечётной степени в эйлеровом графе быть не может: связный конечный граф является эйлеровым тогда и только тогда, когда в нём не больше двух вершин нечётной степени.
Ответ: вершин нечётной степени в эйлеровом графе может не быть вовсе (тогда в нём есть эйлеров цикл), а может быть ровно две; ровно одна вершина нечётной степени невозможна ни в каком графе, а трёх и более в эйлеровом графе не бывает.
