IPB

Здравствуйте, гость ( Вход | Регистрация )

 
Ответить в эту темуОткрыть новую тему
> Круговой турнир, "от балды"
bogach
сообщение 24.05.07, 16:40
Сообщение #1


BridgeClub
****

Группа: Друзья клуба
Сообщений: 24
Регистрация: 02.02.04
Из: Иерусалим
Пользователь №: 38



Играется круговой турнир с чётным числом участников (в шашки). Туры (т.е. кто с кем играет) назначались произвольно и наступил такой момент, что очередной тур невозможно составить. Вопросы:

1. Каков критерий? (т.е. как узнать не перебором, что очередной тур запустить невозможно)
2. За тур до описываемого события была возможность по-разному составить пары для игры. Каков критерий лушего выбора, т.е. существует ли такой ход (расписание) при которм турнир сможет продолжиться до конца?
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
Delta4
сообщение 24.05.07, 17:01
Сообщение #2


BridgeClub
******

Группа: Друзья клуба
Сообщений: 80
Регистрация: 30.01.04
Из: St.Petersburg - Europe
Пользователь №: 19



Имхо, тема - полный оффтоп. Этот ответ - возможно (и вполне вероятно) бред smile.gif.

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

Соответственно, напрашивающийся алгоритм: каждый раз выбирать такой новый тур, чтобы перманент остающейся матрицы был как можно больше. Как практически реализовать (и можно ли это сделать) - не знаю.

Сообщение отредактировал Delta4 - 24.05.07, 17:33
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
catt
сообщение 25.05.07, 9:15
Сообщение #3


национальный гроссмейстер БК.ру
**********

Группа: Друзья клуба
Сообщений: 472
Регистрация: 27.04.04
Из: Москва
Пользователь №: 137



Я склонна согласиться с Димой. Всё-таки это бриджевый форум, а не математический ( смотри описание форума) smile.gif

Несмотря на мою симпатию к тебе, Алексей, и любовь ко всевозможным математическим задачам, я надеюсь, что в следующий раз ты найдёшь другую площадку для обсуждения подобных проблем.

Сообщение отредактировал catt - 25.05.07, 9:15
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
bogach
сообщение 25.05.07, 10:19
Сообщение #4


BridgeClub
****

Группа: Друзья клуба
Сообщений: 24
Регистрация: 02.02.04
Из: Иерусалим
Пользователь №: 38



Ко мне обратился Авгера с вопросом по поводу проведения бриджевых швейцарок. При большом числе команд в начале турнира ещё есть возможность по разному назначать туры, но он не знает критерия оптимального тура. Именно поэтому эта тема и была вынесена на обсуждениеsmile.gif
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения
IBM
сообщение 28.05.07, 22:13
Сообщение #5


клубный мастер БK.ру
*******

Группа: Друзья клуба
Сообщений: 91
Регистрация: 31.01.04
Пользователь №: 31



Нормальная тема.
Критерий не знаю.
Вернуться в начало страницы
 
+Ответить с цитированием данного сообщения

Ответить в эту темуОткрыть новую тему
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



Текстовая версия Сейчас: 29.03.24, 14:15
реклама: