Considere un gráfico conectado no dirigido. Un conjunto de aristas coincidentes en este gráfico se define como un conjunto de aristas de modo que no haya dos aristas en el conjunto que compartan un vértice común. Por ejemplo, la figura izquierda denota un conjunto coincidente en verde, mientras que la figura derecha denota un conjunto no coincidente en rojo.

Se dice que un conjunto coincidente es maximally matching, o a maximal matchingsi es imposible agregar otro borde del gráfico al conjunto coincidente. Por lo tanto, los dos ejemplos anteriores no son conjuntos de coincidencia máxima, pero los dos conjuntos a continuación en azul son coincidencias máximas. Tenga en cuenta que las coincidencias máximas no son necesariamente únicas. Además, no se exige que el tamaño de cada coincidencia máxima posible para un gráfico sea igual a otra coincidencia.

El objetivo de este desafío es escribir un programa / función para encontrar una coincidencia máxima de un gráfico.

Entrada

Suponga que todos los vértices del gráfico de entrada tienen una numeración entera consecutiva que comienza en cualquier valor entero inicial que elija. Un borde se describe mediante un par de enteros desordenados que denotan los vértices que conecta el borde. Por ejemplo, el gráfico que se muestra arriba podría describirse con el siguiente conjunto desordenado de aristas (suponiendo que la numeración de vértices comienza en 0):

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

Una forma alternativa de describir un gráfico es a través de una lista de adyacencia. Aquí hay un ejemplo de lista de adyacencia para el gráfico anterior:

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

Su programa / función debe tomar como entrada un gráfico de cualquier fuente (stdio, parámetro de función, etc.). Puede usar cualquier notación deseada siempre que no se comunique información no trivial adicional a su programa. Por ejemplo, tener un parámetro adicional que indique el número de bordes de entrada es perfectamente aceptable. De manera similar, pasar un conjunto múltiple de bordes desordenado, una lista de adyacencia o una matriz de adyacencia está bien.

Puedes asumir:

1. El gráfico está conectado (por ejemplo, es posible alcanzar cualquier vértice dado cualquier vértice inicial).
2. Hay al menos un borde.
3. Un borde nunca conecta un vértice directamente a sí mismo (por ejemplo, el borde (1,1)no se dará como entrada). Tenga en cuenta que los ciclos aún son posibles (p. Ej .: los gráficos anteriores).
4. Puede requerir que los vértices de entrada comiencen en cualquier índice (por ejemplo, el primer vértice puede ser 0, 1, -1, etc.).
5. La numeración de vértices aumenta secuencialmente desde el índice inicial elegido (por ejemplo 1,2,3,4,..., o 0,1,2,3,...).

Salida

Su programa / función debería generar una lista de bordes que denota un conjunto de coincidencia máxima. Un borde se define por los dos vértices que ese borde conecta. Ex. salida para el conjunto azul izquierdo (usando el ejemplo de ordenamiento de vértices de entrada):

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

Tenga en cuenta que el orden de los vértices no es importante; Entonces, el siguiente resultado describe el mismo conjunto coincidente:

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

La salida puede ser stdout, un archivo, valor de retorno de función, etc.

Ejemplos

Aquí hay algunas entradas de ejemplo (usando el formato de lista de adyacencia). Estos ejemplos comienzan a contar vértices en 0.

Tenga en cuenta que no se proporcionan resultados de ejemplo, sino que he incluido un código de validación de 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 validación Python 3

Aquí hay un código de validación de Python 3 que toma un gráfico y un conjunto de bordes e imprime si ese conjunto coincide al máximo o no. Este código funciona con cualquier índice de inicio 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

Ejemplo 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

Puntuación

Este es el código de golf; el código más corto gana. Se aplican lagunas estándar. Puede usar los complementos deseados.

CJam (16 caracteres)

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

Demostración en línea

Este es un enfoque codicioso que acumula bordes que no tienen ningún vértice en común con los bordes acumulados previamente.

Pyth , 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)

Pruébalo en línea!

Especificaciones

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

Wolfram Language, 25 22 bytes

Guardado 3 bytes gracias a @MartinEnder

FindIndependentEdgeSet

Esto toma la entrada como un Graphobjeto (definido como Graph[{1<->2,2<->3,1<-3>}]etc.)

Brachylog , 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

Pruébalo en línea!

Se garantiza que esto es máximo, ya que Brachylog busca desde el subconjunto más grande.

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

Utiliza el enfoque codicioso para la máxima golfidad.

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

Pensé darle una oportunidad al enfoque recursivo, y al robar el truco de intersección establecido de @ ETHproduction logré socavar su respuesta.

No fui el primero en leer mal la pregunta original, y estaba a punto de presentar la siguiente función recursiva que encuentra un conjunto máximo de bordes coincidentes, en lugar de un conjunto de bordes coincidentes máximos. Sutil diferencia, lo sé!

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

Enfoque recursivo simple. Para cada elemento de entrada, elimina todos los bordes en conflicto del conjunto y encuentra el conjunto máximo de bordes coincidentes del subconjunto restante, luego encuentra el resultado máximo sobre cada elemento de entrada. Algo ineficiente para conjuntos grandes (posible aceleración de 9 bytes).

Jalea , 12 11 bytes

FQ⁼F
ŒPÇÐfṪ

Pruébalo en línea!

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

Salida de muestra: [[1, 4], [2, 3], [5, 6]]

Cómo 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)