Considere um gráfico não direcionado conectado. Um conjunto de arestas correspondente neste gráfico é definido como um conjunto de arestas, de modo que nenhuma duas arestas no conjunto compartilhem um vértice comum. Por exemplo, a figura da esquerda indica um conjunto correspondente em verde, enquanto a figura da direita indica um conjunto não correspondente em vermelho.

Diz- se que maximally matchingum conjunto correspondente é , ou a, maximal matchingse for impossível adicionar outra aresta do gráfico ao conjunto correspondente. Portanto, os dois exemplos acima não são conjuntos de correspondências máximas, mas os dois conjuntos abaixo em azul são correspondências máximas. Observe que as correspondências máximas não são necessariamente únicas. Além disso, não é necessário que o tamanho de cada correspondência máxima possível para um gráfico seja igual a outra correspondência.

O objetivo deste desafio é escrever um programa / função para encontrar uma correspondência máxima de um gráfico.

Entrada

Suponha que todos os vértices do gráfico de entrada tenham uma numeração inteira consecutiva iniciando em qualquer valor inteiro inicial de sua escolha. Uma aresta é descrita por um par não ordenado de números inteiros, indicando os vértices aos quais a aresta se conecta. Por exemplo, o gráfico mostrado acima pode ser descrito com o seguinte conjunto não ordenado de arestas (assumindo que a numeração dos vértices comece em 0):

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

Uma maneira alternativa de descrever um gráfico é através de uma lista de adjacências. Aqui está um exemplo de lista de adjacência para o gráfico acima:

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

Seu programa / função deve ter como entrada um gráfico de qualquer fonte (stdio, parâmetro de função, etc.). Você pode usar qualquer notação desejada, desde que nenhuma informação não trivial adicional seja comunicada ao seu programa. Por exemplo, ter um parâmetro extra indicando o número de arestas de entrada é perfeitamente aceitável. Da mesma forma, é bom passar um conjunto múltiplo não ordenado de arestas, lista de adjacências ou matriz de adjacências.

Você pode assumir:

1. O gráfico está conectado (por exemplo, é possível alcançar qualquer vértice, dado qualquer vértice inicial).
2. Há pelo menos uma aresta.
3. Uma aresta nunca conecta um vértice diretamente a ela mesma (por exemplo, a aresta (1,1)não será fornecida como entrada). Observe que ainda são possíveis ciclos (por exemplo, os gráficos acima).
4. Você pode exigir que os vértices de entrada iniciem em qualquer índice (por exemplo, o primeiro vértice pode ser 0, 1, -1 etc.).
5. A numeração de vértices aumenta sequencialmente a partir do índice inicial escolhido (por exemplo: 1,2,3,4,...ou 0,1,2,3,...).

Resultado

Seu programa / função deve exibir uma lista de arestas indicando um conjunto máximo de correspondências. Uma aresta é definida pelos dois vértices aos quais essa aresta se conecta. Ex. saída para o conjunto azul esquerdo (usando o exemplo de pedido de vértice de entrada):

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

Observe que a ordem dos vértices não é importante; Portanto, a seguinte saída descreve o mesmo conjunto correspondente:

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

A saída pode ser stdout, um arquivo, valor de retorno da função etc.

Exemplos

Aqui estão algumas entradas de exemplo (usando o formato da lista de adjacências). Esses exemplos começam a contar os vértices em 0.

Observe que nenhum exemplo de saída é fornecido. Em vez disso, incluí um código de validação do 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)]

Código de validação Python 3

Aqui está um código de validação do Python 3, que captura um gráfico e um conjunto de arestas e imprime se esse conjunto é o máximo correspondente ou não. Este código funciona com qualquer índice inicial de vértice.

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

Exemplo de uso:

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

Pontuação

Isso é código de golfe; o código mais curto vence. Aplicam-se brechas padrão. Você pode usar quaisquer embutidos desejados.

CJam (16 caracteres)

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

Demonstração online

Essa é uma abordagem gananciosa que acumula arestas que não têm nenhum vértice em comum com as arestas acumuladas anteriormente.

Pitão , 8 bytes

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)

Experimente online!

Especificações

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

Wolfram Language, 25 22 bytes

Guardado 3 bytes graças a @MartinEnder

FindIndependentEdgeSet

Isso leva a entrada como um Graphobjeto (definido como Graph[{1<->2,2<->3,1<-3>}]etc.)

Braquilog , 5 bytes

 ⊇.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

Experimente online!

Isso é garantido no máximo, pois o Brachylog pesquisa no maior subconjunto.

JavaScript (ES6), 67 bytes

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]])

Usa a abordagem gananciosa para obter golfabilidade máxima.

JavaScript (ES6), 68 66 bytes

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

Pensei em tentar a abordagem recursiva e, roubando o truque de cruzamento da @ ETHproduction, consegui minar sua resposta!

Não fui o primeiro a interpretar mal a pergunta original e estava prestes a enviar a seguinte função recursiva que encontra um conjunto máximo de arestas correspondentes, em vez de um conjunto de arestas máximas correspondentes. Diferença sutil, eu sei!

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]||[]

Abordagem recursiva simples. Para cada elemento de entrada, exclui todas as arestas conflitantes do conjunto e localiza o conjunto máximo de arestas correspondentes do subconjunto restante e localiza o resultado máximo sobre cada elemento de entrada. Um pouco ineficiente para conjuntos grandes (é possível uma aceleração de 9 bytes).

Geléia , 12 11 bytes

FQ⁼F
ŒPÇÐfṪ

Experimente online!

Entrada de amostra: [0,1],[0,2],[1,3],[1,4],[2,3],[3,4],[3,5],[5,6]

Saída de amostra: [[1, 4], [2, 3], [5, 6]]

Como funciona

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)