@zemlyakov

Какой размер доминирующего множества направленного графа (турнира)?

Турнир - это направленный граф, в котором каждая пара вершин {u, v}, имеет одно ребро: из u в v; или из v в u.
В теории графов доминирующее множество для графа G = (V, E) — это подмножество D множества вершин V, такое, что любая вершина не из D смежна хотя бы одному элементу из D.
Как можно доказать, что каждый "турнир" с количеством вершин n, содержит доминирующее множество размера log2n ?
  • Вопрос задан
  • 96 просмотров
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Доказательство по индукции. Для одной или двух вершин всегда будет 1 в D.

Пусть degree(v) - количество вершин, инцидентных v.
Лемма: В турнире с n вершинами будет хотя бы одна с degree() >= (n-1)/2. Иначе, просуммируем все degree().
С одной стороны, сумма будет равна количеству ребер, т.е. n(n-1)/2. С другой, эта сумма < n*(n-1)/2 по предполоджению. Противоречие, значит существует v: degree(v) >= (n-1)/2

Теперь докажем основное утверждение.
Рассмотрим турнир с n>2 вершинами. Там есть хотя бы одна v: degree(v) >= (n-1)/2. Включим ее в D. и удалим из графа ее и все, которым она инцедентна. Мы удалили из графа не меньше 1+(n-1)/2 вершин, фактически уполовинив количество вершин в графе. По индукционному предположению там надо log(n/2) вершин в доминирующем множестве. Иы добавили к ней 1. Поэтому в итоге нам надо log(n) вершин и для этого графа.

Это же доказательство можно использовать для построения D - включайте жадно самую крутую вершину в турнире и удаляйте ее и все ею доминируемое.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы