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

 Турнир - это направленный граф, в котором каждая пара вершин {u, v}, имеет одно ребро: из u в v; или из v в u.  

В теории графов доминирующее множество для графа G = (V, E) — это подмножество D множества вершин V, такое, что любая вершина не из D смежна хотя бы одному элементу из D.  

Как можно доказать, что каждый "турнир" с количеством вершин n, содержит доминирующее множество размера log2n ? 

 Доказательство по индукции. Для одной или двух вершин всегда будет 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 - включайте жадно самую крутую вершину в турнире и удаляйте ее и все ею доминируемое.