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: Q8E (page 795)

In Exercises 8–10 draw all the spanning trees of the givensimple graphs.

Short Answer

Expert verified

The possible spanning trees are 3.

Step by step solution

01

Compare with the definition.

A spanning tree of a simple graph G is a subgraph of G that is a tree and that contains all vertices of G.

A tree is an undirected graph that is connected and that does not contains any single circuit. And a tree with n vertices has n-1 edges.

02

Spanning tree.

The graph with vertices 3 and an 3 edges.

The spanning tree will then contain 3 vertices and 2 edges.

Since a tree cannot contain any simple circuits and since there is a triangle. The spanning tree can be draw by removing one edge. And the three possibilities are

This is the required result.

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

Is the rooted tree in Exercise \(3\) a full \({\bf{m}}\)-ary tree for some positive integer \({\bf{m}}\)?

a) Define a rooted tree and the root of such a tree.

b) Define the parent of a vertex and a child of a vertex in a rooted tree.

c) What are an internal vertex, a leaf, and a subtree in a rooted tree\(?\)

d) Draw a rooted tree with at least \({\bf{10}}\) vertices, where the degree of each vertex does not exceed \({\bf{3}}\). Identify the root, the parent of each vertex, the children of each vertex, the internal vertices, and the leaves.

Give six examples of well-formed formulae with three or more operators in postfix notation over the set of symbols \(\left\{ {{\bf{x,y,z}}} \right\}\) and the set of operators \(\left\{ {{\bf{ + , \ast ,}} \circ } \right\}\).

Find the second least expensive communications network connecting the five computer centers in the problem posed at the beginning of the section.

What is wrong with the following “proof” using mathematical induction of the statement that every tree with \({\bf{n}}\) vertices has a path of length \({\bf{n - 1}}\). Basis step: Every tree with one vertex clearly has a path of length \(0\). Inductive step: Assume that a tree with \({\bf{n}}\) vertices has a path of length \({\bf{n - 1}}\), which has \({\bf{u}}\) as its terminal vertex. Add a vertex \({\bf{v}}\) and the edge from \({\bf{u}}\)to \({\bf{v}}\). The resulting tree has \({\bf{n + 1}}\) vertices and has a path of length \({\bf{n}}\). This completes the inductive step.

See all solutions

Recommended explanations on Math Textbooks

Logic and Functions

Read Explanation

Probability and Statistics

Read Explanation

Applied Mathematics

Read Explanation

Mechanics Maths

Read Explanation

Discrete Mathematics

Read Explanation

Statistics

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