Всеволод Баширов (sevabashirov) wrote,
Всеволод Баширов
sevabashirov

Categories:

Слоупок ФМ №18. Ты, я и гЭомЭтрия



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

Вообще, для справки, минимизация средней длины путей в графе турнира позволяет максимизировать "КПД" турнирной сетки - количества полученной информации о соотношении сил, то есть уменьшения неопределенности, за единицу времени.

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

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

P.S. А вот граф Хоффмана-Синглтона на 50 вершин расслаивается на семь "туров"! Шикарно, тем более что количество туров по идее должно быть не меньше, чем двоичный логарифм числа участников.

Tags: Слоупок ФМ, геометрия, турниры
Subscribe

Posts from This Journal “Слоупок ФМ” Tag

promo sevabashirov march 5, 2014 19:02 13
Buy for 10 tokens
Таки да. Промо-блок работает, стартовая сумма за размещение - 10 жжж, ниже некуда. Размещать можно любые посты. То есть абсолютно.
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment