Условие:
Может ли эксцентриситет вершины:
1) Увеличиться при удалении из графа некоторого ребра
2) Уменьшиться при удалении из графа некоторого ребра
3) при удалении другой вершины
4) увеличиться при удалении другой вершины
Решение:
Для начала вспомним, что эксцентриситет вершины в графе – это максимальное расстояние от неё до всех остальных вершин (в пределах той же связной компоненты). Далее проанализируем каждый случай пошагово.
- Может ли эксцентриситет увеличиться при удалении ребра?
Если из графа удаляют ребро, которое когда-то лежало на одном из кратчайших путей от рассматриваемой вершины до самой удалённой (то есть до вершины, определявшей её эксцентриситет), то кратчайший путь к этой вершине может измениться – он может стать длиннее, если других равнозначных коротких путей нет. В рез...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи