Graph Theory - please help

Printable View

November 17th 2009, 10:19 AM
MathSucker

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.
November 17th 2009, 11:09 AM
emakarov

Quote:

G is a graph with 25 vertices http://www.mathhelpforum.com/math-he...cf317e30-1.gif and edges
http://www.mathhelpforum.com/math-he...794ef63c-1.gif.

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.
November 17th 2009, 12:27 PM
MathSucker

Quote:

Originally Posted by emakarov

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?