Страница 56 номер 72, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
Какие из графов, изображённых на рисунке 40, содержат эйлеровы циклы? Найдите эти циклы.
Обозначим вершины: \(A\) — верхняя, \(B\) — правая верхняя, \(C\) — левая, \(D\) — правая нижняя, \(E\) — нижняя. Все три графа связны, поэтому эйлеров цикл есть там, где все степени чётные.
а) Проведены все 10 рёбер: \(AB\), \(AC\), \(AD\), \(AE\), \(BC\), \(BD\), \(BE\), \(CD\), \(CE\), \(DE\); каждая вершина соединена с четырьмя остальными, все пять степеней равны 4 — чётные, эйлеров цикл есть. Проверка суммы: \(4 \cdot 5 = 20 = 2 \cdot 10\).
Цикл \(A\,B\,C\,D\,E\,A\,C\,E\,B\,D\,A\) — все 10 рёбер по одному разу, начало и конец в вершине \(A\).
б) Здесь 8 рёбер: \(AB\), \(AC\), \(BC\), \(BD\), \(BE\), \(CD\), \(CE\), \(DE\). Степени вершин: \(A\) — 2, \(B\) — 4, \(C\) — 4, \(D\) — 3, \(E\) — 3. Проверка суммы: \(2 + 4 + 4 + 3 + 3 = 16 = 2 \cdot 8\).
Нечётные степени у двух вершин, \(D\) и \(E\), поэтому эйлерова цикла нет; есть только эйлеров путь с началом и концом в \(D\) и \(E\), например, \(D\,B\,A\,C\,B\,E\,C\,D\,E\).
в) Здесь 7 рёбер: \(AB\), \(AC\), \(BC\), \(BD\), \(BE\), \(CD\), \(CE\). Степени вершин: \(A\) — 2, \(B\) — 4, \(C\) — 4, \(D\) — 2, \(E\) — 2. Проверка суммы: \(2 + 4 + 4 + 2 + 2 = 14 = 2 \cdot 7\).
Все степени чётные, эйлеров цикл есть: \(A\,B\,D\,C\,E\,B\,C\,A\) — все 7 рёбер по одному разу, начало и конец в вершине \(A\).
Ответ: эйлеровы циклы есть у графов а) и в): в графе а) это цикл \(A\,B\,C\,D\,E\,A\,C\,E\,B\,D\,A\), в графе в) — цикл \(A\,B\,D\,C\,E\,B\,C\,A\); в графе б) эйлерова цикла нет, так как вершины \(D\) и \(E\) имеют нечётные степени 3.
Какие из графов, изображённых на рисунке 40, содержат эйлеровы циклы? Найдите эти циклы.
На рисунке вершины не подписаны, поэтому обозначим их сами: \(A\) — верхняя вершина, \(B\) — правая верхняя, \(C\) — левая, \(D\) — правая нижняя, \(E\) — нижняя.
Эйлеров цикл — это цикл, содержащий все рёбра. По теореме Эйлера в связном графе он существует тогда и только тогда, когда все вершины имеют чётные степени. Все три графа связны, поэтому в каждом достаточно посмотреть на степени вершин.
а) Здесь проведены все 10 рёбер: \(AB\), \(AC\), \(AD\), \(AE\), \(BC\), \(BD\), \(BE\), \(CD\), \(CE\), \(DE\). Каждая вершина соединена с четырьмя остальными, значит, все пять степеней равны 4 — числа чётные, и эйлеров цикл есть. Проверка суммы: \(4 \cdot 5 = 20 = 2 \cdot 10\).
Найдём этот цикл: \(A\,B\,C\,D\,E\,A\,C\,E\,B\,D\,A\). В нём пройдены рёбра \(AB\), \(BC\), \(CD\), \(DE\), \(EA\), \(AC\), \(CE\), \(EB\), \(BD\), \(DA\) — все 10 рёбер, каждое по одному разу, начало и конец в вершине \(A\).
б) Здесь 8 рёбер: \(AB\), \(AC\), \(BC\), \(BD\), \(BE\), \(CD\), \(CE\), \(DE\). Степени вершин: \(A\) — 2, \(B\) — 4, \(C\) — 4, \(D\) — 3, \(E\) — 3. Проверка суммы: \(2 + 4 + 4 + 3 + 3 = 16 = 2 \cdot 8\).
Две вершины, \(D\) и \(E\), имеют нечётные степени, поэтому эйлерова цикла в этом графе нет. Есть только эйлеров путь — незамкнутый маршрут по всем рёбрам с началом и концом в \(D\) и \(E\), например, \(D\,B\,A\,C\,B\,E\,C\,D\,E\). Вернуться по нему в исходную вершину не удаётся.
в) Здесь 7 рёбер: \(AB\), \(AC\), \(BC\), \(BD\), \(BE\), \(CD\), \(CE\). Степени вершин: \(A\) — 2, \(B\) — 4, \(C\) — 4, \(D\) — 2, \(E\) — 2. Проверка суммы: \(2 + 4 + 4 + 2 + 2 = 14 = 2 \cdot 7\).
Все степени чётные, значит, эйлеров цикл есть: \(A\,B\,D\,C\,E\,B\,C\,A\). В нём пройдены рёбра \(AB\), \(BD\), \(DC\), \(CE\), \(EB\), \(BC\), \(CA\) — все 7 рёбер, каждое по одному разу, начало и конец в вершине \(A\).
Ответ: эйлеровы циклы есть у графов а) и в): в графе а) это цикл \(A\,B\,C\,D\,E\,A\,C\,E\,B\,D\,A\), в графе в) — цикл \(A\,B\,D\,C\,E\,B\,C\,A\); в графе б) эйлерова цикла нет, так как вершины \(D\) и \(E\) имеют нечётные степени 3.
