Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Indeed, <a href="http://en.wikipedia.org/wiki/Ore%27s_theorem#Algorithm" rel="nofollow">wikipedia's description</a> of the algorithm <del>is¹</del> was wrong. Palmer's own description is</p> <blockquote> <ol> <li><p>Step 0. Arrange the vertices in a circle.</p></li> <li><p>Step 1. Look around the boundary, say in the counterclockwise direction, for consecutive nonadjacent vertices, i.e., a gap. If there are no gaps, quit with the spanning cycle on the boundary. Otherwise, look for a pair of crossing chords from the vertices of the gap to some other pair of consecutive vertices that may or may not be adjacent (possible gap 2).</p> <p>If found, (i.e., gap 1 was good!), simply rearrange the circular order of the vertices in the obvious way so that the two chords become edges on the boundary and the gaps are switched to the interior. Each time we play this game of criss-cross successfully, one or two gaps on the boundary of the circular arrangement of vertices are replaced by two edges. Otherwise repeat Step 1 with the next gap.</p> <p>Continue until the spanning cycle is on the boundary, or until every gap is bad.</p></li> </ol> </blockquote> <p>You need a pair of <strong>crossing</strong> chords, i.e. you need edges</p> <pre><code>v_i &lt;-&gt; v_j v_{i+1} &lt;-&gt; v_{j+1} </code></pre> <p>That way, by reversing the part from <code>v_{i+1}</code> to <code>v_j</code> (inclusive), you move the vertex <code>v_j</code> - adjacent to <code>v_i</code> in the graph - next to <code>v_i</code> in your cycle, and the vertex <code>v_{i+1}</code> - adjacent to <code>v_{j+1}</code> in the graph - is moved next to <code>v_{j+1}</code> in the cycle. Thus we obtain two new pairs of neighbours in the cycle that are adjacent in the graph, <code>(v_i, v_j)</code> and <code>(v_{i+1}, v_{j+1})</code>, and possibly destroy <em>one</em> pair of cycle-neighbours that are adjacent in the graph, <code>(v_j, v_{j+1})</code>. The number of pairs of cycle-neighbours that are adjacent in the graph increases by 1 or by two each step, so the algorithm terminates.</p> <p>With the wrong indexing of wikipedia, moving <code>v_j</code> next to <code>v_i</code> and <code>v_{i+1}</code> next to <code>v_{j+1}</code> need not generate a new pair of cycle-neighbours that are adjacent in the graph, thus the algorithm need not terminate.</p> <p>So let's play it through for your example</p> <pre><code>E = { (1,2), (1,3), (1,6), (3,2), (3,4), (5,2), (5,4), (6,4), (6,5) } </code></pre> <p>arranging it as <code>1426351</code> initially (no adjacent neighbours).</p> <p>The first pair of cycle-neighbours not adjacent in the graph is <code>(1,4) = (v_1,v_2)</code>. Scan for an index <code>j &gt; 2</code> such that <code>v_j</code> is adjacent to <code>v_1</code> and <code>v_{j+1}</code> to <code>v_2</code>, the first such occurrence is <code>j = 3</code>. Now reverse the part <code>4...2</code> in the cycle (in this case, there's no vertex between 4 and 2), giving the next cycle</p> <pre><code>1234561 // index in cycle 1246351 // vertex </code></pre> <p>with two pairs of adjacent neighours (<code>(1,2)</code> and <code>(4,6)</code>). The first index <code>i</code> with <code>v_i</code> not adjacent to <code>v_{i+1}</code> is 2. Scan for the first <code>j &gt; 3</code> such that <code>v_j</code> is adjacent to <code>v_2 = 2</code> and <code>v_{j+1}</code> adjacent to <code>v_3 = 4</code>. That gives <code>j = 5</code>. Now the part between <code>v_3</code> and <code>v_5</code> (inclusive), giving the next cycle</p> <pre><code>1234561 // index in cycle 1236451 // vertex </code></pre> <p>Once more, <code>v_3 = 3</code> is not adjacent to <code>v_4 = 6</code>, so <code>i = 3</code>, <code>j = 5</code>, reversing yields</p> <pre><code>1234561 // index in cycle 1234651 // vertex </code></pre> <p>Now the only bad pair is <code>(v_6,v_1) = (5,1)</code>. The smallest <code>j &gt; 1</code> such that <code>v_j</code> is adjacent to <code>v_6 = 5</code> and <code>v_{j+1}</code> to <code>v_1 = 1</code> is <code>j = 2</code>. Now reverse the part from <code>v_1</code> to <code>v_2</code> yielding</p> <pre><code>1234561 // index in cycle 2134652 // vertex </code></pre> <p>which is a Hamiltonian cycle.</p> <p>¹ I'll fix it in a moment.</p>
    singulars
    1. This table or related slice is empty.
    1. POPalmer's Algorithm for Hamiltonian cycles
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USDaniel Fischer
    1. USDaniel Fischer
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POPalmer's Algorithm for Hamiltonian cycles
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThank you very much Daniel, I also noticed that Wikipedia made that mistake but I solved it in a different way than yours....Maybe similar but not exactly the same. Anyway Problem solved....Thank you for your effort....I checked your solution and made sure it works....By the way, do you know what should I do in this case (when Wikipedia makes such mistake)...I mean readers will suffer like me. (I have been suffering for 3 weeks).
      singulars
      1. PO
      1. USTraveling Salesman
    2. COIf you find an error in a Wikipedia article, correct it (and give a reason why the old one was wrong), it's a wiki. Unrelated, instead of posting a non-answer, you should have commented on my answer, that would also have notified me. (But, I see your gravatar is different, so it's not your question, as far as the system is concerned, and you couldn't comment on it from that account. Wouldn't it be better to merge your accounts?)
      singulars
      1. PO
      1. USDaniel Fischer
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload