2
$\begingroup$

I'm trying to implement it from wiki but the step 3 confuses me:

  1. Create a minimum spanning tree T of G.
  2. Let O be the set of vertices with odd degree in T. By the handshaking lemma, O has an even number of vertices.
  3. Find a minimum-weight perfect matching M in the induced subgraph given by the vertices from O.
  4. Combine the edges of M and T to form a connected multigraph H in which each vertex has even degree.
  5. Form an Eulerian circuit in H.
  6. Make the circuit found in previous step into a Hamiltonian circuit by skipping repeated vertices (shortcutting).

Induced subgraph I (from odd vertices of O) is taken over G, so it is complete as well as G so there will be multiple perfect matchings.

All Hungarian/Munkres algorithms which I've seen work with Edmonds matrix. To get Edmonds from an arbitrary complete graph I have to 1) split graph into 2 sets of vertices U, V 2) having a split done, perform a minimum matching search in it.

Choosing different sets U, V will give different minimum perfect matchings weight. So the question is how to get a minimum perfect matching in I having a distance matrix of I.

$\endgroup$
  • $\begingroup$ The induced subgraph is only using the vertices of O (those with odd degree in T) - there are helpful examples with images on that wiki page... $\endgroup$ – gilleain Sep 18 '17 at 15:15
  • $\begingroup$ Thanks. I've updated the question. $\endgroup$ – VladimirLenin Sep 19 '17 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.