Доказать, что если G - граф c n вершинами и минимальной степенью вершин δ, то α0(G)≤n – δ.
Число вершин в наибольшем независимом мн-ве. графа наз-ся числом независимости.α0(G)
Задача по графам
Задача по графам
Последний раз редактировалось dfi007 30 ноя 2019, 08:51, всего редактировалось 1 раз.
Причина: test
Причина: test
Задача по графам
dfi007 писал(а):Source of the post
Доказать, что если G - граф c n вершинами и минимальной степенью вершин δ, то α0(G)≤n – δ.
Число вершин в наибольшем независимом мн-ве. графа наз-ся числом независимости.α0(G)
A что тут доказывать-то?
Пусть некая вершина входит в наибольшее независимое множество. Что Вы можете сказать o вершинах из ee окружения?
Последний раз редактировалось VAL 30 ноя 2019, 08:51, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 23 гостей