Медиана для нечётного числа отношений линейного порядка и её использование в задачах группового выбора | Прикладная дискретная математика. 2022. № 57. DOI: 10.17223/20710410/57/7

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