Волновой алгоритм

Обзор по проблеме востановления турниров

Турниры

 

 

Турнир - это направленный полный граф.

В турнире состязаний данный состав игроков или команд ведет такую игру, правилами которой запрещен ничейный исход. Каждый игрок встречается с каждым другим игроком по одному разу и точно один из них одерживает победу. Игроки изображаются вершинами, и для каждой пары вершин дуга идет от победителя к побежденному; так строится турнир.

Из всех полученных когда-либо теорем о турнирах первая принадлежит Редеи для турниров с малым количеством вершин

 

Теорема. Каждый турнир имеет остовный путь.

Теорема. Каждый сильный турнир с р вершинами имеет контур длины n для n=3, 4, ..., р.

Следствие (а). Турнир является сильным тогда и только тогда, когда он имеет остовный контур.

Используя терминологию турниров состязаний, назовем количеством очков вершины ее полустепень исхода. Следующая теорема, доказанная Ландау, появилась в результате эмпирического изучения специальных турниров (так называемых «pecking orders»), в которых вершины представляют кур, а дуги — клевки.

 

Теорема. Расстояние от вершины с наибольшим количеством очков до любой другой равно 1 или 2.

Число транзитивных троек можно выразить через количества очков вершин; см. Харари и Мозер. Как следствие отсюда немедленно получается хорошо известная формула Кендалла и Смита, имеющая большое значение в статистическом анализе. Она была также получена Байнеке и Харари с помощью перехода от циклических троек к сильным подтурнирам большего размера.

Теорема. Число транзитивных троек в турнире с набором количеств очков (S1,S2,....Sp) равно åsi(si-l)/2.

 

 

Для турниров было дано частичное обоснование специального случая гипотезы Улама. Каждый турнир Т с р вершинами определяет р подтурниров Тi = Т-vi. Было доказано, что можно восстановить любой несильный турнир, имеющий, по крайней мере пять вершин. Однако для сильных турниров с р=5 и р=6 гипотеза не верна. Это установили Байнеке и Паркер, показав, что две пары турниров противоречат гипотезе Улама. Но подобных контрпримеров для турниров с большим числом вершин пока неизвестно так что мы предполагаем, что их нет.

 

Путь с минимальным количеством промежуточных вершин. (волновой алгоритм)

 

 

Процедура находит один из минимальных путей (здесь путей проходящих через минимальное количество вершин) в графе G=(V,E) заданном матрицей связности S. Путь ищется из вершины номер u1 к вершине номер u2. Процедура использует волновой алгоритм.

Волновой алгоритм заключается в следующем:

 

1.каждой вершине i приписывается два целых числа T[i] - временная метка и P[i] - метка предыдущей вершины пути (начальное значение T[i]=0, P[i]=0 для всех i);

2.заводятся два списка "фронта волны" NF и OF, а также переменная T (текущее время);

3.OF:={u1}; NF:={}; T:=1;

4.для каждой из вершин i, входящих в OF, пpосматpиваются соседние вершины j

, и если T[j] = 0, то T[j]=T, NF=NF + {j}; в переменную P[j] заносится номер i.

 

5.если NF = {}, то путь не сyществyет, переход к шагу 8;

6.если одна из вершин совпадает с u2, то найден кратчайший путь длины T, переход к шагу 8;

7.OF:=NF; NF:={}; T:=T+1; возврат к шагу 4.

8.Восстанавливаем путь, проходя массив P.

В качестве OF, NF я использую массивы размера n (количество вершин в графе), некоторые языки (например, Pascal) позволяют работать с объектами типа множества, тогда правильнее использовать именно такую структуру для определения OF, NF, но для того чтобы не нарушать общности я все же остановился именно на массивах, которые присутствуют практически во всех языках программирования.

На выходе имеем переменную length, которая определяет длину пути (length=-1 если пути не существует, length=0, если u1=u2) и массив Path содержащий последовательность номеров вершин определяющих путь.