AlbaLed Posted November 3, 2003 Share Posted November 3, 2003 Building blocks of graph theory, more to come !!! 1. How many vertices edges do the following graphs have a) Kn (complete graph) b) Cn (cycle graph) c) Wn (wheel) d) Km,n (biparte ) e) Qn (n-cube graph) 2. State the properties that two graphs must satisfy in order for them to be isomorphic. 3. Define 'strongly connected'/'weakly connected' digraph. 4. What is the minimum number of colors one can color a Cn (circular graph, each node is connected to the next node on the right). Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 3, 2003 Share Posted November 3, 2003 I'll assume undirected edges and let somebody else handle directed, where meaningful. 1. How many vertices edges do the following graphs have a) Kn (complete graph) n*(n-1)/2 or nC2 b) Cn (cycle graph) Do you mean everybody is connected to his right neighbor, in a circle? Then n. c) Wn (wheel) Do you mean it's a circle, and each is also connected to the guy across? Then n + n/2. (n for the circle, plus n/2 for the guy across). d) Km,n (biparte ) Is every one of the m guys on one side connected to every one of the n guys on the other side? If so, then nm. e) Qn (n-cube graph) What the heck is this? A zero dimensional cube is one point, with no neighbors, edges = 0. A one dimensional cube is a line, one edge. A two dimensional cube is a square, 4 edges. A three dimensional cube is a cube, 12 edges. I guess we have 2^n vertices, each of which is connected to n neighbors. So e = n*2^(n-1) n = 0, e = 0 n = 1, e = 1 * 1 = 1 n = 2, e = 2*2 = 4 n = 3, e = 3*2^2 = 3*4 = 12 Seems to work 2. State the properties that two graphs must satisfy in order for them to be isomorphic. They definitely have to have same number of edges and nodes. They also need to have same shape. Not sure what the formal terms are. Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 3, 2003 Author Share Posted November 3, 2003 Nonevent, good job on most of them I should have defined the terms, you only missed wheel wheel n is a circle with n-1 node and a central node connected to all others, like a bicycle wheel :D 2. State the properties that two graphs must satisfy in order for them to be isomorphic. They definitely have to have same number of edges and nodes. They also need to have same shape. Not sure what the formal terms are. Not necessarily the same shape, if you mean by shape the way they look. They need 1. Same number of vertices 2. Same number of edges 3. Vertex degree, there must be a correspondence between vertex x in G1 and vertex f(x) in G2, where f() does the mapping The 3rd property is best described by looking at graphs, if I could only draw???? Check any dicrete math books for this Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 3, 2003 Share Posted November 3, 2003 Ok. Q1 then for wheel, you have n-1 (each of the outside guys to his right neighbor) and then also another n-1 for each to connect to the center, 2n-2. Re Q2, that's what I meant by shape, in the same sense that an apple is the same shape as an orange. :p Quote Link to comment Share on other sites More sharing options...
wood Posted November 4, 2003 Share Posted November 4, 2003 Q2) formally: given graphs G and H, a pair of bijections fv: Vg->Vh and fe: Eg->Eh such that for every edge e E Eg, the endpoints of e are mapped onto the endpoints of fe(e); f is usually used for both the vertex function fv and the edge function fe. Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 4, 2003 Author Share Posted November 4, 2003 thanx wood Quote Link to comment Share on other sites More sharing options...
bb Posted November 4, 2003 Share Posted November 4, 2003 For the best of my understanding shape can be not much alike but in simple words every vertex of n-degree which is connected to I vertices of m-degree, j vertices of k-degree and l vertices of p-degree has to have exact image of itself with exactly the same number of connections to the same degree vertices. And this mapping has to be "one-to-one" and "onto" (every vertex is mapped, none is mapped more then ones). Quote Link to comment Share on other sites More sharing options...
wood Posted November 4, 2003 Share Posted November 4, 2003 3. Define 'strongly connected'/'weakly connected' digraph. A digraph is strongly connected if every two of its vertices are mutually reachable/connected, right? A digraph is weakly connected if the underlying graph is connected. 4. What is the minimum number of colors one can color a Cn (circular graph, each node is connected to the next node on the right). 2 colors if |V| is even. 3 colors if |V| is odd. ?? Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 4, 2003 Share Posted November 4, 2003 Q3) Strongly connected graphs are graphs where every node is reachable from every other node. ("Reachable" means "there is a path involving one or more intermediate edges.") Weakly connected graphs would be strongly connected if it were undirected, but some of the edges point the wrong way so that it's not really strongly connected. http://www.utdallas.edu/~ravip/cs3345/slidesweb/node7.html Q4) If your circle has an even number of edges, then it's bipartite, in which case its chromatic number is 2, per somebody (wood's?) response to an earlier post. If it has an odd number, then you're stuck with 3 colors since when you "get back around" to where you started, the colors don't "line up" right and you are forced to waste an extra color. Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 4, 2003 Author Share Posted November 4, 2003 Goooooooooood !!!!!!!! Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 4, 2003 Share Posted November 4, 2003 :o (You knew that was coming, didn't you?) Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted November 4, 2003 Author Share Posted November 4, 2003 I posted just to be assured :D Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.