deciding if a graph is "colourable" with 2 colours

This is a discussion on deciding if a graph is "colourable" with 2 colours within the C Programming forums, part of the General Programming Boards category; Hello there! Some months ago, I had to solve an exercise which asked to write a function which receives an ...

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    100

    deciding if a graph is "colourable" with 2 colours

    Hello there!
    Some months ago, I had to solve an exercise which asked to write a function which receives an adjacency matrix and returns 1 or 0 if the graph corresponding to such matrix is colourable or not with 2 colours.. In other words, it asks to check if there are cycles with an odd number of nodes..
    I failed completely that exercise (and unfortunately it was an exam) and never tried to solve it anymore.. Now, I tried again to catch some ideas but all the solutions I can find seems quite complicated... Which could be an easy algorithm to solve the problem? Can you provide me with some links/hints please?

    Thanks a lot!
    Bye!

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    If you know what the words "adjacency matrix" and "cycle" and "odd" mean, then you should be home free. (Hint: If you look at the five-step cycles (for instance) from node N to node N, how would you find how many there are using the adjacency matrix?)

  3. #3
    Registered User
    Join Date
    Oct 2007
    Posts
    100
    Quote Originally Posted by tabstop View Post
    If you know what the words "adjacency matrix" and "cycle" and "odd" mean, then you should be home free. (Hint: If you look at the five-step cycles (for instance) from node N to node N, how would you find how many there are using the adjacency matrix?)
    mhmm..

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. error help making no sense
    By tunerfreak in forum C++ Programming
    Replies: 5
    Last Post: 04-17-2007, 08:55 PM
  2. Help w/ graph as adjacency matrix
    By ac251404 in forum C++ Programming
    Replies: 4
    Last Post: 05-09-2006, 11:25 PM
  3. determining a path through the graph
    By Mist in forum C Programming
    Replies: 2
    Last Post: 02-27-2005, 12:21 PM
  4. plot a graph on the screen
    By dionys in forum C Programming
    Replies: 4
    Last Post: 04-15-2004, 03:46 PM
  5. Minimize crossing edges in undirected graph
    By Shiro in forum C Programming
    Replies: 0
    Last Post: 12-26-2001, 04:48 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21