Страница 54 номер 84, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Дан граф (рис. 45). Какое наименьшее число рёбер нужно удалить из графа, чтобы оставшийся подграф был эйлеровым графом? Приведите пример.
Связный конечный граф является эйлеровым тогда и только тогда, когда в нём не больше двух вершин нечётной степени. Удаление одного ребра уменьшает на 1 степени двух его концов, то есть меняет чётность ровно у двух вершин.
а) Восемь вершин \(A\), \(B\), \(C\), \(D\), \(K\), \(L\), \(M\), \(N\) и 14 рёбер: \(AD\), \(DN\), \(NK\), \(KA\), \(BC\), \(CM\), \(ML\), \(LB\), \(AB\), \(DC\), \(NM\), \(KL\) и две диагонали \(BN\) и \(KC\). Степени вершин: \(A\) — 3, \(B\) — 4, \(C\) — 4, \(D\) — 3, \(K\) — 4, \(L\) — 3, \(M\) — 3, \(N\) — 4.
Вершин нечётной степени четыре: \(A\), \(D\), \(L\), \(M\). Их больше двух, поэтому сам граф эйлеровым не является и хотя бы одно ребро удалить придётся.
Одного ребра достаточно. Удалим ребро \(AD\): степени вершин \(A\) и \(D\) станут равны 2, остальные не изменятся, и вершинами нечётной степени останутся только \(L\) и \(M\). Подграф связен: от \(A\) до \(D\) ведёт путь \(ABCD\), а все остальные вершины по-прежнему соединены рёбрами куба. Значит, он эйлеров.
б) Шесть вершин \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) и 10 рёбер: \(EA\), \(AF\), \(AB\), \(BC\), \(BD\), \(EC\), \(DF\), \(CF\), \(DE\), \(EF\). Степени вершин: \(A\) — 3, \(B\) — 3, \(C\) — 3, \(D\) — 3, \(E\) — 4, \(F\) — 4.
Вершин нечётной степени снова четыре: \(A\), \(B\), \(C\), \(D\). Их больше двух, поэтому и здесь без удаления не обойтись.
Удалим ребро \(AB\): степени вершин \(A\) и \(B\) станут равны 2, и вершинами нечётной степени останутся только \(C\) и \(D\). Подграф связен: вершина \(A\) соединена рёбрами \(EA\) и \(AF\) с вершинами \(E\) и \(F\), вершина \(B\) — рёбрами \(BC\) и \(BD\) с вершинами \(C\) и \(D\), а вершины \(C\), \(D\), \(E\), \(F\) связаны между собой рёбрами \(EC\), \(DF\), \(CF\), \(DE\), \(EF\). Значит, он эйлеров.
Ответ: а) наименьшее число рёбер — одно, например ребро \(AD\); б) наименьшее число рёбер — одно, например ребро \(AB\).
Дан граф (рис. 45). Какое наименьшее число рёбер нужно удалить из графа, чтобы оставшийся подграф был эйлеровым графом? Приведите пример.
Связный конечный граф является эйлеровым тогда и только тогда, когда в нём не больше двух вершин нечётной степени. Удаление одного ребра уменьшает на 1 степени двух его концов, поэтому чётность меняется ровно у двух вершин.
а) В графе восемь вершин \(A\), \(B\), \(C\), \(D\), \(K\), \(L\), \(M\), \(N\) и 14 рёбер: \(AD\), \(DN\), \(NK\), \(KA\), \(BC\), \(CM\), \(ML\), \(LB\), \(AB\), \(DC\), \(NM\), \(KL\) и две диагонали \(BN\) и \(KC\).
Степени вершин: \(A\) — 3, \(B\) — 4, \(C\) — 4, \(D\) — 3, \(K\) — 4, \(L\) — 3, \(M\) — 3, \(N\) — 4.
Вершин нечётной степени четыре: \(A\), \(D\), \(L\), \(M\). Их больше двух, поэтому сам граф эйлеровым не является и хотя бы одно ребро удалить придётся.
Одного ребра достаточно. Удалим ребро \(AD\): степени вершин \(A\) и \(D\) станут равны 2, остальные степени не изменятся, и вершинами нечётной степени останутся только \(L\) и \(M\). Подграф связен: от \(A\) до \(D\) ведёт путь \(ABCD\), а все остальные вершины по-прежнему соединены рёбрами куба.
Значит, в подграфе ровно две вершины нечётной степени и он связен, поэтому он эйлеров.
б) В графе шесть вершин \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) и 10 рёбер: \(EA\), \(AF\), \(AB\), \(BC\), \(BD\), \(EC\), \(DF\), \(CF\), \(DE\), \(EF\).
Степени вершин: \(A\) — 3, \(B\) — 3, \(C\) — 3, \(D\) — 3, \(E\) — 4, \(F\) — 4.
Вершин нечётной степени снова четыре: \(A\), \(B\), \(C\), \(D\). Их больше двух, поэтому и здесь без удаления не обойтись.
Удалим ребро \(AB\): степени вершин \(A\) и \(B\) станут равны 2, и вершинами нечётной степени останутся только \(C\) и \(D\). Подграф связен: вершина \(A\) соединена рёбрами \(EA\) и \(AF\) с вершинами \(E\) и \(F\), вершина \(B\) — рёбрами \(BC\) и \(BD\) с вершинами \(C\) и \(D\), а вершины \(C\), \(D\), \(E\), \(F\) связаны между собой рёбрами \(EC\), \(DF\), \(CF\), \(DE\), \(EF\).
Значит, в подграфе ровно две вершины нечётной степени и он связен, поэтому он эйлеров.
Ответ: а) наименьшее число рёбер — одно, например ребро \(AD\); б) наименьшее число рёбер — одно, например ребро \(AB\).
