Страница 68 номер 101, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
Какие из графов на рисунке 60 планарные? Свой ответ обоснуйте.
а) Шесть вершин двумя тройками, каждая вершина одной тройки соединена с каждой вершиной другой — \(3 \cdot 3 = 9\) рёбер, внутри троек рёбер нет. Это граф о трёх домиках и трёх колодцах, он непланарный: как ни прокладывай тропинки, последняя обязательно пересечёт одну из проложенных.
б) Пять вершин соединены всеми возможными рёбрами, которых \(\frac{5 \cdot 4}{2} = 10\): это полный граф с пятью вершинами, он тоже непланарный.
в) Девять вершин в узлах сетки \(3 \times 3\): соединены все соседи по горизонтали (6 рёбер) и по вертикали (6 рёбер), и проведены обе диагонали каждой из четырёх клеток (8 рёбер) — всего 20 рёбер. Этот граф планарный.
Обозначим вершины: \(O\) — центральная, \(A\), \(C\), \(E\), \(G\) — угловые (левая верхняя, правая верхняя, правая нижняя, левая нижняя), \(B\), \(D\), \(F\), \(H\) — середины сторон (верхняя, правая, нижняя, левая). Рёбра: восемь сторон клеток \(AB\), \(BC\), \(CD\), \(DE\), \(EF\), \(FG\), \(GH\), \(HA\); восемь рёбер из центра — \(OB\), \(OD\), \(OF\), \(OH\) (стороны клеток) и \(OA\), \(OC\), \(OE\), \(OG\) (диагонали); четыре диагонали между серединами сторон \(BH\), \(BD\), \(FD\), \(FH\). Всего \(8 + 8 + 4 = 20\).
Расставим восемь вершин, кроме центральной, по окружности в порядке \(A\), \(B\), \(C\), \(D\), \(E\), \(F\), \(G\), \(H\) — стороны клеток станут сторонами восьмиугольника. Вершину \(O\) поместим внутрь и соединим со всеми восемью: эти рёбра расходятся из одной точки и не пересекаются. Рёбра \(BH\), \(BD\), \(FD\), \(FH\) проведём снаружи дугами: каждая перешагивает ровно через одну вершину (\(BH\) — через \(A\), \(BD\) — через \(C\), \(FD\) — через \(E\), \(FH\) — через \(G\)), поэтому дуги не пересекаются ни между собой, ни со сторонами восьмиугольника.
Ответ: а) непланарный — это граф о трёх домиках и трёх колодцах; б) непланарный — это полный граф с пятью вершинами; в) планарный: восемь вершин, кроме центральной, укладываются в восьмиугольник, центральная соединяется с ними изнутри, а четыре оставшиеся диагонали проводятся снаружи восьмиугольника.
Какие из графов на рисунке 60 планарные? Свой ответ обоснуйте.
Вершины в задании не подписаны, поэтому в третьем графе обозначим их сами.
а) Шесть вершин разбиты на две тройки, и каждая вершина одной тройки соединена с каждой вершиной другой — всего \(3 \cdot 3 = 9\) рёбер; внутри троек рёбер нет. Это в точности граф головоломки о трёх домиках и трёх колодцах. По теореме Понтрягина — Куратовского он непланарный: как ни прокладывай тропинки, последняя обязательно пересечёт одну из уже проложенных.
б) Пять вершин соединены всеми возможными рёбрами, которых \(\frac{5 \cdot 4}{2} = 10\). Это полный граф с пятью вершинами — второй граф теоремы Понтрягина — Куратовского, и он тоже непланарный.
в) Девять вершин стоят в узлах квадратной сетки \(3 \times 3\). Соединены все соседи по горизонтали (6 рёбер) и по вертикали (6 рёбер), а кроме того проведены обе диагонали каждой из четырёх клеток (8 рёбер) — всего 20 рёбер.
Этот граф планарный. Обозначим вершины: \(O\) — центральная, \(A\), \(C\), \(E\), \(G\) — угловые (левая верхняя, правая верхняя, правая нижняя, левая нижняя), \(B\), \(D\), \(F\), \(H\) — середины сторон (верхняя, правая, нижняя, левая). Тогда рёбра такие:
— восемь сторон клеток \(AB\), \(BC\), \(CD\), \(DE\), \(EF\), \(FG\), \(GH\), \(HA\) — каждая соединяет угол с серединой стороны;
— восемь рёбер из центральной вершины: \(OB\), \(OD\), \(OF\), \(OH\) (стороны клеток) и \(OA\), \(OC\), \(OE\), \(OG\) (диагонали клеток);
— четыре диагонали клеток, соединяющие середины сторон: \(BH\), \(BD\), \(FD\), \(FH\).
Всего \(8 + 8 + 4 = 20\) рёбер — все они на месте.
Изобразим граф без пересечений. Расставим восемь вершин, кроме центральной, по окружности в порядке \(A\), \(B\), \(C\), \(D\), \(E\), \(F\), \(G\), \(H\) — тогда восемь сторон клеток станут сторонами восьмиугольника. Центральную вершину \(O\) поместим внутрь и соединим со всеми восемью — эти рёбра расходятся из одной точки и потому друг друга не пересекают. Оставшиеся четыре ребра \(BH\), \(BD\), \(FD\), \(FH\) проведём снаружи восьмиугольника дугами: каждая перешагивает ровно через одну вершину (\(BH\) — через \(A\), \(BD\) — через \(C\), \(FD\) — через \(E\), \(FH\) — через \(G\)), поэтому дуги не пересекаются ни между собой, ни со сторонами восьмиугольника.
Ответ: а) непланарный — это граф о трёх домиках и трёх колодцах; б) непланарный — это полный граф с пятью вершинами; в) планарный: восемь вершин, кроме центральной, укладываются в восьмиугольник, центральная соединяется с ними изнутри, а четыре оставшиеся диагонали проводятся снаружи восьмиугольника.
