Страница 66 номер 113, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
Докажите, что граф, изображённый на рисунке 68, не является планарным.
Вершины на рисунке не подписаны, поэтому обозначим их сами. Вершины «заднего» квадрата: \(B_1\) — вверху слева, \(B_2\) — вверху справа, \(B_3\) — внизу справа, \(B_4\) — внизу слева. Вершины «переднего» квадрата в том же порядке — \(F_1\), \(F_2\), \(F_3\), \(F_4\).
В графе 8 вершин и 14 рёбер: стороны заднего квадрата \(B_1B_2\), \(B_2B_3\), \(B_3B_4\), \(B_4B_1\); стороны переднего квадрата \(F_1F_2\), \(F_2F_3\), \(F_3F_4\), \(F_4F_1\); боковые рёбра \(B_1F_1\), \(B_2F_2\), \(B_3F_3\), \(B_4F_4\); две диагонали \(B_1F_3\) и \(B_2F_4\).
Удалим вершины \(F_1\) и \(F_2\) вместе с примыкающими к ним рёбрами — останется девять рёбер:
- \(B_1B_2\), \(B_1B_4\) — стороны заднего квадрата, \(B_1F_3\) — диагональ;
- \(B_3B_2\), \(B_3B_4\) — стороны заднего квадрата, \(B_3F_3\) — боковое ребро;
- \(F_4B_2\) — диагональ, \(F_4B_4\) — боковое ребро, \(F_4F_3\) — сторона переднего квадрата.
Все девять рёбер в исходном графе есть, поэтому такой подграф существует. В нём шесть вершин, каждая из вершин \(B_1\), \(B_3\), \(F_4\) соединена с каждой из вершин \(B_2\), \(B_4\), \(F_3\), а больше рёбер нет. Значит, этот подграф изоморфен графу \(K_{3,3}\): тройка \(B_1\), \(B_3\), \(F_4\) отвечает трём «домам», тройка \(B_2\), \(B_4\), \(F_3\) — трём «колодцам», и рёбра при этом соответствии сохраняются.
Граф \(K_{3,3}\) не является планарным, а подграф планарного графа планарен: если бы весь граф удалось изобразить на плоскости без пересечений, то, стерев лишние вершины и рёбра, мы получили бы чертёж без пересечений и для подграфа. Значит, граф, содержащий непланарный подграф, сам непланарен, а наш граф содержит подграф, изоморфный \(K_{3,3}\).
Ответ: граф содержит подграф, изоморфный непланарному графу \(K_{3,3}\), поэтому он не является планарным, что и требовалось доказать.
Докажите, что граф, изображённый на рисунке 68, не является планарным.
Вершины на рисунке не подписаны, поэтому обозначим их сами. Вершины «заднего» квадрата: \(B_1\) — вверху слева, \(B_2\) — вверху справа, \(B_3\) — внизу справа, \(B_4\) — внизу слева. Вершины «переднего» квадрата в том же порядке — \(F_1\), \(F_2\), \(F_3\), \(F_4\).
В графе 8 вершин и 14 рёбер: стороны заднего квадрата \(B_1B_2\), \(B_2B_3\), \(B_3B_4\), \(B_4B_1\); стороны переднего квадрата \(F_1F_2\), \(F_2F_3\), \(F_3F_4\), \(F_4F_1\); боковые рёбра \(B_1F_1\), \(B_2F_2\), \(B_3F_3\), \(B_4F_4\); две диагонали \(B_1F_3\) и \(B_2F_4\).
Выделим в этом графе подграф. Удалим вершины \(F_1\) и \(F_2\) вместе с примыкающими к ним рёбрами — останется девять рёбер:
- \(B_1B_2\), \(B_1B_4\) — стороны заднего квадрата, \(B_1F_3\) — диагональ;
- \(B_3B_2\), \(B_3B_4\) — стороны заднего квадрата, \(B_3F_3\) — боковое ребро;
- \(F_4B_2\) — диагональ, \(F_4B_4\) — боковое ребро, \(F_4F_3\) — сторона переднего квадрата.
Все девять рёбер в исходном графе есть, поэтому такой подграф существует. В нём шесть вершин, и каждая из вершин \(B_1\), \(B_3\), \(F_4\) соединена с каждой из вершин \(B_2\), \(B_4\), \(F_3\), а больше рёбер в подграфе нет. Значит, этот подграф изоморфен графу \(K_{3,3}\): соответствие вершин видно сразу — тройка \(B_1\), \(B_3\), \(F_4\) отвечает трём «домам», а тройка \(B_2\), \(B_4\), \(F_3\) — трём «колодцам», и рёбра при этом соответствии сохраняются.
Граф \(K_{3,3}\) не является планарным.
Осталось заметить, что подграф планарного графа планарен: если бы весь граф удалось изобразить на плоскости без пересечений, то, стерев лишние вершины и рёбра, мы получили бы чертёж без пересечений и для подграфа. Значит, граф, содержащий непланарный подграф, сам непланарен.
Наш граф содержит подграф, изоморфный \(K_{3,3}\), поэтому он не планарен.
Ответ: граф содержит подграф, изоморфный непланарному графу \(K_{3,3}\), поэтому он не является планарным, что и требовалось доказать.
