Нахождение максимального числа k такое, что для всех комбинаций k пар у нас есть k различных элементов в каждой комбинации

Нам даны N пар. Каждая пара содержит два числа. Нам нужно найти максимальное число K такое, что если мы возьмем какую-либо комбинацию пар J (1 <= J <= K) из данных N пар, мы имеем по меньшей мере J разных чисел во всех выбранных J-парах. Мы можем иметь более одной пары.

Например, рассмотрим пары (1,2) (1,2) (1,2) (7,8) (9,10) Для этого случая K = 2, так как при K > 2, если мы выберем три пары (1,2), мы имеем только два разных числа i.e 1 и 2.

Проверка для каждой возможной комбинации, начиная с одной, займет очень много времени. Что было бы эффективным алгоритмом для решения проблемы?

Ответ 1

Создайте граф с одной вершиной для каждого числа и одного ребра для каждой пары.

Если этот граф является цепью или деревом, мы имеем число "чисел", равное числу "пар" плюс одно. После удаления любого количества ребер из этого графика мы никогда не получаем меньше вершин, чем ребра.

Теперь добавьте один цикл к этой цепочке/дереву. Существует равное количество вершин и ребер. После удаления любого количества ребер из этого графика снова мы не получаем меньше вершин, чем ребра.

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

Теперь добавьте второй цикл к любому из отключенных компонентов. После удаления всех остальных компонентов. наконец, мы имеем больше ребер, чем вершины (больше пар, чем числа).

Все это приводит к выводу, что K + 1 - это точно число ребер в наименьшем возможном подграфе, состоящее из двух циклов и, возможно, цепочки, соединяющих эти циклы.

Алгоритм:

Для каждого подключенного компонента найдите кратчайший цикл, проходящий через каждый node с алгоритмом Флойда-Варшалла.

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

Теперь найдите минимальную длину всех этих подграфов. И вычтите 1.

Вышеуказанный алгоритм вычисляет K, если в графе есть хотя бы одна компонента двойного цикла. Если таких компонентов нет, K = N.

Ответ 2

Кажется, связано с MinCut/MaxFlow. Вот попытка уменьшить его до MinCut/MaxFlow:

- Produce one vertex for each number
- Produce one vertex for each pair
- Produce an edge from number i to a pair if the number is present in the pair, weight 1
- Produce a source node and connect it to all numbers, weight 1 for each connection
- Produce a sink node and connect it to all numbers, weight 1 for each connection

Запуск MaxFlow на этом должен дать вам номер K, так как любой набор из трех пар, который содержит только два числа, будет "заблокирован" ограничениями на исходящих ребрах из числа.

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

Ответ 3

Я сделал некоторый прогресс в этом, но еще не был эффективным решением. Однако это может указывать на способ.

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

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

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

Я продолжаю думать, что какой-то поиск по ширине может найти их в полиномиальное время, но я не понимаю, как это сделать.

Ответ 4

Это эквивалентно обнаружению аккорда, который фиксирует наименьший цикл на графике. Очень наивный алгоритм:

Убедитесь, что удаление края приводит к циклу, содержащему вершины, соответствующие краю. Если да, то отметьте длину самого маленького цикла.