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ć:
- Wykres jest połączony (np. Możliwe jest dotarcie do dowolnego wierzchołka przy dowolnym wierzchołku początkowym).
- Istnieje co najmniej jedna krawędź.
- 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). - 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.).
- Numeracja wierzchołków rośnie kolejno od wybranego indeksu początkowego (np .:
1,2,3,4,...lub0,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.
[[0 1] [3 4]]zamiast maksymalnego zestawu[[0 2] [1 4] [3 5]]. ((1, 1)