Considérons un graphique connecté non orienté. Un ensemble d'arêtes correspondant sur ce graphique est défini comme un ensemble d'arêtes de sorte qu'il n'y ait pas deux arêtes dans l'ensemble partageant un sommet commun. Par exemple, la figure de gauche indique un ensemble correspondant en vert, tandis que la figure de droite indique un ensemble non correspondant en rouge.

Un ensemble correspondant est dit maximally matchingou maximal matchings'il est impossible d'ajouter un autre bord du graphique à l'ensemble correspondant. Ainsi, les deux exemples ci-dessus ne sont pas des ensembles de correspondances maximales, mais les deux ensembles ci-dessous en bleu sont des correspondances maximales. Notez que les correspondances maximales ne sont pas nécessairement uniques. De plus, il n'est pas nécessaire que la taille de chaque correspondance maximale possible pour un graphique soit égale à une autre correspondance.

Le but de ce défi est d'écrire un programme / fonction pour trouver une correspondance maximale d'un graphique.

Contribution

Supposons que tous les sommets du graphe d'entrée aient une numérotation entière consécutive commençant à n'importe quelle valeur entière de début de votre choix. Une arête est décrite par une paire d'entiers non ordonnés indiquant les sommets auxquels l'arête se connecte. Par exemple, le graphique ci-dessus pourrait être décrit avec l'ensemble d'arêtes non ordonné suivant (en supposant que la numérotation des sommets commence à 0):

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

Une autre façon de décrire un graphe est d'utiliser une liste d'adjacence. Voici un exemple de liste d'adjacence pour le graphique ci-dessus:

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

Votre programme / fonction doit prendre en entrée un graphe de n'importe quelle source (stdio, paramètre de fonction, etc.). Vous pouvez utiliser n'importe quelle notation souhaitée tant qu'aucune information non triviale supplémentaire n'est communiquée à votre programme. Par exemple, avoir un paramètre supplémentaire indiquant le nombre de bords d'entrée est parfaitement acceptable. De même, la transmission d'un ensemble multiple non ordonné de bords, d'une liste d'adjacence ou d'une matrice d'adjacence est correcte.

Vous pouvez supposer:

1. Le graphe est connecté (par exemple, il est possible d'atteindre n'importe quel sommet avec n'importe quel sommet de départ).
2. Il y a au moins un bord.
3. Une arête ne connecte jamais un sommet directement à elle-même (ex. L'arête (1,1)ne sera pas donnée en entrée). Notez que les cycles sont toujours possibles (ex.: Les graphiques ci-dessus).
4. Vous pouvez exiger que les sommets d'entrée commencent à n'importe quel index (par exemple, le premier sommet peut être 0, 1, -1, etc.).
5. La numérotation des sommets augmente séquentiellement à partir de votre index de départ choisi (ex .: 1,2,3,4,..., ou 0,1,2,3,...).

Production

Votre programme / fonction devrait produire une liste d'arêtes indiquant un ensemble de correspondance maximal. Une arête est définie par les deux sommets auxquels cette arête se connecte. Ex. sortie pour l'ensemble bleu de gauche (en utilisant l'exemple de classement des sommets d'entrée):

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

Notez que l'ordre des sommets n'est pas important; Ainsi, la sortie suivante décrit le même ensemble correspondant:

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

La sortie peut être vers stdout, un fichier, une valeur de retour de fonction, etc.

Exemples

Voici quelques exemples d'entrées (en utilisant le format de liste d'adjacence). Ces exemples commencent à compter les sommets à 0.

Notez qu'aucun exemple de sortie n'est donné, à la place, j'ai inclus un code de validation 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)]

Validation du code Python 3

Voici un code de validation Python 3 qui prend un graphique et un ensemble d'arêtes et affiche si cet ensemble correspond au maximum ou non. Ce code fonctionne avec n'importe quel index de début de sommet.

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

Exemple d'utilisation:

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

Notation

C'est le golf de code; le code le plus court gagne. Des échappatoires standard s'appliquent. Vous pouvez utiliser toutes les fonctions intégrées souhaitées.

CJam (16 caractères)

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

Démo en ligne

Il s'agit d'une approche gourmande qui accumule des arêtes qui n'ont aucun sommet en commun avec les arêtes accumulées précédemment.

Pyth , 8 octets

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)

Essayez-le en ligne!

Spécifications

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

Langue Wolfram, 25 22 octets

Sauvegardé 3 octets grâce à @MartinEnder

FindIndependentEdgeSet

Cela prend l'entrée comme un Graphobjet (défini comme Graph[{1<->2,2<->3,1<-3>}]etc.)

Brachylog , 5 octets

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

Essayez-le en ligne!

Ceci est garanti d'être maximal, car Brachylog recherche dans le plus grand sous-ensemble.

JavaScript (ES6), 67 octets

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

Utilise l'approche gourmande pour un golfe maximal.

JavaScript (ES6), 68 66 octets

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

Je pensais que j'allais essayer l'approche récursive, et en volant l'astuce d'ensemble d'intersection de @ ETHproduction, j'ai réussi à saper sa réponse!

Je n'étais pas le premier à avoir mal lu la question d'origine, et j'étais sur le point de soumettre la fonction récursive suivante qui trouve un ensemble maximal de bords correspondants, plutôt qu'un ensemble de bords correspondants maximaux. Différence subtile, je sais!

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

Approche récursive simple. Pour chaque élément d'entrée, supprime tous les bords en conflit de l'ensemble et trouve l'ensemble maximal d'arêtes correspondantes du sous-ensemble restant, puis trouve le résultat maximal sur chaque élément d'entrée. Un peu inefficace pour les grands ensembles (accélération de 9 octets possible).

Gelée , 12 11 octets

FQ⁼F
ŒPÇÐfṪ

Essayez-le en ligne!

Exemple d'entrée: [0,1],[0,2],[1,3],[1,4],[2,3],[3,4],[3,5],[5,6]

Exemple de sortie: [[1, 4], [2, 3], [5, 6]]

Comment ça fonctionne

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)