Страница 54 номер 85, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Какой максимальный по числу рёбер эйлеров подграф можно выделить в данном графе (рис. 46)?
Связный конечный граф является эйлеровым тогда и только тогда, когда в нём не больше двух вершин нечётной степени.
а) Шесть вершин \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) и 10 рёбер: \(AD\), \(FB\), \(AE\), \(AC\), \(DF\), \(DB\), \(EF\), \(CB\), \(EB\), \(CF\). Степени вершин: \(A\) — 3, \(B\) — 4, \(C\) — 3, \(D\) — 3, \(E\) — 3, \(F\) — 4.
Проверка: сумма степеней \(3 + 4 + 3 + 3 + 3 + 4 = 20\), то есть удвоенное число рёбер.
Вершин нечётной степени четыре: \(A\), \(C\), \(D\), \(E\), — значит, подграф из всех 10 рёбер не годится.
Удалим ребро \(AD\): степени вершин \(A\) и \(D\) станут равны 2, и вершинами нечётной степени останутся только \(C\) и \(E\). Подграф связен: вершина \(A\) соединена рёбрами \(AE\) и \(AC\), вершина \(D\) — рёбрами \(DF\) и \(DB\), а вершины \(B\), \(C\), \(E\), \(F\) связаны рёбрами \(FB\), \(EF\), \(CB\), \(EB\), \(CF\). Подграф из 9 рёбер эйлеров, а больше взять нельзя: единственный подграф с 10 рёбрами — сам граф.
б) Шесть вершин \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) и 11 рёбер: \(AB\), \(BC\), \(CD\), \(AD\), \(BE\), \(AE\), \(ED\), \(EC\), \(EF\), \(FC\), \(BF\). Степени вершин: \(A\) — 3, \(B\) — 4, \(C\) — 4, \(D\) — 3, \(E\) — 5, \(F\) — 3.
Проверка: сумма степеней \(3 + 4 + 4 + 3 + 5 + 3 = 22\), то есть удвоенное число рёбер.
Вершин нечётной степени снова четыре: \(A\), \(D\), \(E\), \(F\), — весь граф не эйлеров.
Удалим ребро \(AD\): степени вершин \(A\) и \(D\) станут равны 2, и вершинами нечётной степени останутся только \(E\) и \(F\). Подграф связен: вершина \(A\) соединена рёбрами \(AB\) и \(AE\), вершина \(D\) — рёбрами \(CD\) и \(ED\), а вершины \(B\), \(C\), \(E\), \(F\) связаны рёбрами \(BC\), \(BE\), \(EC\), \(EF\), \(FC\), \(BF\). Подграф из 10 рёбер эйлеров, а больше взять нельзя: единственный подграф с 11 рёбрами — сам граф.
Ответ: а) 9 рёбер — например, весь граф без ребра \(AD\); б) 10 рёбер — например, весь граф без ребра \(AD\).
Какой максимальный по числу рёбер эйлеров подграф можно выделить в данном графе (рис. 46)?
Связный конечный граф является эйлеровым тогда и только тогда, когда в нём не больше двух вершин нечётной степени. Удаление одного ребра меняет чётность степеней ровно у двух вершин — у его концов.
а) В графе шесть вершин \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) и 10 рёбер: \(AD\), \(FB\), \(AE\), \(AC\), \(DF\), \(DB\), \(EF\), \(CB\), \(EB\), \(CF\).
Степени вершин: \(A\) — 3, \(B\) — 4, \(C\) — 3, \(D\) — 3, \(E\) — 3, \(F\) — 4.
Проверка: сумма степеней равна \(3 + 4 + 3 + 3 + 3 + 4 = 20\), то есть удвоенному числу рёбер.
Вершин нечётной степени четыре: \(A\), \(C\), \(D\), \(E\). Их больше двух, поэтому весь граф эйлеровым не является и подграф из всех 10 рёбер не годится.
Возьмём подграф из 9 рёбер: удалим ребро \(AD\). Степени вершин \(A\) и \(D\) станут равны 2, и вершинами нечётной степени останутся только \(C\) и \(E\). Подграф связен: вершина \(A\) соединена рёбрами \(AE\) и \(AC\), вершина \(D\) — рёбрами \(DF\) и \(DB\), а вершины \(B\), \(C\), \(E\), \(F\) связаны рёбрами \(FB\), \(EF\), \(CB\), \(EB\), \(CF\). Значит, этот подграф эйлеров.
Больше 9 рёбер взять нельзя: единственный подграф с 10 рёбрами — сам граф, а он не эйлеров.
б) В графе шесть вершин \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) и 11 рёбер: \(AB\), \(BC\), \(CD\), \(AD\), \(BE\), \(AE\), \(ED\), \(EC\), \(EF\), \(FC\), \(BF\).
Степени вершин: \(A\) — 3, \(B\) — 4, \(C\) — 4, \(D\) — 3, \(E\) — 5, \(F\) — 3.
Проверка: сумма степеней равна \(3 + 4 + 4 + 3 + 5 + 3 = 22\), то есть удвоенному числу рёбер.
Вершин нечётной степени снова четыре: \(A\), \(D\), \(E\), \(F\). Их больше двух, поэтому весь граф не эйлеров.
Возьмём подграф из 10 рёбер: удалим ребро \(AD\). Степени вершин \(A\) и \(D\) станут равны 2, и вершинами нечётной степени останутся только \(E\) и \(F\). Подграф связен: вершина \(A\) соединена рёбрами \(AB\) и \(AE\), вершина \(D\) — рёбрами \(CD\) и \(ED\), а вершины \(B\), \(C\), \(E\), \(F\) связаны рёбрами \(BC\), \(BE\), \(EC\), \(EF\), \(FC\), \(BF\). Значит, этот подграф эйлеров.
Больше 10 рёбер взять нельзя: единственный подграф с 11 рёбрами — сам граф, а он не эйлеров.
Ответ: а) 9 рёбер — например, весь граф без ребра \(AD\); б) 10 рёбер — например, весь граф без ребра \(AD\).
