Skip to main content
\(\require{cancel}\newcommand\degree[0]{^{\circ}} \newcommand\Ccancel[2][black]{\renewcommand\CancelColor{\color{#1}}\cancel{#2}} \newcommand{\alert}[1]{\boldsymbol{\color{magenta}{#1}}} \newcommand{\blert}[1]{\boldsymbol{\color{blue}{#1}}} \newcommand{\bluetext}[1]{\color{blue}{#1}} \delimitershortfall-1sp \newcommand\abs[1]{\left|#1\right|} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section18.2Chapter 18 Exercises

Figure18.14
  1. Which of the graphs in Figure18.14 above are trees? Explain how you know.

  2. Given the descriptions below, decide which of these options applies and explain your choice: (T) the graph is definitely a tree, (N) the graph is definitely not a tree, (M) the graph may or may not be a tree (more information is needed).

    1. A network has 12 vertices and 13 edges.
    2. A network has 12 vertices and 12 edges.
    3. A network has 12 vertices and 12 bridges.
    4. A network has 12 vertices and 11 edges.
    5. A network has 12 vertices and at least 11 edges.
    6. A network has 12 vertices and 11 bridges.
    7. A network has 7 vertices (A through G) and there is only one path connecting A and G.
    8. A network has 7 vertices, all of which have degree 2.
  3. The table below gives the distance (in kilometers) between several cities in Nebraska. Use Kruskal's algorithm to find a minimal spanning tree for these cities. Draw the tree and give its total weight.

Figure18.15