Content deleted Content added
→Algorithm: reword bullet point 3 to disambiguate (the previous wording could also be read as "find a perfect matching in the subgraph induced in the minimum spanning tree", which is how I read it originally, and it took me a while to realise there was a second potential meaning); also some minor grammar fixes |
|||
Line 11:
# Create a [[minimum spanning tree]] {{mvar|T}} of {{mvar|G}}.
# Let {{mvar|O}} be the set of vertices with odd [[degree (graph theory)|degree]] in {{mvar|T}}. By the [[handshaking lemma]], {{mvar|O}} has an even number of vertices.
# Find a minimum-weight [[perfect matching]] {{mvar|M}} in the subgraph [[induced subgraph|induced]]
# Combine the edges of {{mvar|M}} and {{mvar|T}} to form a connected [[multigraph]] {{mvar|H}} in which each vertex has even degree.
# Form an [[Eulerian circuit]] in {{mvar|H}}.
# Make the circuit found in previous step into a [[Hamiltonian circuit]] by skipping repeated vertices (''shortcutting'').
===Computational complexity===
| |||