ГДЗ Алгебра 7 клас — Мерзляк А. Г. 2024, вправа 218

🧠 Розв’язання вправи 218 крок за кроком

1. Подамо станції вершинами графа, а можливість безпосереднього проїзду між ними — ребрами. За умовою граф зв’язний.
2. Візьмемо найдовший простий шлях v₀,v₁,…,vₖ, у якому жодна станція не повторюється.
3. Припустімо, що після закриття кінцевої станції v₀ решта графа стає незв’язною.
4. Тоді в графі без v₀ існує компонента, яка не містить v₁. Оскільки початковий граф був зв’язним, у цій компоненті є вершина w, сполучена ребром із v₀.
5. Тоді шлях w,v₀,v₁,…,vₖ є простим і на одну вершину довшим за обраний найдовший шлях — суперечність.
6. Отже, видалення v₀ не порушує зв’язності решти мережі. Таку станцію й можна закрити.