если игрок х победил игрока у. По идее, игрок более высокого класса должен победить игрока низшего класса, хотя противоположный (неожиданный)  результат наблюдается довольно часто. Естественным определением рейтинга будет  топологическое упорядочение, полученное после удаления из графа минимального  разрывающего множества ребер, представляющих неожиданные результаты матча.

Решая задачу разрывающего множества, ответьте на следующие вопросы. Нужно ли отбросить какие-либо ограничивающие условия? Если граф уже является бесконтурным орграфом, что можно выяснить с помощью топологической  сортировки, то никакие изменения не требуются. Один из способов поиска разрывающего множества состоит в модифицировании алгоритма топологической сортировки  таким образом, чтобы при обнаружении конфликта удалялось проблемное ребро или вершина. Но это разрывающее множество может оказаться намного больше  требуемого, т. к. на ориентированных графах задачи поиска разрывающего множества  ребер и разрывающего множества вершин являются NP-полными. Как найти подходящее разрывающее множество ребер? Эффективный  эвристический алгоритм с линейным временем исполнения создает вершинное упорядочение, а потом удаляет каждую дугу, идущую в неправильном направлении. При любом упорядочении вершин направление, по крайней мере, половины дуг должно быть одинаковым (слева направо или справа налево), поэтому в качестве разрывающего множества следует взять то, которое меньше. Как правильно выбрать начальную вершину? Вполне естественно отсортировать вершины по их реберной разбалансированности, т. е. по разности между степенью захода и степенью исхода.