Betrachten Sie einen verbundenen ungerichteten Graphen. Eine übereinstimmende Menge von Kanten in diesem Diagramm wird als eine Menge von Kanten definiert, sodass keine zwei Kanten in der Menge einen gemeinsamen Scheitelpunkt haben. Beispielsweise kennzeichnet die linke Abbildung eine Übereinstimmungsmenge in Grün, während die rechte Abbildung eine nicht übereinstimmende Menge in Rot kennzeichnet.

Eine übereinstimmende Menge wird als " maximally matchingoder" bezeichnet, maximal matchingwenn es nicht möglich ist, der übereinstimmenden Menge eine weitere Kante des Diagramms hinzuzufügen. Die beiden obigen Beispiele sind also keine maximalen Übereinstimmungen, aber beide Sätze in Blau sind maximale Übereinstimmungen. Beachten Sie, dass maximale Übereinstimmungen nicht unbedingt eindeutig sind. Darüber hinaus ist es nicht erforderlich, dass die Größe jeder möglichen maximalen Übereinstimmung für ein Diagramm einer anderen Übereinstimmung entspricht.

Das Ziel dieser Herausforderung ist es, ein Programm / eine Funktion zu schreiben, um eine maximale Übereinstimmung eines Graphen zu finden.

Eingang

Angenommen, alle Eckpunkte des Eingabediagramms haben eine fortlaufende Ganzzahlennummerierung, beginnend mit einem beliebigen ganzzahligen Anfangswert Ihrer Wahl. Eine Kante wird durch ein ungeordnetes Paar von Ganzzahlen beschrieben, die die Eckpunkte bezeichnen, die die Kante verbindet. Das oben gezeigte Diagramm könnte zum Beispiel mit der folgenden ungeordneten Menge von Kanten beschrieben werden (unter der Annahme, dass die Nummerierung der Scheitelpunkte bei 0 beginnt):

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

Eine alternative Möglichkeit, ein Diagramm zu beschreiben, ist die Verwendung einer Adjazenzliste. Hier ist ein Beispiel einer Adjazenzliste für das obige Diagramm:

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

Ihr Programm / Ihre Funktion muss einen Graphen aus einer beliebigen Quelle (stdio, Funktionsparameter usw.) als Eingabe verwenden. Sie können jede gewünschte Notation verwenden, solange Ihrem Programm keine zusätzlichen nicht-trivialen Informationen übermittelt werden. Zum Beispiel ist es vollkommen akzeptabel, einen zusätzlichen Parameter zu haben, der die Anzahl der Eingangsflanken angibt. In ähnlicher Weise ist die Übergabe eines ungeordneten Mehrfachsatzes von Kanten, einer Adjazenzliste oder einer Adjazenzmatrix in Ordnung.

Sie können annehmen:

1. Der Graph ist verbunden (z. B. ist es möglich, einen beliebigen Scheitelpunkt mit einem beliebigen Startscheitelpunkt zu erreichen).
2. Es gibt mindestens eine Kante.
3. Eine Kante verbindet niemals einen Scheitelpunkt direkt mit sich selbst (z. (1,1)B. wird die Kante nicht als Eingabe angegeben). Beachten Sie, dass noch Zyklen möglich sind (Beispiel: die obigen Grafiken).
4. Möglicherweise müssen die Eingabe-Vertices an einem beliebigen Index beginnen (z. B. kann der erste Vertex 0, 1, -1 usw. sein).
5. Die Scheitelpunktnummerierung wird ab dem von Ihnen gewählten Startindex (z. B. 1,2,3,4,...oder 0,1,2,3,...) fortlaufend erhöht .

Ausgabe

Ihr Programm / Ihre Funktion sollte eine Liste von Kanten ausgeben, die eine maximale Übereinstimmungsmenge angibt. Eine Kante wird durch die beiden Eckpunkte definiert, die diese Kante verbindet. Ex. Ausgabe für die linke blaue Menge (anhand des Beispiels für die Reihenfolge der Eingabescheitelpunkte):

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

Beachten Sie, dass die Reihenfolge der Scheitelpunkte nicht wichtig ist. Die folgende Ausgabe beschreibt also dieselbe Übereinstimmungsmenge:

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

Die Ausgabe kann auf stdout, eine Datei, einen Funktionsrückgabewert usw. erfolgen.

Beispiele

Hier sind einige Beispieleingaben (unter Verwendung des Adjazenzlistenformats). Diese Beispiele beginnen mit dem Zählen von Eckpunkten bei 0.

Beachten Sie, dass keine Beispielausgaben angegeben werden. Stattdessen habe ich einen Python 3-Validierungscode eingefügt.

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

Validierungs-Python 3-Code

Hier ist ein Python 3-Validierungscode, der ein Diagramm und eine Reihe von Kanten aufnimmt und ausgibt, ob diese Reihe maximal übereinstimmt oder nicht. Dieser Code funktioniert mit jedem Vertex-Startindex.

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

Beispielverwendung:

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

Wertung

Das ist Code Golf; kürzester Code gewinnt. Es gelten Standardlücken. Sie können beliebige integrierte Funktionen verwenden.

CJam (16 Zeichen)

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

Online-Demo

Dies ist ein gieriger Ansatz, bei dem Kanten akkumuliert werden, die mit den zuvor akkumulierten Kanten keinen Scheitelpunkt gemeinsam haben.

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)

Probieren Sie es online!

Technische Daten

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

Wolfram-Sprache, 25 22 Bytes

3 Bytes gespart dank @MartinEnder

FindIndependentEdgeSet

Dies nimmt Eingaben als GraphObjekt (definiert als 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

Probieren Sie es online!

Dies ist garantiert maximal, da Brachylog aus der größten Teilmenge sucht.

JavaScript (ES6), 67 Byte

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

Nutzt den gierigen Ansatz für maximale Golffreundlichkeit.

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

Ich dachte, ich würde den rekursiven Ansatz ausprobieren, und indem ich den von @ ETHproduction festgelegten Kreuzungstrick stahl, gelang es mir, seine Antwort zu unterbieten!

Ich war nicht der erste, der die ursprüngliche Frage falsch interpretiert hat, und wollte die folgende rekursive Funktion einreichen, die eine maximale Menge von Übereinstimmungskanten anstelle einer Menge von maximalen Übereinstimmungskanten findet. Subtiler Unterschied, ich weiß!

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

Einfacher rekursiver Ansatz. Löscht für jedes Eingabeelement alle widersprüchlichen Kanten aus der Menge und ermittelt die maximale Menge übereinstimmender Kanten der verbleibenden Teilmenge. Anschließend wird das maximale Ergebnis für jedes Eingabeelement ermittelt. Etwas ineffizient für große Gruppen (9-Byte-Beschleunigung möglich).

Jelly , 12 11 Bytes

FQ⁼F
ŒPÇÐfṪ

Probieren Sie es online!

Beispieleingabe: [0,1],[0,2],[1,3],[1,4],[2,3],[3,4],[3,5],[5,6]

Beispielausgabe: [[1, 4], [2, 3], [5, 6]]

Wie es funktioniert

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)