Difference between revisions of "TADM2E 5.17"

From Algorithm Wiki
Jump to: navigation, search
m (Fixed spelling)
(Add solution for a) and explain why solution proposed for b was incorrect.)
 
Line 1: Line 1:
(b) use DFS to find cycle of length 3.
+
(a) Compare every possible set of three vertices and test if there is an edge between the three.
  
we maintain an array parent[i].
+
(b) One may be tempted to use DFS to find cycle of length 3, by maintaining an array parent[I] and check any backedge u-v whether grandparent of u is equal to v. However this is incorrect, consider the graph
  
while processing any backedge u-v we check whether grandparent of u is equal to v .if true we found a cycle of length 3.
+
A - B - C - D - A (square)
grandparentU = parent[parent[u]]
+
  
i,e  grandparentU == v,then found cycle of length 3.stop futher exploration of DFS
+
D - E - F - G - D (another square, connected to the first one through D)
 +
 
 +
A - G (edge that closes the triangle A - D - G).
 +
 
 +
 
 +
DFS would produce:
 +
 
 +
A -> B - > C -> D (grandParent of D is B) -> A (nothing to do, back up the recursion to D and move to the next edge) -> E -> F -> G (grandparent of G is E)
 +
 
 +
At this point we find a cycle when considering the edge G - D, but the grandparent of D isn't connected to G. So we continue and consider A, and then the recursion ends and we process back every node till A, and consider the last edge: A -G. Since A isn't connected to the grandfather of G, we don't find the triangle.
 +
 
 +
Some possible solutions can be found in : http :// i11www.iti.uni-karlsruhe.de/extra/publications/sw-fclt-05_t.pdf

Latest revision as of 06:51, 2 January 2017

(a) Compare every possible set of three vertices and test if there is an edge between the three.

(b) One may be tempted to use DFS to find cycle of length 3, by maintaining an array parent[I] and check any backedge u-v whether grandparent of u is equal to v. However this is incorrect, consider the graph

A - B - C - D - A (square)

D - E - F - G - D (another square, connected to the first one through D)

A - G (edge that closes the triangle A - D - G).


DFS would produce:

A -> B - > C -> D (grandParent of D is B) -> A (nothing to do, back up the recursion to D and move to the next edge) -> E -> F -> G (grandparent of G is E)

At this point we find a cycle when considering the edge G - D, but the grandparent of D isn't connected to G. So we continue and consider A, and then the recursion ends and we process back every node till A, and consider the last edge: A -G. Since A isn't connected to the grandfather of G, we don't find the triangle.

Some possible solutions can be found in : http :// i11www.iti.uni-karlsruhe.de/extra/publications/sw-fclt-05_t.pdf