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

Question

[zemlyakov]

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

Comments

[Rsa97]

n = 3
log₂n = 1,584962501
Множества с размером 1,584962501 не существует, следовательно предположение неверно. Либо неверна формулировка гипотезы.

Answer 1

[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 - включайте жадно самую крутую вершину в турнире и удаляйте ее и все ею доминируемое.