3.11.1: Exercises

Last updated
Save as PDF

Page ID: 214471

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\dsum}{\displaystyle\sum\limits} $

$ \newcommand{\dint}{\displaystyle\int\limits} $

$ \newcommand{\dlim}{\displaystyle\lim\limits} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$\newcommand{\longvect}{\overrightarrow}$

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\ket}[1]{\left| #1 \right>}$
$\newcommand{\bra}[1]{\left< #1 \right|}$
$\newcommand{\braket}[2]{\left< #1 \vphantom{#2} \right| \left. #2 \vphantom{#1} \right>}$
$\newcommand{\braopket}[3]{\left< #1 \vphantom{#2}\vphantom{#3} \right| #2 \vphantom{#1}\vphantom{#3} \left| #3 \vphantom{#1}\vphantom{#2} \right>}$
$\newcommand{\qmvec}[1]{\mathbf{\vec{#1}}}$
$\newcommand{\op}[1]{\hat{\mathbf{#1}}}$
$\newcommand{\expect}[1]{\langle #1 \rangle}$
$\newcommand{\dfn}[1]{\emph{\textbf{#1}}}$

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

For the following exercises, refer to the figure shown.

$Four graphs. Graph M has 5 vertices: p, q, t, u, and r. The edges are q t, p u, and u r. Graph W has 11 vertices: a to k. the edges are a e, a f, a b, b g, b h, b c, c i, c d, c k, a j, and j k. Graph R has 7 vertices: a, b, c, d, e, f, and h. The curved edges are a b, b c, c d, d e, and e f. A straight edge connects b and h. Graph X has 10 vertices: a to j. The edges are b a, b c, b d, b i, b f, i e, i g, i h, and i j.$

Exercise $\PageIndex{1}$

Which graphs, if any, are trees?

Exercise $\PageIndex{2}$

Which graphs, if any, are not trees because they are not connected?

Exercise $\PageIndex{3}$

Which graphs, if any, are not trees because they contain a cycle?

For the following exercises, refer to the figure shown. Identify any graphs that fit the given description.

$Six graphs. Graph T 1 has 16 vertices labeled from a, b, c, d, e, f, g, h, I, j, k, m, n, o, r, and s. The edges are b d, b c, b a, a n, b r, b f, r s, r i, e o, o i, i j, j k, i h, i g, and g m. Graph T 2 has 6 vertices: a to f. The edges are a b, a c, a d, a e, and a f. Graph T 3 has 11 vertices: a to k. The edges are b d, f k, k b, b i, i c, a j, j b, b h, h g, and g e. Graph T 4 has 8 vertices: a to h. The edges are a b, b c, c d, d e, e f, f g, and g h. Graph T 5 has 15 vertices: a to o. The edges are a b, b c, b d, b e, e f, e g, e h, e i, e m, m j, m k, m l, m n, and n o. Graph T 6 has 10 vertices: a to j. The edges are a b, a c, a d, a e, a f, j h, h g, and h i.$

Exercise $\PageIndex{4}$

Tree graph

Exercise $\PageIndex{5}$

Star graph

Exercise $\PageIndex{6}$

Star like graph

Exercise $\PageIndex{7}$

Line graph (or path graph)

Exercise $\PageIndex{8}$

Lobster graph

Exercise $\PageIndex{9}$

Caterpillar graph

Exercise $\PageIndex{10}$

Forest graph

For the following exercises, use the figure shown to answer the questions.

$Two graphs. Graph H has 7 vertices: a to g. The edges are a b, a e, b d, e d, d c, d f, f g, and c g. Graph Q has 7 vertices: h to n. The edges are h i, h j, I j, I k, k m, m n, m l, k l, and n l.$

Exercise $\PageIndex{11}$

Determine whether Graph H₁ is a spanning tree of Graph H. If not, explain how you know.

$Graph H 1 has 7 vertices labeled from a to g. The edges are a b, b d, e d, d f, f g, and g c.$

Exercise $\PageIndex{12}$

Determine whether Graph H₂ is a spanning tree of Graph H. If not, explain how you know.

$Graph H 2 has 7 vertices labeled from a to g. The edges are a e, e d, d b, d c, c f, and f g.$

Exercise $\PageIndex{13}$

Determine whether Graph H₃ is a spanning tree of Graph H. If not, explain how you know.

$Graph H 3 has 7 vertices labeled from a to g. The edges are a b, a e, c d, d f, and c g.$

Exercise $\PageIndex{14}$

Determine whether Graph Q₁ is a spanning tree of Graph Q. If not, explain how you know.

$Graph Q 1 has 7 vertices labeled from h to n. The edges are j h, h i, I k, k l, k m, l m, and m n.$

Exercise $\PageIndex{15}$

Determine whether Graph Q₂ is a spanning tree of Graph Q. If not, explain how you know.

$Graph Q 2 has 7 vertices labeled from h to m. The edges are j h, h i, I k, k m, and m l.$

Exercise $\PageIndex{16}$

Determine whether Graph Q₃ is a spanning tree of Graph Q. If not, explain how you know.

$Graph Q 3 has 7 vertices labeled from h to m. The edges are h i, I j, I k, k l, l m, and l n.$

For the following exercises, a student has been asked to construct a spanning tree for Graph O, as shown in the figure. The dashed lines show the first step that the student took, creating a path from vertex h to vertex d.

$Graph O has eight vertices labeled from a to h. The edges are as follows: a f, a e, g f, g e, g h, h e, e f, f b, b c, f c, c d, f d, and d e. The edges, h e, e f, f b, b c, and c d are in dashed lines.$

Exercise $\PageIndex{17}$

How many more edges must be included with the dashed edges to create a spanning tree?

Exercise $\PageIndex{18}$

List three unused (solid) edges from Graph O that cannot be used to complete the spanning tree.

Exercise $\PageIndex{19}$

Give an example of a set of edges that do not have e as an endpoint, which would complete the spanning tree.

Exercise $\PageIndex{20}$

Give an example of a set of edges that do not have f as an endpoint, which would complete the spanning tree.

$Graph O has eight vertices labeled from a to h. The edges are as follows: a f, a e, g f, g e, g h, h e, e f, f b, b c, f c, c d, f d, and d e. The edges, g f, g e, e h, and f c are in dashed lines.$

Exercise $\PageIndex{21}$

How many more edges must be included with the dashed edges to create a spanning tree?

Exercise $\PageIndex{22}$

List two unused edges from Graph O that cannot be used to complete the spanning tree.

Exercise $\PageIndex{23}$

Give an example of a set of edges that do not have f as an endpoint, which would complete the spanning tree.

Exercise $\PageIndex{24}$

Give an example of a set of edges that have neither c nor e as an endpoint, which would complete the spanning tree.

For the following exercises, use Graphs A, B, and C.

$Three graphs. Graph A has two overlapping quadrilaterals, s t u v and w x y z. An edge connects w to u. Graph B has two overlapping quadrilaterals, s t z y, and r v w x. A vertex, u is at the center of r v and t z. Graph C has six vertices. Edges connect s t, t v, v w, w x, x u, w u, u s, and u t.$

Exercise $\PageIndex{25}$

How many edges must be removed from Graph A to create a spanning tree?

Exercise $\PageIndex{26}$

How many edges must be removed from Graph B to create a spanning tree?

Exercise $\PageIndex{27}$

How many edges must be removed from Graph C to create a spanning tree?

Exercise $\PageIndex{28}$

Identify all the distinct cyclic subgraphs of Graph A.

Exercise $\PageIndex{29}$

Identify all the cyclic subgraphs of Graph B.

Exercise $\PageIndex{30}$

Identify all the cyclic subgraphs of Graph C.

Exercise $\PageIndex{31}$

Draw four spanning trees of Graph A each of which includes edges vs, uv, wz and xy.

Exercise $\PageIndex{32}$

Draw four spanning trees of Graph B which includes edge ut, but not ur.

Exercise $\PageIndex{33}$

Draw four spanning trees of Graph C that each have only one edge with an endpoint at vertex u.

For the following exercises, use the figure shown. Draw a graph that fits the given description.

$Four graphs. Each graph has four vertices: a, b, c, and d. The first graph shows the following edges: a c, c d, and c b. The second graph shows the following edges: a b, b d, and d c. The third graph shows the following edges: b a, a c, and cd. The fourth graph shows the following edges: a d, b d, and c d.$

Exercise $\PageIndex{34}$

S₁, S₂, S₃ and S₄ are all spanning trees.

Exercise $\PageIndex{35}$

S₁ and S₂ are spanning trees, but S₄ is not.

Exercise $\PageIndex{36}$

S₃ and S₄ are spanning trees but S₁ is not.

Exercise $\PageIndex{37}$

S₂ and S₃ are spanning trees but S₁ is not.

Exercise $\PageIndex{38}$

S₂ and S₃ are spanning trees but S₄ is not.

Exercise $\PageIndex{39}$

S₁, S_2, and S₃ are spanning trees but S₄ is not.

Exercise $\PageIndex{40}$

S₂, S₃, and S₄ are spanning trees but S₁ is not.

Exercise $\PageIndex{41}$

S₁ and S₄ are spanning trees but S₂ and S₃ are not.

For the following exercises, use the figure shown to find the weight of the given spanning tree.

$Graph Z has nine vertices arranged in 3 rows and 3 columns. The vertices are as follows. Row 1: q, r, s. Row 2: t, u, v. Row 3; w, x, y. The edges are as follows. 1, q to t. 2, s to v. 3, r to s. 4, q to u. 5, u to y. 6, r to v. 7, r to u. 8, v to y. 9, w to x. 10, x to y. 1, u to x. 12, t to w. 13, q to r. 14, t to u. 15, u to v.$

Exercise $\PageIndex{42}$

$A graph has 9 vertices arranged in 3 rows and 3 columns. The vertices are as follows. Row 1: q, r, s. Row 2: t, u, v. Row 3; w, x, y. The edges are as follows: q u, r u, r s, t u, u v, t w, u x, and x y.$

Exercise $\PageIndex{43}$

$A graph has 9 vertices arranged in 3 rows and 3 columns. The vertices are as follows. Row 1: q, r, s. Row 2: t, u, v. Row 3; w, x, y. The edges are as follows: q r, r u, r s, t u, u v, t w, w x, and v y.$

Exercise $\PageIndex{44}$

$A graph has 9 vertices arranged in 3 rows and 3 columns. The vertices are as follows. Row 1: q, r, s. Row 2: t, u, v. Row 3; w, x, y. The edges are as follows: q r, r s, r u, t u, u v, u x, w x, and x y.$

Exercise $\PageIndex{45}$

Use Kruskal’s algorithm to draw a minimum spanning tree for Graph Z in the provided figure. Find its weight.

For the following exercises, draw a minimum spanning tree for the given graph, and calculate its weight.

$Four graphs. Graph A has four vertices: a, b, c, and d. The edges are labeled as follows: a b, 3; b d, 3; d c, 1; c a, 2; a d, 1; b c, 2. Graph B has five vertices: e, f, g, h, and i. The edges are labeled as follows: e f, 2-thirds; f g, 5-twelfths; g h, 1-twelfth; h i, 3-fourths; i e, 1-fourth; e h, 1-half; eg, 1-sixth; f i, -third; f h, 5-sixths; g i, 1. Graph C has five vertices: i, j, k, m, and n. The curved edges are labeled as follows: km, 20; m n, 30; n j, 40; j i, 50; i k, 10. The straight edges are labeled as follows: k j, 90; k n, 60; m i, 100; m j, 70; n i, 80. Graph d has four vertices; o, p, q, and r. The edges are labeled as follows: o p, 1.7; p q, 4.3; q r, 3.5; r o, 2.9 p r, 3.; o p, 1.2.$

Exercise $\PageIndex{46}$

Graph A

Exercise $\PageIndex{47}$

Graph C

Exercise $\PageIndex{48}$

Graph B

Exercise $\PageIndex{49}$

Graph D

For the following exercises, draw a weighted graph to represent the given information. Then use the graph to find a minimum spanning tree and give its weight. Explain what the weight represents in the given scenario.

Exercise $\PageIndex{50}$

City planners are tasked with building roadways to connect locations A, B, C, and D. The cost to build the roadways between any given pair of locations is given in the table.

	A	B	C	D
A	-	125	320	275
B	125	-	110	540
C	320	110	-	1,010
D	275	540	1,010	-

Exercise $\PageIndex{51}$

In a video game, the goal is to visit five different lands, V, W, X, Y and Z, without losing all your lives. The paths between the lands are rated for danger, 1 being lowest and 10 being highest. Once a path has been traversed successfully, it is free from danger. The ratings are given in the table.

	V	W	X	Y	Z
V	-	2	4	9	10
W	2	-	6	8	No Path
X	4	6	-	7	No Path
Y	9	8	7	-	5
Z	10	No Path	No Path	5	-

Exercise \(\PageIndex{1}\)

Exercise \(\PageIndex{2}\)

Exercise \(\PageIndex{3}\)

Exercise \(\PageIndex{4}\)

Exercise \(\PageIndex{5}\)

Exercise \(\PageIndex{6}\)

Exercise \(\PageIndex{7}\)

Exercise \(\PageIndex{8}\)

Exercise \(\PageIndex{9}\)

Exercise \(\PageIndex{10}\)

Exercise \(\PageIndex{11}\)

Exercise \(\PageIndex{12}\)

Exercise \(\PageIndex{13}\)

Exercise \(\PageIndex{14}\)

Exercise \(\PageIndex{15}\)

Exercise \(\PageIndex{16}\)

Exercise \(\PageIndex{17}\)

Exercise \(\PageIndex{18}\)

Exercise \(\PageIndex{19}\)

Exercise \(\PageIndex{20}\)

Exercise \(\PageIndex{21}\)

Exercise \(\PageIndex{22}\)

Exercise \(\PageIndex{23}\)

Exercise \(\PageIndex{24}\)

Exercise \(\PageIndex{25}\)

Exercise \(\PageIndex{26}\)

Exercise \(\PageIndex{27}\)

Exercise \(\PageIndex{28}\)

Exercise \(\PageIndex{29}\)

Exercise \(\PageIndex{30}\)

Exercise \(\PageIndex{31}\)

Exercise \(\PageIndex{32}\)

Exercise \(\PageIndex{33}\)

Exercise \(\PageIndex{34}\)

Exercise \(\PageIndex{35}\)

Exercise \(\PageIndex{36}\)

Exercise \(\PageIndex{37}\)

Exercise \(\PageIndex{38}\)

Exercise \(\PageIndex{39}\)

Exercise \(\PageIndex{40}\)

Exercise \(\PageIndex{41}\)

Exercise \(\PageIndex{42}\)

Exercise \(\PageIndex{43}\)

Exercise \(\PageIndex{44}\)

Exercise \(\PageIndex{45}\)

Exercise \(\PageIndex{46}\)

Exercise \(\PageIndex{47}\)

Exercise \(\PageIndex{48}\)

Exercise \(\PageIndex{49}\)

Exercise \(\PageIndex{50}\)

Exercise \(\PageIndex{51}\)