My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Algorithms

Algorithms Algorithms and Data Structures - Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum


Reply
 
LinkBack Thread Tools Display Modes
June 16th, 2010, 10:44 PM   #1
 
Joined: Jun 2010
Posts: 1
decide if a graph contains a triangle

Devise an algorithm that will decide if a given graph of n vertices and m edges does or does not contain a triangle (K3), in time O(max{n^2, mn}).

I found this problem in ch.1 of Algorithms and Complexity by H S Wilf. Any ideas are appreciated. Or if you know of some place where an algorithm to do this is explained, tell me. Thanks.
becko is offline  
 

My Computer Forum is free to register and we welcome everyone!

January 30th, 2011, 02:21 PM   #2
 
Joined: Jan 2011
Posts: 1
Re: decide if a graph contains a triangle

My thoughts are, do a depth first transversal from any node to the rest. When you encounter an unvisited node, give it a number representing the distance from the first node, mark it as visited, and continue the transversal. When you encounter a node that is already visited, check if it is the one you visited 1 step back, which would result in a triangle. If it is not, continue the transversal to some other node.

Code:
bool ContainsTriangle(Node[] nodes)
{
	for (int index = 0; index < nodes.length; index++)
	{
		//In case the graph is not connected.
		Node n = nodes[index];
		if (n.visited)
			continue;
		n.visited = true;
		n.nr = 0;
		if (Visit(n)) 
			return true;
	}
	return false;
}

bool Visit(Node n)
{
	foreach (Node n2 in n.neighbors)
	{
		if (n2.visited)
		{
			if (n2.nr == n.nr - 1)
				return true;
			continue;
		}
		n2.visited = true;
		n2.nr = n.nr + 1;
		if (Visit(n2))
			return true;
	}
	return false;
}
Note that Visit is only called once pr node (it is not called if n.visited is true, it sets it to true before calling, and it is never set to false).
Also, the foreach loop in total really only runs once pr edge, since it only runs over the edges going out of the current node.
Now, it's been a long time since my algorithm course, so I probably messed up somewhere, but I get that to O(n + m), which seems strange considering the bound you got from your book..
beier is offline  
December 28th, 2011, 12:50 PM   #3
 
Joined: Dec 2011
Posts: 3
Re: decide if a graph contains a triangle

I would like to add something in this conversation:
There is a theorem that states an upper bound to the number of edges that a graph could have without having a triangle:

"Every graph with n vertices and more than (n^2)/4 edges has a triangle"

So, if you build an algorithm to solve your problem, you could before test the condition from the theorem above. If there is more than (n^2/4) edges in the graph, you don't have to keep running the algorithm, because this graph will have a triangle.

[FYI: I read about this theorem in Bollobas' book "Modern Graph Theory"]
tsouzab is offline  
Reply

  My Computer Forum > Computer Science Forum > Algorithms

Tags
decide, graph, triangle



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Finding an acyclic orientation in a graph Anonymous Coward Algorithms 7 January 24th, 2010 01:28 PM





Copyright © 2018 My Computer Forum Forum. All rights reserved.