Board  Threads  Posts  Last Post  

Q1 Does each of these lists of vertices form a path in the following graph? Which paths are simple? Which are circuits? What are the lengths of those that are paths?

1  1 
Answer: by vsiap Nov 22, 2014 15:06:17 GMT 

Q2 Determine whether the given graph is connected. 
1  1 
Answer: by vsiap Nov 22, 2014 15:27:54 GMT 

Q3 Determine whether the given graph is connected. 
1  1 
Answer: by vsiap Nov 22, 2014 15:29:37 GMT 

Q4 What do the connected components of acquaintanceship graphs represent? 
1  1 
Answer: by vsiap Nov 22, 2014 15:42:59 GMT 

Q5 Explain why in the collaboration graph of mathematicians (see Example 3 in Section 10.1) a vertex representing a mathematician is in the same connected component as the vertex representing Paul Erdös if and only if that mathematician has a finite Erdös number. 
1  1 
Answer: by vsiap Nov 22, 2014 15:53:50 GMT 

Q6 In the Hollywood graph (see Example 3 in Section 10.1), when is the vertex representing an actor in the same connected component as the vertex representing Kevin Bacon? 
1  1 
Answer: by vsiap Nov 22, 2014 15:57:05 GMT 

Q7 Determine whether each of these graphs is strongly connected and if not, whether it is weakly connected.

1  1 
Answer: by vsiap Nov 22, 2014 16:03:12 GMT 

Q8 Find the strongly connected components of each of these graphs. 
1  1 
Answer: by vsiap Nov 22, 2014 16:07:05 GMT 

Q9 Find the strongly connected components of each of these graphs. 
1  1 
Answer: by vsiap Nov 22, 2014 16:26:53 GMT 

Q10 Show that if G=(V,E) is a directed graph and u,v,and w are vertices in V for which u and v are mutually reachable and v and w are mutually reachable, then u and w are mutually reachable.

1  1 
Answer: by vsiap Nov 22, 2014 16:41:49 GMT 

Q11 Show that if G = (V , E) is a directed graph, then the strong components of two vertices u and v of V are either the same or disjoint. [Hint: Use Exercise 10.] 
1  1 
Answer: by vsiap Nov 22, 2014 16:45:25 GMT 

Q12 Find the number of paths of length n between two different vertices in K_4 if n is

1  1 
Answer: by vsiap Nov 23, 2014 19:38:33 GMT 

Q13 Use paths either to show that these graphs are not isomorphic or to find an isomorphism between them. 
1  1 
Answer: by vsiap Nov 24, 2014 3:58:10 GMT 

Q14 Find the number of paths of length n between any two adjacent vertices in K_(3,3) for the values of n in Exercise 12. 
1  1 
Answer: by vsiap Nov 24, 2014 4:26:09 GMT 

Q15 Find the number of paths of length n between any two nonadjacent vertices in K_(3,3) for the values of n in Exercise 12. 
1  1 
Answer: by vsiap Nov 24, 2014 4:59:09 GMT 

Q16 Find the number of paths between c and d in the graph in Figure 1 of length

1  1 
Answer: by vsiap Nov 25, 2014 2:24:32 GMT 

Q17 Find the number of paths from a to c in the directed graph in Exercise 7(b) of length

1  1 
Answer: by vsiap Nov 25, 2014 3:35:40 GMT 

Q18 Show that every connected graph with n vertices has at least n − 1 edges. 
1  1 
Answer: by vsiap Nov 26, 2014 3:54:38 GMT 

Q19 Let G = (V,E) be a simple graph. Let R be the relation on V consisting of pairs of vertices (u, v) such that there is a path from u to v or such that u = v. Show that R is an equivalence relation. 
1  6 
Answer: by Vernell Feb 18, 2021 14:32:37 GMT 

Q20 Show that in every simple graph there is a path from every vertex of odd degree to some other vertex of odd degree. 
1  1 
Answer: by vsiap Nov 27, 2014 22:20:23 GMT 

Q21 Find all the cut vertices of the given graph. 
3  3 
allahpundit by Hap May 31, 2019 6:59:21 GMT 

Q22 Find all the cut vertices of the given graph. 
1  1 
Answer. by vsiap Nov 26, 2014 4:47:58 GMT 

Q23 Find all the cut vertices of the given graph. 
1  1 
Answer: by vsiap Nov 26, 2014 4:51:42 GMT 

Q24 Find all the cut edges in the graphs in Exercises 21–23. 
1  1 
Answer: by vsiap Nov 26, 2014 23:58:57 GMT 

Q25 A communications link in a network should be provided with a backup link if its failure makes it impossible for some message to be sent. For each of the communications networks shown here in (a) and (b), determine those links that should be backed up. 
1  1 
Answer: by vsiap Nov 27, 2014 22:33:46 GMT 

Q26 Find a vertex basis for each of the directed graphs in Exercises 5–6 of Section 10.2. 
1  1 
Answer: by vsiap Nov 27, 2014 23:14:31 GMT 

Q27 What is the significance of a vertex basis in an influence graph (described in Example 2 of Section 10.1)? Find a vertex basis in the influence graph in that example. 
1  1 
Answer: by vsiap Nov 27, 2014 23:17:15 GMT 

