Results 1 to 3 of 3

Math Help - Graph Theory - please help

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    64

    Graph Theory - please help

    I've read through all of my class notes and looked at a number of online tutorials. But questions like this still stump me. My main problem is I have absolutely no idea what it means.

    G is a graph with 25 vertices x_2, x_3, . . . , x_{26} and edges
    \{x_i, x_j\} \Leftrightarrow gcd(i, j) > 1.

    (a) Find the number of connected components.
    (b) Find a spanning tree for each component.

    If somebody could explain the gcd edges part to me in plain English that would be great. Also, does anybody know any good tutorials that have explanations and algorithms that would help me solve a and b? I'm sure this is simple enough, but I don't know where to start.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    G is a graph with 25 vertices and edges
    .
    It apparently means that there is an edge between x_i and x_j if and only if the greatest common divisor (GCD) of i and j is greater than 1.

    Concerning a tutorial, I don't know much, but a long time ago this book: "Discrete Mathematics and Its Applications" by Kenneth Rosen was used in the Discrete Mathematics course in our university (it has new editions). It has chapters on graphs and trees. A more difficult higher-level standard reference for similar things is (or was) "Data Structures and Algorithms" by Aho, Ullman. I am sure there are many online sources as well, starting from Wikipedia.

    For this problem, though, there may be some characteristic about this particular graph that follows from properties of GCD that makes it easier to find those things, and the general algorithm for finding spanning trees may not be the best thing. I am saying this without looking carefully into the problem, but I would advise trying to understand what kind of graph this is and what the definitions of these concepts are, and going into general algorithms later if needed.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2009
    Posts
    64
    Quote Originally Posted by emakarov View Post
    It apparently means that there is an edge between x_i and x_j if and only if the greatest common divisor (GCD) of i and j is greater than 1.
    Well if I find all of the multiples of each prime number between 2 and 13, then I've found all the possible edges for the graph. This leaves me with 5 different complete graphs (not sure what the point of that is though).

    Can somebody give me an example of one connected component and I'll see if I can go from there?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 05:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum