Login Registrieren

Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Discrete Mathematics and its Applications

Kenneth H. Rosen

$Math Studyset Vaia Explanations$ Math

7th Edition · 808 pages

ISBN: 9780073383095

Chapter 11: Q9E (page 802)

Find a connected weighted simple graph with the fewestedges possible that has more than one minimum spanning tree.

Short Answer

Expert verified

The connected weighted graph is

Step by step solution

01

Definition

A graph is connected if there exists a path between every pair of vertices.

02

Weight of the edge

The easiest weighted simple graph with more than one spanning tree, are weighted simple graphs with the same weight on each edge and with more than \({\bf{n - 1}}\) edges (when there are \({\bf{n}}\) edges).

For example, let us take a graph \({\bf{G}}\) with \(4\) vertices \({\bf{a, b, c, d}}\) and an edge with weight \(1\) between every pair of vertices.

03

Obtaining the graph

Then any subgraph of \({\bf{G}}\) that is a tree, will also be a minimal spanning tree. Two possible minimal spanning trees are given in the image below (note that the total weight is \(3\) in both minimal spanning trees).

Note: The two given minimal spanning trees are not even isomorphic in this case.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Use Sollin's algorithm to produce a minimum spanning tree for the weighted graph shown in

\({\bf{a}})\)Figure \(1\).

\(b)\)Figure \(3\).

Sollin's algorithm produces a minimum spanning tree from a connected weighted simple graph \({\bf{G = (V,E)}}\) by successively adding groups of edges. Suppose that the vertices in \({\bf{V}}\) are ordered. This produces an ordering of the edges where \({\bf{\{ }}{{\bf{u}}_{\bf{0}}}{\bf{,}}{{\bf{v}}_{\bf{0}}}{\bf{\} }}\) precedes \({\bf{\{ }}{{\bf{u}}_{\bf{1}}}{\bf{,}}{{\bf{v}}_{\bf{1}}}{\bf{\} }}\) if \({{\bf{u}}_{\bf{0}}}\) precedes \({{\bf{u}}_{\bf{1}}}\) or if \({{\bf{u}}_{\bf{0}}}{\bf{ = }}{{\bf{u}}_{\bf{1}}}\) and \({{\bf{v}}_{\bf{0}}}\) precedes \({{\bf{v}}_{\bf{1}}}\). The algorithm begins by simultaneously choosing the edge of least weight incident to each vertex. The first edge in the ordering is taken in the case of ties. This produces a graph with no simple circuits, that is, a forest of trees (Exercise \({\bf{24}}\) asks for a proof of this fact). Next, simultaneously choose for each tree in the forest the shortest edge between a vertex in this tree and a vertex in a different tree. Again the first edge in the ordering is chosen in the case of ties. (This produces a graph with no simple circuits containing fewer trees than were present before this step; see Exercise \({\bf{24}}\).) Continue the process of simultaneously adding edges connecting trees until \({\bf{n - 1}}\) edges have been chosen. At this stage a minimum spanning tree has been constructed.

Show that the addition of edges at each stage of Sollin’s algorithm produces a forest.

a. Describe Kruskal's algorithm and Prim's algorithm for finding minimum spanning trees.

b. Illustrate how Kruskal's algorithm and Prim's algorithm are used to find a minimum spanning tree, using a weighted graph with at least eight vertices and \(15\) edges.

Which of these graphs are trees?

(a)

(b)

(c)

(d)

(e)

(f)

Three couples arrive at the bank of a river. Each of the wives is jealous and does not trust her husband when he is with one of the other wives (and perhaps with other people), but not with her. How can six people cross to the other side of the river using a boat that can hold no more than two people so that no husband is alone with a woman other than his wife? Use a graph theory model.

See all solutions

Recommended explanations on Math Textbooks

Pure Maths

Read Explanation

Discrete Mathematics

Read Explanation

Statistics

Read Explanation

Theoretical and Mathematical Physics

Read Explanation

Decision Maths

Read Explanation

Calculus

Read Explanation

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free