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

Соответствующий набор называется maximally matchingили, maximal matchingесли невозможно добавить другое ребро графа в соответствующий набор. Таким образом, оба приведенных выше примера не являются максимальными совпадающими наборами, но оба из приведенных ниже синих наборов являются максимальными совпадениями. Обратите внимание, что максимальные соответствия не обязательно являются уникальными. Кроме того, не требуется, чтобы размер каждого возможного максимального соответствия для графа был равен другому соответствию.

Цель этой задачи - написать программу / функцию для поиска максимального соответствия графа.

вход

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

[(0,1), (0,2), (1,3), (1,4), (2,3), (3,4), (3,5), (5,6)]

Альтернативный способ описания графа - через список смежности. Вот пример списка смежности для приведенного выше графика:

[0:(1,2), 1:(0,3,4), 2:(0,3), 3:(1,2,4,5), 4:(1,3), 5:(3,6), 6:(5)]

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

Вы можете предположить:

1. Граф связен (например, можно достичь любой вершины по любой начальной вершине).
2. Есть хотя бы один край.
3. Ребро никогда не соединяет вершину непосредственно с самим собой (например, ребро (1,1)не будет задано в качестве входного). Обратите внимание, что циклы все еще возможны (например: приведенные выше графики).
4. Вы можете потребовать, чтобы входные вершины начинались с любого индекса (например, первая вершина может быть 0, 1, -1 и т. Д.).
5. Нумерация вершин последовательно увеличивается от выбранного вами начального индекса (например 1,2,3,4,..., или 0,1,2,3,...).

Выход

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

[(1,4), (2,3), (5,6)]

Обратите внимание, что порядок вершин не важен; Таким образом, следующий вывод описывает тот же набор соответствия:

[(4,1), (2,3), (6,5)]   

Вывод может быть в стандартный вывод, файл, возвращаемое значение функции и т. Д.

Примеры

Вот несколько примеров ввода (используя формат списка смежности). Эти примеры начинаются с подсчета вершин в 0.

Обратите внимание, что примеры не приводятся, вместо этого я включил код проверки Python 3.

[0:(1), 1:(0)]

[0:(1,2), 1:(0,3,4), 2:(0,3), 3:(1,2,4,5), 4:(1,3), 5:(3,6), 6:(5)]

[0:(1,2), 1:(0,2,3,4,5), 2:(0,1), 3:(1), 4:(1), 5:(1)]

[0:(1,2), 1:(0,2,3), 2:(0,1,4), 3:(1,4,5), 4:(2,3), 5:(3)]

Валидационный код Python 3

Вот код проверки Python 3, который принимает график и набор ребер и выводит, максимально ли совпадает этот набор или нет. Этот код работает с любым начальным индексом вершины.

def is_maximal_matching(graph, edges):
    '''
    Determines if the given set of edges is a maximal matching of graph
    @param graph a graph specified in adjacency list format
    @param edges a list of edges specified as vertex pairs

    @return True if edges describes a maximal matching, False otherwise.
    Prints out some diagnostic text for why edges is not a maximal matching
    '''

    graph_vtxs = {k for k,v in graph.items()}
    vtxs = {k for k,v in graph.items()}

    # check that all vertices are valid and not used multiple times
    for e in edges:
        if(e[0] in graph_vtxs):
            if(e[0] in vtxs):
                vtxs.remove(e[0])
            else:
                print('edge (%d,%d): vertex %d is used by another edge'%(e[0],e[1],e[0]))
                return False
        else:
            print('edge (%d,%d): vertex %d is not in the graph'%(e[0],e[1],e[0]))
            return False
        if(e[1] in graph_vtxs):
            if(e[1] in vtxs):
                vtxs.remove(e[1])
            else:
                print('edge (%d,%d): vertex %d is used by another edge'%(e[0],e[1],e[1]))
                return False
        else:
            print('edge (%d,%d): vertex %d is not in the graph'%(e[0],e[1],e[0]))
            return False
        if(e[1] not in graph[e[0]]):
            print('edge (%d,%d): edge not in graph'%(e[0],e[1]))
            return False

    # check that any edges can't be added
    for v in vtxs:
        ovtxs = graph[v]
        for ov in ovtxs:
            if(ov in vtxs):
                print('could add edge (%d,%d) to maximal set'%(v,ov))
                return False

    return True

Пример использования:

