Difference between revisions of "TADM2E 5.17"
NotQuantum (talk | contribs) m (Fixed spelling) |
(Add solution for a) and explain why solution proposed for b was incorrect.) |
||
| Line 1: | Line 1: | ||
| − | ( | + | (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 | ||
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
