ГДЗ Алгебра 7 клас — Мерзляк А. Г. 2024, Вправа 218
Алгебра. 7 клас · Мерзляк А. Г., Якір М. С. · 2024 · Станція метро, яку можна закрити без втрати зв’язності
Відкрити сторінку 54 разом із ГДЗ →💡 Підказка · Вправа 218
Уяви мережу метро як зв’язний граф і візьми найдовший простий маршрут без повторення станцій.
🧠 Розв’язання · Вправа 218
- Подамо станції вершинами графа, а можливість безпосереднього проїзду між ними — ребрами. За умовою граф зв’язний.
- Візьмемо найдовший простий шлях v₀,v₁,…,vₖ, у якому жодна станція не повторюється.
- Припустімо, що після закриття кінцевої станції v₀ решта графа стає незв’язною.
- Тоді в графі без v₀ існує компонента, яка не містить v₁. Оскільки початковий граф був зв’язним, у цій компоненті є вершина w, сполучена ребром із v₀.
- Тоді шлях w,v₀,v₁,…,vₖ є простим і на одну вершину довшим за обраний найдовший шлях — суперечність.
- Отже, видалення v₀ не порушує зв’язності решти мережі. Таку станцію й можна закрити.
✅ Відповідь · Вправа 218
Так, така станція завжди існує: підійде кінцева вершина будь-якого найдовшого простого шляху мережі.
Знайшли помилку у відповіді? Повідомити →Інші вправи сторінки 54Перейди одразу до потрібного номера
Дивись також сторінку підручника, усі ГДЗ сторінки 54, ГДЗ Алгебра 7 клас, ГДЗ Мерзляк 7 клас, усі підручники з предмета «Алгебра» та усі розв’язання Мерзляк А. Г. 2024.