Rozważ dołączony niekierowany wykres. Zestaw dopasowanie krawędzi na tym wykresie jest zdefiniowany jako zbiór krawędziami, tak, że dwa brzegi w zbiorze mają wspólny wierzchołek. Na przykład lewa cyfra oznacza pasujący zestaw na zielono, a prawa cyfra oznacza niepasujący zestaw na czerwono.

Mówi się, że pasujący zestaw jest maximally matching, a maximal matchingjeśli nie można dodać kolejnej krawędzi wykresu do pasującego zestawu. Zatem oba powyższe przykłady nie są maksymalnymi zestawami dopasowań, ale oba poniższe zestawy w kolorze niebieskim są maksymalnymi dopasowaniami. Pamiętaj, że maksymalne dopasowania niekoniecznie są unikalne. Ponadto nie ma wymogu, aby rozmiar każdego możliwego maksymalnego dopasowania dla wykresu był równy drugiemu dopasowaniu.

Celem tego wyzwania jest napisanie programu / funkcji w celu znalezienia maksymalnego dopasowania wykresu.

Wejście

Załóżmy, że wszystkie wierzchołki wykresu wejściowego mają kilka kolejnych liczb całkowitych rozpoczynających się od dowolnej początkowej wartości całkowitej wybranej przez użytkownika. Krawędź jest opisana nieuporządkowaną parą liczb całkowitych oznaczających wierzchołki, które łączy krawędź. Na przykład powyższy wykres można opisać za pomocą następującego nieuporządkowanego zestawu krawędzi (zakładając, że numeracja wierzchołków zaczyna się od 0):

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

Alternatywnym sposobem opisania wykresu jest lista sąsiedztwa. Oto przykładowa lista przylegania dla powyższego wykresu:

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

Twój program / funkcja musi pobierać jako dane wejściowe wykres z dowolnego źródła (stdio, parametr funkcji itp.). Możesz użyć dowolnej zapisanej notacji, o ile do twojego programu nie zostaną przekazane żadne dodatkowe nietrywialne informacje. Na przykład posiadanie dodatkowego parametru oznaczającego liczbę krawędzi wejściowych jest całkowicie dopuszczalne. Podobnie przekazywanie nieuporządkowanego wielosettu krawędzi, listy przylegania lub macierzy przylegania jest w porządku.

Możesz założyć:

1. Wykres jest połączony (np. Możliwe jest dotarcie do dowolnego wierzchołka przy dowolnym wierzchołku początkowym).
2. Istnieje co najmniej jedna krawędź.
3. Zbocze nigdy nie łączy wierzchołka bezpośrednio ze sobą (np. Zbocze (1,1)nie zostanie podane jako dane wejściowe). Należy pamiętać, że cykle są nadal możliwe (np .: powyższe wykresy).
4. Możesz wymagać, aby wierzchołki wejściowe zaczynały się od dowolnego indeksu (np. Pierwszy wierzchołek może mieć wartość 0, 1, -1 itd.).
5. Numeracja wierzchołków rośnie kolejno od wybranego indeksu początkowego (np .: 1,2,3,4,...lub 0,1,2,3,...).

Wynik

Twój program / funkcja powinna wypisać listę krawędzi oznaczających maksymalny zestaw pasujący. Krawędź jest zdefiniowana przez dwa wierzchołki, które łączy ta krawędź. Dawny. dane wyjściowe dla lewego niebieskiego zestawu (przy użyciu przykładowego uporządkowania wierzchołków wejściowych):

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

Zauważ, że kolejność wierzchołków nie jest ważna; Poniższe dane wyjściowe opisują ten sam zestaw pasujący:

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

Wyjściem może być wyjście standardowe, plik, wartość zwracana przez funkcję itp.

Przykłady

Oto kilka przykładowych danych wejściowych (w formacie listy sąsiedztwa). Te przykłady zaczynają się liczyć od wierzchołków 0.

Zauważ, że nie podano żadnych przykładowych danych wyjściowych, zamiast tego podałem kod sprawdzający w Pythonie 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)]

Sprawdzanie poprawności kodu Python 3

Oto kod sprawdzający w Pythonie 3, który pobiera wykres i zestaw krawędzi i drukuje, czy ten zestaw jest maksymalnie zgodny, czy nie. Ten kod działa z dowolnym indeksem początkowym wierzchołków.

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

Przykładowe użycie:

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

Punktacja

To jest kod golfowy; najkrótszy kod wygrywa. Obowiązują standardowe luki. Możesz użyć dowolnych wbudowanych funkcji.

CJam (16 znaków)

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

Demo online

Jest to zachłanne podejście, które gromadzi krawędzie, które nie mają żadnego wspólnego wierzchołka z poprzednio zgromadzonymi krawędziami.

Pyth , 8 bajtów

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)

Wypróbuj online!

Okular

• Wejście: [(0,1), (0,2), (1,3), (1,4), (2,3), (3,4), (3,5), (5,6)]
• Wynik: [(1, 4), (2, 3), (5, 6)]

Wolfram Language, 25 22 bajtów

Zaoszczędź 3 bajty dzięki @MartinEnder

FindIndependentEdgeSet

Pobiera dane wejściowe jako Graphobiekt (zdefiniowany jako Graph[{1<->2,2<->3,1<-3>}]itp.)

Brachylog , 5 bajtów

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

Wypróbuj online!

Jest to z pewnością maksymalne, ponieważ Brachylog wyszukuje z największego podzbioru.

JavaScript (ES6), 67 bajtów

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

Używa chciwego podejścia dla maksymalnej golfisty.

JavaScript (ES6), 68 66 bajtów

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

Pomyślałem, że spróbuję podejść rekursywnie, a kradnąc sztuczkę skrzyżowania @ ETHproduction udało mi się podważyć jego odpowiedź!

Nie byłem pierwszym, który błędnie odczytał oryginalne pytanie, i miałem zamiar przedstawić następującą funkcję rekurencyjną, która znajduje maksymalny zestaw pasujących krawędzi, a nie zestaw maksymalnych pasujących krawędzi. Subtelna różnica, wiem!

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

Proste podejście rekurencyjne. Dla każdego elementu wejściowego usuwa wszystkie sprzeczne krawędzie ze zbioru i znajduje maksymalny zestaw pasujących krawędzi pozostałego podzbioru, a następnie znajduje maksymalny wynik dla każdego elementu wejściowego. Nieco nieefektywny w przypadku dużych zestawów (możliwe przyspieszenie 9 bajtów).

Galaretka , 12 11 bajtów

FQ⁼F
ŒPÇÐfṪ

Wypróbuj online!

Przykładowe dane wejściowe: [0,1],[0,2],[1,3],[1,4],[2,3],[3,4],[3,5],[5,6]

Przykładowe dane wyjściowe: [[1, 4], [2, 3], [5, 6]]

Jak to działa

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)