Страница 54 номер 87, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
На рисунке 48 изображён плоский граф. Существует ли ломаная, пересекающая все рёбра этого графа по одному разу?
Обозначим вершины: \(T\) — вершина на верхней стороне, \(L\) — на левой стороне, \(R\) — на правой, \(M_1\), \(M_2\), \(M_3\) — вершины на среднем горизонтальном отрезке слева направо, \(B_1\) и \(B_2\) — вершины на нижней стороне. Углы внешнего прямоугольника вершинами не являются: там рёбра просто изламываются.
Рёбра этого графа: \(LT\), \(TR\), \(TM_2\), \(LM_1\), \(M_1M_2\), \(M_2M_3\), \(M_3R\), \(LB_1\), \(M_1B_1\), \(B_1B_2\), \(M_3B_2\), \(B_2R\) — всего 12 рёбер. Граф связен и разбивает плоскость на шесть областей: пять конечных — верхнюю левую \(A\), верхнюю правую \(B\), нижнюю левую \(C\), нижнюю среднюю \(D\), нижнюю правую \(E\) — и внешнюю \(F\).
Каждой области сопоставим вершину нового графа, а каждому ребру исходного графа — ребро нового, соединяющее вершины тех двух областей, которые это ребро разделяет: \(LT\) — области \(A\) и \(F\); \(TR\) — \(B\) и \(F\); \(TM_2\) — \(A\) и \(B\); \(LM_1\) — \(A\) и \(C\); \(M_1M_2\) — \(A\) и \(D\); \(M_2M_3\) — \(B\) и \(D\); \(M_3R\) — \(B\) и \(E\); \(LB_1\) — \(C\) и \(F\); \(M_1B_1\) — \(C\) и \(D\); \(B_1B_2\) — \(D\) и \(F\); \(M_3B_2\) — \(D\) и \(E\); \(B_2R\) — \(E\) и \(F\).
Значит, в новом графе шесть вершин и 12 рёбер: \(AB\), \(AC\), \(AD\), \(AF\), \(BD\), \(BE\), \(BF\), \(CD\), \(CF\), \(DE\), \(DF\), \(EF\).
Степени вершин нового графа: \(A\) — 4, \(B\) — 4, \(C\) — 3, \(D\) — 5, \(E\) — 3, \(F\) — 5.
Проверка: сумма степеней \(4 + 4 + 3 + 5 + 3 + 5 = 24\), то есть удвоенное число рёбер.
Ломаная не проходит через вершины исходного графа, поэтому в каждый момент она находится внутри одной из областей, а, пересекая ребро, переходит в соседнюю область. Выпишем подряд области, по которым она идёт: каждые две соседние в этой записи разделены ребром, то есть соответствующие им вершины нового графа соединены ребром, — получился путь в новом графе. Каждое ребро исходного графа ломаная пересекает ровно один раз, поэтому этот путь проходит по каждому ребру нового графа ровно один раз, то есть является эйлеровым путём.
Новый граф связен: вершина \(A\) соединена рёбрами с \(B\), \(C\), \(D\) и \(F\), а вершина \(E\) — с \(B\). Но вершин нечётной степени в нём четыре: \(C\), \(D\), \(E\) и \(F\), а связный конечный граф является эйлеровым тогда и только тогда, когда в нём не больше двух вершин нечётной степени. Значит, эйлерова пути в новом графе нет, а следовательно, нет и ломаной, пересекающей каждое ребро исходного графа ровно один раз.
Ответ: нет, такой ломаной не существует.
На рисунке 48 изображён плоский граф. Существует ли ломаная, пересекающая все рёбра этого графа по одному разу?
Обозначим вершины: \(T\) — вершина на верхней стороне, \(L\) — на левой стороне, \(R\) — на правой, \(M_1\), \(M_2\), \(M_3\) — вершины на среднем горизонтальном отрезке слева направо, \(B_1\) и \(B_2\) — вершины на нижней стороне. Углы внешнего прямоугольника вершинами не являются: там рёбра просто изламываются.
Рёбра этого графа: \(LT\), \(TR\), \(TM_2\), \(LM_1\), \(M_1M_2\), \(M_2M_3\), \(M_3R\), \(LB_1\), \(M_1B_1\), \(B_1B_2\), \(M_3B_2\), \(B_2R\) — всего 12 рёбер.
Граф связен и разбивает плоскость на шесть областей: пять конечных — верхнюю левую, верхнюю правую, нижнюю левую, нижнюю среднюю и нижнюю правую — и внешнюю.
Построим новый граф: каждой области сопоставим вершину, а каждому ребру исходного графа — ребро нового графа, соединяющее вершины тех двух областей, которые это ребро разделяет.
Вершины нового графа обозначим так: \(A\) — верхняя левая область, \(B\) — верхняя правая, \(C\) — нижняя левая, \(D\) — нижняя средняя, \(E\) — нижняя правая, \(F\) — внешняя.
Каждое ребро исходного графа разделяет ровно две области: \(LT\) — области \(A\) и \(F\); \(TR\) — \(B\) и \(F\); \(TM_2\) — \(A\) и \(B\); \(LM_1\) — \(A\) и \(C\); \(M_1M_2\) — \(A\) и \(D\); \(M_2M_3\) — \(B\) и \(D\); \(M_3R\) — \(B\) и \(E\); \(LB_1\) — \(C\) и \(F\); \(M_1B_1\) — \(C\) и \(D\); \(B_1B_2\) — \(D\) и \(F\); \(M_3B_2\) — \(D\) и \(E\); \(B_2R\) — \(E\) и \(F\).
Значит, в новом графе шесть вершин и 12 рёбер: \(AB\), \(AC\), \(AD\), \(AF\), \(BD\), \(BE\), \(BF\), \(CD\), \(CF\), \(DE\), \(DF\), \(EF\).
Степени вершин нового графа: \(A\) — 4, \(B\) — 4, \(C\) — 3, \(D\) — 5, \(E\) — 3, \(F\) — 5.
Проверка: сумма степеней равна \(4 + 4 + 3 + 5 + 3 + 5 = 24\), то есть удвоенному числу рёбер.
Свяжем ломаную с новым графом. Ломаная не проходит через вершины исходного графа, поэтому в каждый момент она находится внутри одной из областей, а, пересекая ребро, переходит в соседнюю область. Выпишем подряд области, по которым она идёт. Каждые две соседние области в этой записи разделены ребром, то есть соответствующие им вершины нового графа соединены ребром, — получился путь в новом графе. Каждое ребро исходного графа ломаная пересекает ровно один раз, поэтому этот путь проходит по каждому ребру нового графа ровно один раз, то есть является эйлеровым путём.
Но в новом графе четыре вершины нечётной степени: \(C\), \(D\), \(E\) и \(F\). Новый граф связен: вершина \(A\) соединена рёбрами с \(B\), \(C\), \(D\) и \(F\), а вершина \(E\) — с \(B\). А связный конечный граф является эйлеровым тогда и только тогда, когда в нём не больше двух вершин нечётной степени. Значит, эйлерова пути в новом графе нет.
Следовательно, и ломаной, пересекающей каждое ребро исходного графа ровно один раз, не существует.
Ответ: нет, такой ломаной не существует.
