StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strong>Path by Hcycle(V,E):</strong> Call Hcycle() on a graph created by adding one vertex that is connected to all other vertices. If new graph has a cycle than removing new node from that cycle we get path on original graph.</p> <p><strong>Cycle by Hpath(V,E):</strong> Call Hpath() on a graph created by adding one vertex and connecting it to same neighbours as one existing vertex. That means these 2 vertices will have same naighbours. If new graph has a path than at least one path end is on these two vertices. If other vertex is not end, than it is on path third position and by reordering path we can set both vertices to be path end points. Merging these two vertices (since they have same neighbours) we get a cycle in original graph.</p> <p><strike><strong>Path by Hcycle(V,E):</strong> If graph has cycle than it has path also. If graph doesn't have cycle than for each unconnected pair of vertices (<code>v1</code>, <code>v2</code>) add edge between them and check is there a cycle with <code>Hcycle(V,E+(v1,v2))</code>. If there is a cycle than there is a path between <code>v1</code> and <code>v2</code> in original graph. Hcycle is called max <code>|V|^2</code> times.</p> <p><strong>Cycle by Hpath(V,E):</strong> Idea is to force a path to has end vertices we know about. That can be done by constructing graph where two vertices have degree one. Let <code>N(v)</code> be neighbours of <code>v</code>. For an edge <code>(v1,v2)</code> and <code>n1</code> from <code>N(v1)-v2</code> and <code>n2</code> from <code>N(v2)-v1</code> construct a graph by removing all edges from <code>v1</code> except to <code>n1</code>, and removing all edges from <code>v2</code> except to <code>n2</code>. If that graph has a path, than it's ends are on <code>v1</code> and <code>v2</code>, and our original graph has a circle. Hpath is called max <code>|E|*|V|^2</code> times.</strike></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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