Страница 68 номер 102, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
Какое наибольшее число рёбер может быть у планарного графа с 5 вершинами? с 6 вершинами? Свои ответы обоснуйте.
Пусть у планарного графа \(\text{В}\) вершин и \(\text{Р}\) рёбер, причём \(\text{В} \geqslant 3\). Граф можно считать связным: распадись он на части, к нему удалось бы добавить ребро между разными частями, не нарушив планарности, и рёбер стало бы больше, а нас интересует наибольшее их число.
Каждая грань плоского графа ограничена не меньше чем тремя рёбрами, а каждое ребро лежит на границе ровно двух граней, поэтому
\[2\text{Р} \geqslant 3\text{Г}.\]
По формуле Эйлера \(\text{Г} = 2 - \text{В} + \text{Р}\), откуда \(2\text{Р} \geqslant 6 - 3\text{В} + 3\text{Р}\), то есть \(3\text{В} - 6 \geqslant \text{Р}\).
При \(\text{В} = 5\) получаем \(\text{Р} \leqslant 3 \cdot 5 - 6 = 9\), при \(\text{В} = 6\) — \(\text{Р} \leqslant 3 \cdot 6 - 6 = 12\). Обе оценки достигаются.
Пять вершин и девять рёбер. Из полного графа с вершинами \(A\), \(B\), \(C\), \(D\), \(E\) выбросим ребро \(DE\): останется \(10 - 1 = 9\) рёбер. Он планарный — треугольник \(ABD\), внутри него \(C\), соединённая с \(A\), \(B\), \(D\), а внутри треугольника \(ABC\) — \(E\), соединённая с \(A\), \(B\), \(C\).
Шесть вершин и двенадцать рёбер. У октаэдра 6 вершин, 12 рёбер и 8 треугольных граней: \(6 - 12 + 8 = 2\). Граф его вершин и рёбер планарный: поверхность выпуклого многогранника без одной грани растягивается на плоскость. Плоское изображение: треугольник \(ABC\), внутри него треугольник \(DEF\), причём \(D\) соединена с \(B\) и \(C\), \(E\) — с \(C\) и \(A\), \(F\) — с \(A\) и \(B\).
Ответ: у планарного графа с 5 вершинами не больше 9 рёбер, а с 6 вершинами — не больше 12; обе оценки достигаются: 9 рёбер даёт полный граф с пятью вершинами без одного ребра, а 12 рёбер — граф октаэдра.
Какое наибольшее число рёбер может быть у планарного графа с 5 вершинами? с 6 вершинами? Свои ответы обоснуйте.
Пусть у планарного графа \(\text{В}\) вершин и \(\text{Р}\) рёбер, причём \(\text{В} \geqslant 3\). Считать граф связным можно: если бы он распадался на части, к нему удалось бы добавить ещё одно ребро между разными частями, не нарушив планарности, и рёбер стало бы больше, — а нас интересует наибольшее их число.
Нарисуем граф на плоскости без пересечений; пусть у полученного плоского графа \(\text{Г}\) граней. Каждая грань ограничена не меньше чем тремя рёбрами, а каждое ребро лежит на границе ровно двух граней, поэтому
\[2\text{Р} \geqslant 3\text{Г}.\]
По формуле Эйлера \(\text{В} - \text{Р} + \text{Г} = 2\), откуда \(\text{Г} = 2 - \text{В} + \text{Р}\). Подставим это в неравенство: \(2\text{Р} \geqslant 6 - 3\text{В} + 3\text{Р}\), то есть \(3\text{В} - 6 \geqslant \text{Р}\).
При \(\text{В} = 5\) получаем \(\text{Р} \leqslant 3 \cdot 5 - 6 = 9\); при \(\text{В} = 6\) получаем \(\text{Р} \leqslant 3 \cdot 6 - 6 = 12\).
Обе оценки достигаются.
Пять вершин и девять рёбер. Возьмём полный граф с пятью вершинами \(A\), \(B\), \(C\), \(D\), \(E\) и выбросим из него ребро \(DE\); останется \(10 - 1 = 9\) рёбер. Этот граф планарный: треугольник \(ABD\), внутри него вершина \(C\), соединённая с \(A\), \(B\) и \(D\), а внутри треугольника \(ABC\) — вершина \(E\), соединённая с \(A\), \(B\) и \(C\).
Шесть вершин и двенадцать рёбер. Возьмём октаэдр — выпуклый многогранник с восемью треугольными гранями. У него 6 вершин и 12 рёбер (формула Эйлера подтверждает: \(6 - 12 + 8 = 2\)), а граф его вершин и рёбер планарный: поверхность выпуклого многогранника, из которой вырезали одну грань, растягивается на плоскость. Плоское изображение такое: треугольник \(ABC\), внутри него треугольник \(DEF\), причём каждая вершина внутреннего треугольника соединена с двумя ближайшими вершинами внешнего — \(D\) с \(B\) и \(C\), \(E\) с \(C\) и \(A\), \(F\) с \(A\) и \(B\).
Ответ: у планарного графа с 5 вершинами не больше 9 рёбер, а с 6 вершинами — не больше 12; обе оценки достигаются: 9 рёбер даёт полный граф с пятью вершинами без одного ребра, а 12 рёбер — граф октаэдра.
