Реши задание на изображении
Краткие ответы
- Формула Эйлера для многогранников: \(\;В-Р+Г=2\).
- 81: выбрать висячую вершину остовного дерева.
- 82: а) \(1\); б) \(6\); в) \(3\) ребра.
- 83: а) \(3\); б) \(7\); в) \(2\) ребра.
- 84: а) существует; б), в), г) не существуют.
- 85: \(19\) тропинок.
- 86: можно закрыть \(406\) авиалиний.
- 87: сеть обязательно связна.
Вопросы
Для многогранника: \[ В-Р+Г=2, \] где \(В\) — число вершин, \(Р\) — число рёбер, \(Г\) — число граней.
Проверка:
- тетраэдр: \(4-6+4=2\);
- куб: \(8-12+6=2\).
Грань плоского графа — это область плоскости, на которые граф разбивает плоскость. Внешняя неограниченная область также считается гранью.
Для связного плоского графа: \[ В-Р+Г=2. \]
81
Из исходной сети можно удалить некоторые дороги так, чтобы остался остовный граф — дерево, соединяющее все города.
У дерева есть хотя бы одна висячая вершина, то есть город, связанный с деревом только одной дорогой. Выберем такой город \(A\).
Если закрыть все дороги, ведущие в \(A\), то оставшаяся часть дерева \(T-A\) всё ещё будет связной: между любыми двумя оставшимися городами существует путь, не проходящий через \(A\).
Значит, из любого города можно попасть в любой другой, кроме выбранного.
82
В любом дереве с \(n\) вершинами должно быть \(n-1\) рёбер.
а) 6 вершин и 6 рёбер. Нужно оставить 5, поэтому удалить: \[ 6-5=1. \] Достаточно удалить любую сторону шестиугольника.
б) 5 вершин и 10 рёбер. Нужно оставить 4: \[ 10-4=6. \] Например, оставить четыре ребра, идущие от одной вершины к остальным.
в) 8 вершин и 10 рёбер. Нужно оставить 7: \[ 10-7=3. \] Можно оставить все 7 рёбер, идущих из центральной вершины, а три внешних ребра удалить.
83
а) На рисунке 8 вершин и 4 разрозненных ребра. Для дерева нужно 7 рёбер: \[ 7-4=3. \] Добавляем 3 ребра, соединяя четыре компоненты в одну.
б) 8 изолированных вершин. Нужно соединить их в дерево: \[ 8-1=7. \] Добавляем 7 рёбер, например соединяем вершины в цепочку.
в) На рисунке три компоненты, каждая уже является деревом. Чтобы соединить три компоненты, нужно добавить: \[ 3-1=2 \] ребра.
84
Для дерева на \(n\) вершинах сумма степеней всех вершин равна
\[ d_1+d_2+\dots+d_n=2(n-1). \]
а) \(1,1,2,2,2\)
Можно построить цепочку из пяти вершин:
\[ A-B-C-D-E. \]
Степени вершин: \(1,2,2,2,1\).
б) \(2,2,2,3\)
\[ 2+2+2+3=9, \] но для четырёх вершин сумма должна быть
\[ 2(4-1)=6. \]
Такого дерева не существует.
в) \(1,1,1,1,1\)
\[ 1+1+1+1+1=5, \] а должно быть
\[ 2(5-1)=8. \]
Такого дерева не существует.
г) \(1,1,1,1,1,1,1,2,4\)
\[ 1\cdot7+2+4=13, \] а для девяти вершин требуется
\[ 2(9-1)=16. \]
Такого дерева не существует.
85
Условие означает, что граф домов и тропинок является деревом.
В дереве с \(n\) вершинами \(n-1\) рёбер, поэтому
\[ 20-1=\boxed{19}. \]
86
Всего между 30 городами можно провести
\[ \binom{30}{2}=\frac{30\cdot29}{2}=435 \]
авиалиний.
Чтобы все города оставались связанными, достаточно оставить дерево, то есть 29 авиалиний.
Тогда можно закрыть
\[ 435-29=\boxed{406} \]
авиалиний.
87
Предположим, что сеть несвязна. Тогда в каждой её компоненте любой город должен иметь 6 соседей, поэтому в одной компоненте должно быть не менее
\[ 6+1=7 \]
городов.
Если бы компонент было хотя бы две, то городов потребовалось бы не менее
\[ 7+7=14, \]
но всего их 13. Противоречие.
Следовательно, компонент всего одна, то есть из любого города можно добраться в любой другой.
