Results 1 to 2 of 2

Math Help - Triangle-free graph algorithm

  1. #1
    moi
    moi is offline
    Newbie
    Joined
    Apr 2008
    Posts
    3

    Question Triangle-free graph algorithm

    Anybody know how to write an algorithm for testing whether a graph is triangle-free?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by moi View Post
    Anybody know how to write an algorithm for testing whether a graph is triangle-free?
    Here is a thought:

    Write an algorithm to go through every vertex (ie depth first search)

    At each vertex, check if it is part of a triangle.

    To check whether a vertex is part of a triangle, place every vertex it is adjacent to in set A. For every vertex in set A, create a set of every vertex they are adjacent to B_(A_1), B_(A_2), ..., B_(A_n).

    If there is any intersection between A and B_(A_1), or A and B_(A_2), or ..., or A and B_(A_n), then the node being tested is part of a triangle. Therefore there is a triangle in the graph.

    If you go through your search, and this situation never occurs, then there are no triangles in the graph.

    There is probably a better way, but this is the first thing that came to mind.


    I attached a picture to show. The green/blue (though you can barely see the blue) vertex is the node being tested, the red vertices are the vertices that it connects to (set A), the blue vertices are the vertices that are in subset B_(A_k) (the set of vertices which vertex A_k is adjacent to). Notice that the vertex which is half red and half blue is in both set A and set B_(A_k), therefore there is a triangle.
    Attached Thumbnails Attached Thumbnails Triangle-free graph algorithm-graph.jpg  
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algorithm for determining if a graph is possible?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 4th 2010, 01:12 PM
  2. Free market: supply and demand graph
    Posted in the Pre-Calculus Forum
    Replies: 10
    Last Post: November 13th 2009, 06:49 AM
  3. Good free graph software.
    Posted in the Math Software Forum
    Replies: 2
    Last Post: October 21st 2008, 10:43 PM
  4. Graph Algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 2nd 2008, 05:39 AM
  5. Need a graph algorithm
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 6th 2008, 02:27 PM

Search Tags


/mathhelpforum @mathhelpforum