Sub-Boards 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?
a) a,e,b,c,b
b) a,e,a,d,b,c,a
c) e,b,a,d,b,e
d) c,b,d,a,e,c

by vsiap
Nov 22, 2014 15:06:17 GMT Q2

Determine whether the given graph is connected.

by vsiap
Nov 22, 2014 15:27:54 GMT Q3

Determine whether the given graph is connected.

by vsiap
Nov 22, 2014 15:29:37 GMT Q4

What do the connected components of acquaintanceship graphs represent?

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.

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?

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.

by vsiap
Nov 22, 2014 16:03:12 GMT Q8

Find the strongly connected components of each of these graphs.

by vsiap
Nov 22, 2014 16:07:05 GMT Q9

Find the strongly connected components of each of these graphs.

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.

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.]

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
a) 2.
b) 3.
c) 4.
d) 5.

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.

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.

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.

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
a) 2.
b) 3.
c) 4.
d) 5.
e) 6.
f) 7.

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
a)2.
b)3.
c)4.
d)5.
e)6.
f)7.

by vsiap
Nov 25, 2014 3:35:40 GMT Q18

Show that every connected graph with n vertices has at least n − 1 edges.

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.

by cialis price
Dec 31, 2021 9:10:48 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.

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.

by vsiap
Nov 26, 2014 4:47:58 GMT Q23

Find all the cut vertices of the given graph.

by vsiap
Nov 26, 2014 4:51:42 GMT Q24

Find all the cut edges in the graphs in Exercises 21–23.

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.

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.

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.

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.

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
C(n1,2)+C(n2,2)+...+C(nk,2).

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
(n1)^2+(n2)^2+...+(nk)^2<=n^2-(k-1)(2n-k),
where ni is the number of vertices in the ith connected component.]

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.

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
a) 2?
b) 3?
c) 4?
d) 5?

0 0 No posts have been made on this board. Q34

Show that each of the following graphs has no cut vertices.
a) C_n where n≥3
b) W_n wheren≥3
c) K_(m,n) where m≥2 and n≥2
d) Q_n where n≥2

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
a) κ(G)=n−1 if and only if G=K_(n).
b) λ(G)=n−1 if and only if G=K_(n).

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.]
a) Find all allowable states of the puzzle,where neither the wolf and the goat nor the goat and the cabbage are left on the same shore without the farmer.

b) Construct a graph such that each vertex of this graph represents an allowable state and the vertices representing two allowable states are connected by an edge if it is possible to move from one state to the other using one trip of the boat.

c) Explain why finding a path from the vertex representing (FWGC, ∅) to the vertex representing (∅, FWGC ) solves the puzzle.
d) Find two different solutions of the puzzle,eachusing seven crossings.
e) Suppose that the farmer must pay a toll of one dollar whenever he crosses the river with an animal. Which solution of the puzzle should the farmer use to pay the least total toll?

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 three-gallon jug and a five-gallon 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.

Section 10.4

Status    Subject Created By Replies Views Last Post

Board Information & Statistics Section 10.4 Connectivity   