← Older revision

Revision as of 01:38, 31 July 2020

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

−

----

−

Alternative solution

−

<pre>

−

1. O(|V|^3)

−

- If only adjacency lists are available, convert adjacency lists to the adjacency matrix

−

- If an adjacency matrix is available, traverse the matrix O(|V|^2) get a vertex U and an adjacent M, traverse the M row O(|V|) and check the vertices

−

for adjacency with U O(1)

−

2. O(|V|*|Е|), |V| <= |E|

−

- Data preparation

−

- - Let's analyze the case with the largest upper bound => assume that |V| = |E|

−

- - If an adjacency matrix is available, create additional adjacency lists O(|V|^2)

−

- - If adjacency lists are given, create an additional adjacency matrix O(|V| + |E|) = O(2 * |V|) by assumption ~ O(|V|)

−

- - At this stage, we have adjacency lists and an adjacency matrix, and each element of the adjacency lists also stores its coordinates from the adjacency matrix

−

- Algorithm

−

- - Traverse adjacency lists O(|V| + |E|) vertex U is the owner of the current list, vertex M is a list item

−

- - - Traversing a list owned by M O(|V|) vertex M is the owner of the list, vertex C is a list item

−

- - - - Checking C for adjacency with U O(1), since the coordinates of the vertices are known => row U and column C are known

−

- - Time complexity O(|V| + |E|) * O(|V|) * O(1) ~ O(|V|) * O(|V|) = O(|V|^2) ~ O(|V| * |E|), by assumption |V| = |E|

−

</pre>

−

--[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 10:16, 5 July 2020 (UTC)

TADM2E 5.17 - Revision history

Matt: Undo revision 1050 by FuckMatt (talk)

FuckMatt: Blanked the page

← Older revision	Revision as of 09:31, 31 July 2020
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
	+
	+	----
	+	Alternative solution
	+
	+	<pre>
	+	1. O(\|V\|^3)
	+	- If only adjacency lists are available, convert adjacency lists to the adjacency matrix
	+	- If an adjacency matrix is available, traverse the matrix O(\|V\|^2) get a vertex U and an adjacent M, traverse the M row O(\|V\|) and check the vertices
	+	for adjacency with U O(1)
	+
	+	2. O(\|V\|*\|Е\|), \|V\| <= \|E\|
	+	- Data preparation
	+	- - Let's analyze the case with the largest upper bound => assume that \|V\| = \|E\|
	+	- - If an adjacency matrix is available, create additional adjacency lists O(\|V\|^2)
	+	- - If adjacency lists are given, create an additional adjacency matrix O(\|V\| + \|E\|) = O(2 * \|V\|) by assumption ~ O(\|V\|)
	+	- - At this stage, we have adjacency lists and an adjacency matrix, and each element of the adjacency lists also stores its coordinates from the adjacency matrix
	+
	+	- Algorithm
	+	- - Traverse adjacency lists O(\|V\| + \|E\|) vertex U is the owner of the current list, vertex M is a list item
	+	- - - Traversing a list owned by M O(\|V\|) vertex M is the owner of the list, vertex C is a list item
	+	- - - - Checking C for adjacency with U O(1), since the coordinates of the vertices are known => row U and column C are known
	+	- - Time complexity O(\|V\| + \|E\|) * O(\|V\|) * O(1) ~ O(\|V\|) * O(\|V\|) = O(\|V\|^2) ~ O(\|V\| * \|E\|), by assumption \|V\| = \|E\|
	+	</pre>
	+	--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 10:16, 5 July 2020 (UTC)