Страница 22 номер 47, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого 2 часть. Углубленный уровень
Решите задачу о пяти базарных площадях.
Обозначим площади \(A\), \(B\), \(C\), \(D\), \(E\). Площади — вершины графа, маршруты — его рёбра: каждые две вершины соединены ребром. Пар площадей 10: \(AB\), \(AC\), \(AD\), \(AE\), \(BC\), \(BD\), \(BE\), \(CD\), \(CE\), \(DE\), поэтому \(v = 5\), \(e = 10\).
Предположим противное: все 10 маршрутов удалось проложить так, что никакие два из них не пересекаются. Тогда получился конечный связный плоский граф. По формуле Эйлера \(v - e + f = 2\), поэтому число областей \(f = 2 - 5 + 10 = 7\).
Степень каждой области не меньше 3. Область степени 1 ограничена петлёй, а петель нет: каждый маршрут соединяет две разные площади. Граница области степени 2 — либо два маршрута между одними и теми же площадями, либо один маршрут, который при обходе проходится дважды. Первого не бывает: две площади соединены одним маршрутом. Второе бывает, только если весь граф — один маршрут, а маршрутов 10. Значит, суммарная степень семи областей не меньше \(3 \cdot 7 = 21\).
С другой стороны, суммарная степень областей равна удвоенному числу рёбер: \(2 \cdot 10 = 20\), а \(20 < 21\). Это противоречит тому, что она не меньше 21. Значит, предположение неверно, и соединить площади так, чтобы никакие два маршрута не пересекались, нельзя: граф пяти площадей не планарный.
Ответ: начертить такой план нельзя — граф пяти площадей не планарный.
Решите задачу о пяти базарных площадях.
В задаче о пяти базарных площадях нужно соединить каждые две из пяти площадей маршрутом так, чтобы никакие два маршрута не пересекались. Обозначим площади \(A\), \(B\), \(C\), \(D\), \(E\). Площади — вершины графа, маршруты — его рёбра: каждые две вершины соединены ребром. Пар площадей 10: \(AB\), \(AC\), \(AD\), \(AE\), \(BC\), \(BD\), \(BE\), \(CD\), \(CE\), \(DE\), поэтому \(v = 5\), \(e = 10\). Докажем, что начертить такой план нельзя.
Предположим противное: все 10 маршрутов удалось проложить так, что никакие два из них не пересекаются. Тогда получился конечный связный плоский граф. По формуле Эйлера \(v - e + f = 2\), поэтому число областей \(f = 2 - 5 + 10 = 7\).
Степень каждой области не меньше 3. Область степени 1 ограничена петлёй, а петель нет: каждый маршрут соединяет две разные площади. Граница области степени 2 — либо два маршрута между одними и теми же площадями, либо один маршрут, который при обходе проходится дважды. Первого не бывает: две площади соединены одним маршрутом. Второе бывает, только если весь граф — один маршрут, а маршрутов 10. Значит, суммарная степень семи областей не меньше \(3 \cdot 7 = 21\).
С другой стороны, суммарная степень областей равна удвоенному числу рёбер: \(2 \cdot 10 = 20\), а \(20 < 21\). Это противоречит тому, что она не меньше 21. Значит, предположение неверно, и соединить площади так, чтобы никакие два маршрута не пересекались, нельзя: граф пяти площадей не планарный.
Ответ: начертить такой план нельзя — граф пяти площадей не планарный.