graph = {0:[1,2], 1:[0,3,4], 2:[0,3], 3:[1,2,4,5], 4:[1,3], 5:[3,6], 6:[5]}
candidate = [(0,1),(2,3)]
is_maximal_matching(graph, candidate) // False
candidate = [(0,1),(2,3),(5,6),(0,1)]
is_maximal_matching(graph, candidate) // False
candidate = [(0,1),(2,3),(5,6)]
is_maximal_matching(graph, candidate) // True

счет

Это код гольф; самый короткий код выигрывает. Применяются стандартные лазейки. Вы можете использовать любые встроенные модули по желанию.

CJam (16 символов)

{M\{_2$&!*+}/2/}

Онлайн демо

Это жадный подход, который накапливает ребра, у которых нет вершин, общих с ранее накопленными ребрами.

Pyth , 8 байт

ef{IsTty
       y  power set (gerenate all set of edges)
      t   remove the first one (the first one is
          empty and will cause problems)
 f        filter for sets T satisfying:
     T        T
    s         flatten
  {I          is invariant under deduplicate, i.e. contains no
              duplicating vertices, as the elements represent vertices
e         pick the last one (the power set is ordered from
          smallest to largest)

Попробуйте онлайн!

Спекуляции

• Входные данные: [(0,1), (0,2), (1,3), (1,4), (2,3), (3,4), (3,5), (5,6)]
• Выход: [(1, 4), (2, 3), (5, 6)]

Wolfram Language, 25 22 байта

Сохранено 3 байта благодаря @MartinEnder

FindIndependentEdgeSet

Это принимает входные данные как Graphобъект (определяется как Graph[{1<->2,2<->3,1<-3>}]и т. Д.)

Брахилог , 5 байт

 ⊇.c≠∧

?⊇.cL≠   implicit ? at the beginning;
         ∧ breaks implicit . at the end;
         temporary variable inserted.
?⊇.      input is a superset of output
  .cL    output concatenated is L
    L≠   L contains distinct elements

Попробуйте онлайн!

Это гарантированно будет максимальным, так как Brachylog ищет из наибольшего подмножества.

JavaScript (ES6), 67 байт

let f =
a=>a.map(b=>r.some(c=>c.some(d=>~b.indexOf(d)))||r.push(b),r=[])&&r

let g = a => console.log("[%s]", f(a).map(x => "[" + x + "]").join(", "))
g([[0,1]])
g([[0,1], [0,2], [1,3], [1,4], [2,3], [3,4], [3,5], [5,6]])
g([[0,1], [0,2], [1,2], [1,3], [1,4], [1,5]])
g([[0,1], [0,2], [1,2], [1,3], [2,4], [3,4], [3,5]])

Использует жадный подход для максимальной игры в гольф.

JavaScript (ES6), 68 66 байт

f=a=>a[0]?[a[0],...f(a.filter(b=>!a[0].some(c=>~b.indexOf(c))))]:a
f=([b,...a])=>b?[b,...f(a.filter(c=>!c.some(c=>~b.indexOf(c))))]:a

Я думал, что смогу дать рекурсивный подход, и, украдя уловку пересечения @ ETHproduction, мне удалось подрезать его ответ!

Я не был первым, кто неправильно прочитал исходный вопрос, и я собирался представить следующую рекурсивную функцию, которая находит максимальный набор совпадающих ребер, а не набор максимальных совпадающих ребер. Тонкая разница, я знаю!

f=a=>a.map(([b,c])=>[[b,c],...f(a.filter(([d,e])=>b-d&&b-e&&c-d&&c-e))]).sort((d,e)=>e.length-d.length)[0]||[]

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

Желе , 12 11 байт

FQ⁼F
ŒPÇÐfṪ

Попробуйте онлайн!

Пример ввода: [0,1],[0,2],[1,3],[1,4],[2,3],[3,4],[3,5],[5,6]

Пример вывода: [[1, 4], [2, 3], [5, 6]]

Как это устроено

FQ⁼F    - Helper function, returns 1 if a set of edges is non-matching
F       - Flatten input
 Q      - Remove repeated elements
  ⁼     - Return boolean value. Is this equal to
   F    - The flattened input list

ŒPÇÐfṪ - Main link.
ŒP     - Power set of input list of edges
   Ðf  - Remove all elements which return 1 if
  Ç    - (Helper function) it is a non-matching set
     Ṫ - Get the last element in the resultant list (the longest). 
           Always maximal because it is the longest, so any
           edge added would not be in this list (not matching)