Pertimbangkan grafik yang tidak diarahkan yang terhubung. Sebuah cocok set tepi pada grafik ini didefinisikan sebagai satu set tepi sehingga tidak ada dua sisi dalam pangsa set vertex umum. Misalnya, gambar kiri menunjukkan set yang cocok berwarna hijau, sedangkan angka kanan menunjukkan set yang tidak cocok berwarna merah.

Himpunan yang cocok dikatakan sebagai maximally matching, atau maximal matchingjika tidak mungkin untuk menambahkan sisi lain dari grafik ke himpunan yang cocok. Jadi kedua contoh di atas bukan set pencocokan maksimal, tetapi kedua set di bawah ini dalam warna biru adalah pencocokan maksimal. Perhatikan bahwa pencocokan maksimal belum tentu unik. Selain itu, tidak ada persyaratan bahwa ukuran setiap pencocokan maksimal yang mungkin untuk grafik sama dengan pencocokan lain.

Tujuan dari tantangan ini adalah untuk menulis suatu program / fungsi untuk menemukan pencocokan maksimal grafik.

Memasukkan

Asumsikan semua simpul dari grafik input memiliki penomoran bilangan bulat berurutan yang dimulai dari nilai integer awal pilihan Anda. Suatu tepi digambarkan oleh sepasang bilangan bulat yang tidak berurutan yang menunjukkan simpul yang disambungkan ujung tersebut. Misalnya, grafik yang ditunjukkan di atas dapat dijelaskan dengan kumpulan tepi yang tidak berurutan berikut (dengan asumsi penomoran simpul dimulai pada 0):

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

Cara alternatif untuk menggambarkan grafik adalah melalui daftar adjacency. Berikut adalah contoh daftar kedekatan untuk grafik di atas:

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

Program / fungsi Anda harus mengambil input dari sumber apa pun (stdio, parameter fungsi, dll.). Anda dapat menggunakan notasi apa pun yang diinginkan selama tidak ada informasi non-sepele tambahan dikomunikasikan ke program Anda. Sebagai contoh, memiliki parameter tambahan yang menunjukkan jumlah tepi input sangat dapat diterima. Demikian pula, melewatkan multiset tepi yang tidak teratur, daftar adjacency, atau matriks adjacency baik-baik saja.

Anda dapat mengasumsikan:

1. Grafik terhubung (misalnya, dimungkinkan untuk mencapai titik mana pun mengingat titik awal mana pun).
2. Setidaknya ada satu sisi.
3. Edge tidak pernah menghubungkan vertex secara langsung ke dirinya sendiri (mis. Edge (1,1)tidak akan diberikan sebagai input). Perhatikan bahwa siklus masih dimungkinkan (mis .: grafik di atas).
4. Anda mungkin mensyaratkan bahwa simpul input mulai pada indeks apa pun (misalnya simpul pertama bisa 0, 1, -1, dll.).
5. Penomoran vertikal meningkat secara berurutan dari indeks awal yang Anda pilih (mis .: 1,2,3,4,..., atau 0,1,2,3,...).

Keluaran

Program / fungsi Anda harus menampilkan daftar tepi yang menunjukkan set pencocokan maksimal. Tepi ditentukan oleh dua simpul yang disambungkan oleh tepian itu. Ex. output untuk set biru kiri (menggunakan contoh input vertex pemesanan):

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

Perhatikan bahwa urutan simpul tidak penting; Jadi output berikut ini menjelaskan set yang sama:

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

Output mungkin ke stdout, file, nilai pengembalian fungsi, dll.

Contohnya

Berikut adalah beberapa contoh input (menggunakan format daftar adjacency). Contoh-contoh ini mulai menghitung titik di 0.

Perhatikan bahwa tidak ada contoh output yang diberikan, sebagai gantinya saya telah memasukkan kode validasi 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)]

Validasi kode Python 3

Berikut adalah kode validasi Python 3 yang mengambil grafik dan set tepi dan mencetak apakah set itu secara maksimal cocok atau tidak. Kode ini berfungsi dengan indeks titik awal mana pun.

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

Contoh penggunaan:

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

Mencetak gol

Ini adalah kode golf; kode menang paling pendek. Celah standar berlaku. Anda dapat menggunakan built-in yang diinginkan.

CJam (16 karakter)

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

Demo online

Ini adalah pendekatan serakah yang mengakumulasi tepi yang tidak memiliki titik sama dengan tepi yang sebelumnya terakumulasi.

Pyth , 8 byte

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)

Cobalah online!

Spesifikasi

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

Bahasa Wolfram, 25 22 byte

Disimpan 3 byte berkat @MartinEnder

FindIndependentEdgeSet

Ini mengambil input sebagai Graphobjek (didefinisikan sebagai Graph[{1<->2,2<->3,1<-3>}]dll.)

Brachylog , 5 byte

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

Cobalah online!

Ini dijamin maksimal, karena Brachylog mencari dari subset terbesar.

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

Menggunakan pendekatan serakah untuk golfiness maksimal.

JavaScript (ES6), 68 66 byte

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

Saya pikir saya akan memberikan pendekatan rekursif, dan dengan mencuri trik persimpangan set @ ETHproduction saya berhasil memotong jawabannya!

Saya bukan orang pertama yang salah membaca pertanyaan awal, dan saya akan mengirimkan fungsi rekursif berikut yang menemukan satu set tepi pencocokan maksimal, daripada serangkaian tepi pencocokan maksimal. Perbedaan yang halus, saya tahu!

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

Pendekatan rekursif sederhana. Untuk setiap elemen input, hapus semua tepi yang saling bertentangan dari set dan temukan set maksimal tepi yang cocok dari subset yang tersisa, kemudian temukan hasil maksimal di atas setiap elemen input. Agak tidak efisien untuk set besar (9-byte speed-up dimungkinkan).

Jelly , 12 11 byte

FQ⁼F
ŒPÇÐfṪ

Cobalah online!

Input sampel: [0,1],[0,2],[1,3],[1,4],[2,3],[3,4],[3,5],[5,6]

Output sampel: [[1, 4], [2, 3], [5, 6]]

Bagaimana itu bekerja

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)