Страница 66 номер 112, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Какое наименьшее количество рёбер нужно удалить из графа (рис. 67), чтобы оставшийся подграф оказался планарным? Обоснуйте ответ.
Обозначим вершины первого графа: левый столбец сверху вниз — \(A\), \(B\), \(C\), правый столбец сверху вниз — \(D\), \(E\), \(F\). Вершины второго графа обозначим по кругу: \(K\) — верхняя, \(L\) — правая верхняя, \(M\) — правая нижняя, \(N\) — левая нижняя, \(P\) — левая верхняя.
а) В первом графе каждая из вершин \(A\), \(B\), \(C\) соединена с каждой из вершин \(D\), \(E\), \(F\); в нём 6 вершин и 9 рёбер. Это граф \(K_{3,3}\), а он не является планарным, поэтому ноль рёбер удалить нельзя.
Одного ребра достаточно. Удалим ребро \(AE\); останется 8 рёбер: \(AD\), \(AF\), \(BD\), \(BE\), \(BF\), \(CD\), \(CE\), \(CF\). Расположим вершины \(D\), \(E\), \(F\) одна под другой в столбец, вершину \(B\) поставим слева от столбца, а \(C\) — справа: рёбра \(BD\), \(BE\), \(BF\) пойдут веером влево, а \(CD\), \(CE\), \(CF\) — веером вправо. Вершину \(A\) поставим ещё правее вершины \(C\) и соединим её с \(D\) и \(F\) линиями, обходящими \(C\) сверху и снизу, — пересечений не возникает.
б) Второй граф — полный граф \(K_5\): 5 вершин и 10 рёбер. Он не является планарным, поэтому ноль рёбер удалить нельзя.
Одного ребра достаточно. Удалим ребро \(NP\); останется 9 рёбер. Вершину \(N\) поместим внутри треугольника \(KLM\) и соединим с \(K\), \(L\) и \(M\), а вершину \(P\) — снаружи треугольника и соединим с теми же тремя вершинами: рёбра \(NK\), \(NL\), \(NM\) лежат внутри треугольника, рёбра \(PK\), \(PL\), \(PM\) — снаружи, поэтому пересечений нет.
Ответ: а) одно ребро; б) одно ребро.
Какое наименьшее количество рёбер нужно удалить из графа (рис. 67), чтобы оставшийся подграф оказался планарным? Обоснуйте ответ.
Обозначим вершины первого графа: левый столбец сверху вниз — \(A\), \(B\), \(C\), правый столбец сверху вниз — \(D\), \(E\), \(F\). Вершины второго графа обозначим по кругу: \(K\) — верхняя, \(L\) — правая верхняя, \(M\) — правая нижняя, \(N\) — левая нижняя, \(P\) — левая верхняя.
а) Первый граф полный в том смысле, что каждая из вершин \(A\), \(B\), \(C\) соединена с каждой из вершин \(D\), \(E\), \(F\); в нём 6 вершин и 9 рёбер. Это граф \(K_{3,3}\), а он не является планарным. Значит, ноль рёбер удалить нельзя: оставив все девять рёбер, плоского чертежа не получить.
Одного ребра достаточно. Удалим ребро \(AE\); останется 8 рёбер: \(AD\), \(AF\), \(BD\), \(BE\), \(BF\), \(CD\), \(CE\), \(CF\). Расположим вершины \(D\), \(E\), \(F\) одна под другой в столбец, вершину \(B\) поставим слева от этого столбца, а вершину \(C\) — справа: рёбра \(BD\), \(BE\), \(BF\) пойдут веером влево, а \(CD\), \(CE\), \(CF\) — веером вправо, и пересечений не возникнет. Вершину \(A\) поставим ещё правее вершины \(C\) и соединим её с \(D\) и \(F\) линиями, обходящими \(C\) сверху и снизу. Получается плоский граф.
б) Второй граф — полный граф \(K_5\): 5 вершин и 10 рёбер. Он не является планарным, поэтому ноль рёбер удалить нельзя.
Одного ребра достаточно. Удалим ребро \(NP\); останется 9 рёбер. Нарисуем треугольник \(KLM\), вершину \(N\) поместим внутри него и соединим с \(K\), \(L\) и \(M\), а вершину \(P\) поместим снаружи треугольника и соединим её с теми же тремя вершинами. Рёбра \(NK\), \(NL\), \(NM\) лежат внутри треугольника, рёбра \(PK\), \(PL\), \(PM\) — снаружи, поэтому пересечений нет.
В обоих случаях удалить ноль рёбер нельзя, а удаления одного ребра хватает.
Ответ: а) одно ребро; б) одно ребро.