Q28 Show that if a connected simple graph G is the union of the graphs G1 and G2, then G1 and G2 have at least one common vertex.

1  1 
Answer: by vsiap Dec 1, 2014 17:03:39 GMT 

Q29 Show that if a simple graph G has k connected components and these components have n1,n2,...,nk vertices, respectively, then the number of edges of G does not exceed

1  1 
Answer: by vsiap Dec 1, 2014 17:08:47 GMT 

Q30 Use Exercise 29 to show that a simple graph with n vertices and k connected components has at most (n − k)(n − k + 1)/2 edges. [Hint: First show that

0  0  No posts have been made on this board.  
Q31 Show that a simple graph G with n vertices is connected if it has more than (n − 1)(n − 2)/2 edges. 
1  1 
Answer by maholiza Dec 2, 2014 23:29:36 GMT 

Q32 Describe the adjacency matrix of a graph with n connected components when the vertices of the graph are listed so that vertices in each connected component are listed successively.

0  0  No posts have been made on this board.  
Q33 How many nonisomorphic connected simple graphs are there with n vertices when n is

0  0  No posts have been made on this board.  
Q34 Show that each of the following graphs has no cut vertices.

0  0  No posts have been made on this board.  
Q35 Show that each of the graphs in Exercise 34 has no cut edges. 
0  0  No posts have been made on this board.  
Q36 For each of these graphs, find κ(G), λ(G), and min_(v∈V) deg(v), and determine which of the two inequalities in κ(G) ≤ λ(G) ≤ min_(v∈V) deg(v) are strict. 
0  0  No posts have been made on this board.  
Q37 Show that if G is a connected graph, then it is possible to remove vertices to disconnect G if and only if G is not a complete graph. 
0  0  No posts have been made on this board.  
Q38 Show that if G is a connected graph with n vertices then

0  0  No posts have been made on this board.  
Q39 Find κ(K_(m,n)) and λ(K_(m,n)), where m and n are positive integers. 
0  0  No posts have been made on this board.  
Q40 Construct a graph G with κ(G) = 1, λ(G) = 2, and min_(v∈V) deg(v) = 3. 
0  0  No posts have been made on this board.  
Q41 Show that if G is a graph, then κ(G) ≤ λ(G). 
0  0  No posts have been made on this board.  
Q42 Explain how Theorem 2 can be used to find the length of the shortest path from a vertex v to a vertex w in a graph. 
0  0  No posts have been made on this board.  
Q43 Use Theorem 2 to find the length of the shortest path between a and f in the graph in Figure 1. 
0  0  No posts have been made on this board.  
Q44 Use Theorem 2 to find the length of the shortest path from a to c in the directed graph in Exercise 7(b). 
0  0  No posts have been made on this board.  
Q45 Let P1 and P2 be two simple paths between the vertices u and v in the simple graph G that do not contain the same set of edges. Show that there is a simple circuit in G. 
0  0  No posts have been made on this board.  
Q46 Show that the existence of a simple circuit of length k, where k is an integer greater than 2, is an invariant for graph isomorphism. 
0  0  No posts have been made on this board.  
Q47 Explain how Theorem 2 can be used to determine whether a graph is connected. 
0  0  No posts have been made on this board.  
Q48 Use Exercise 47 to show that the graph G1 in Figure 2 is connected whereas the graph G2 in that figure is not connected. 
0  0  No posts have been made on this board.  
Q49 Show that a simple graph G is bipartite if and only if it has no circuits with an odd number of edges.

0  0  No posts have been made on this board.  
Q50 In an old puzzle attributed to Alcuin of York (735–804), a farmer needs to carry a wolf, a goat, and a cabbage across a river. The farmer only has a small boat, which can carry the farmer and only one object (an animal or a vegetable). He can cross the river repeatedly. However, if the farmer is on the other shore, the wolf will eat the goat, and, simi larly, the goat will eat the cabbage. We can describe each state by listing what is on each shore. For example, we can use the pair (FG,WC ) for the state where the farmer and goat are on the first shore and the wolf and cabbage are on the other shore. [The symbol ∅ is used when nothing is on a shore, so that (FWGC, ∅) is the initial state.]

0  0  No posts have been made on this board.  
Q51 Use a graph model and a path in your graph, as in Exercise 50, to solve the jealous husbands problem. Two married couples, each a husband and a wife, want to cross a river. They can only use a boat that can carry one or two people from one shore to the other shore. Each husband is extremely jealous and is not willing to leave his wife with the other husband, either in the boat or on shore. How can these four people reach the opposite shore? 
0  0  No posts have been made on this board.  
Q52 Suppose that you have a threegallon jug and a fivegallon jug. You may fill either jug with water, you may empty either jug, and you may transfer water from either jug into the other jug. Use a path in a directed graph to show that you can end up with a jug containing exactly one gallon. [Hint: Use an ordered pair (a, b) to indicate how much water is in each jug. Represent these ordered pairs by vertices. Add an edge for each allowable operation with the jugs.] 
0  0  No posts have been made on this board. 
Status  Subject  Created By  Replies  Views  Last Post  

No threads were found. 





