Медиана для нечётного числа отношений линейного порядка и её использование в задачах группового выбора

Ищется медиана для нечётного числа отношений линейного порядка, заданных на конечном множестве $A $, также являющаяся линейным порядком на $A $. К подобной задаче приходим при исследовании некоторых задач группового выбора. В рассматриваемом случае бинарное отношение $\tilde{\rho}$, имеющее минимальное суммарное расстояние (по Хеммингу) до заданного набора бинарных отношений, является медианой для этих отношений, и притом единственной. Однако эта медиана не всегда является линейным порядком (или даже квазипорядком) и в этих случаях не может быть взята в качестве решения поставленной задачи. Тем не менее бинарное отношение $\tilde{\rho}$ обязательно принадлежит множеству $LA[n]$ (линейных асимметричных бинарных отношений на $A $), которому, в частности, принадлежат и все линейные порядки на $A $. Исследуются некоторые свойства бинарных отношений из $LA[n]$. Вводятся понятия «почти оптимального» и $\Delta$-оптимального отношений, являющихся линейными порядками и одновременно точными решениями поставленной задачи. Приводятся алгоритмы их нахождения, основанные на полученных утверждениях относительно бинарных отношений из $LA[n]$ и имеющие полиномиальную вычислительную сложность. Рассматривается отношение эквивалентности на множестве $LA[n]$, позволяющее разбивать это множество на классы эквивалентности, количество которых $K_n$ намного меньше числа элементов в $LA[n]$. Например, $|LA[5]|=1024$, $K_5=12$. Таким образом, каждое бинарное отношение из $LA[n]$ эквивалентно в точности одному из $K_n$ представителей классов эквивалентности, а следовательно, обладает его основными свойствами. Но тогда исследование широкого класса задач может быть сведено к рассмотрению сравнительно небольшого их набора. Процесс нахождения указанного набора представителей классов эквивалентности иллюстрируется для $n=2, 3, 4, 5$. Приводится также метод решения поставленной задачи, использующий представление бинарных отношений в виде графов (метод выделения минимальных множеств представителей контуров в медиане $\tilde{\rho}$), имеющий экспоненциальную вычислительную сложность.