Страница 6 номер 2, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого 2 часть. Углубленный уровень
Является ли деревом граф дорог в вашем населённом пункте? Постройте в тетради часть этого графа в обоснование своего ответа.
Например: возьмём город, в котором улицы пересекаются и делят его на кварталы. Вершины графа дорог — перекрёстки, рёбра — участки улиц между соседними перекрёстками. Построим часть этого графа — два соседних квартала:
Улицы вокруг квартала дают замкнутый путь \(ABEDA\): рёбра в нём не повторяются, промежуточные вершины \(B\), \(E\), \(D\) — тоже, поэтому это цикл. Граф с циклом деревом не является. Деревом граф дорог бывает только там, где улицы ветвятся и нигде не замыкаются в кольцо, — например, в небольшом посёлке с одной дорогой и тупиковыми ответвлениями от неё.
Ответ: нет: в городе с кварталами улицы вокруг квартала образуют цикл, поэтому граф дорог — не дерево.
Является ли деревом граф дорог в вашем населённом пункте? Постройте в тетради часть этого графа в обоснование своего ответа.
Например: возьмём город, в котором улицы пересекаются и делят его на кварталы. Вершины графа дорог — перекрёстки; ребро соединяет два соседних перекрёстка, если между ними идёт участок улицы. Построим часть этого графа — два соседних квартала:
Улицы вокруг квартала дают замкнутый путь \(ABEDA\): рёбра в нём не повторяются, промежуточные вершины \(B\), \(E\), \(D\) — тоже, поэтому это цикл. Граф, в котором есть цикл, деревом не является. Деревом граф дорог бывает только там, где улицы ветвятся и нигде не замыкаются в кольцо, — например, в небольшом посёлке с одной дорогой и тупиковыми ответвлениями от неё.
Ответ: нет: в городе с кварталами улицы вокруг квартала образуют цикл, поэтому граф дорог — не дерево.
