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

In Exercises 2–6 find a spanning tree for the graph shown by removing edges in simple circuits.

Short Answer

Expert verified

For the result follow the steps.

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 contain any single circuit. And a tree with n vertices has n-1 edges.

Here graph contains 5 vertices and 6 edges.

The spanning tree contains 5 vertices and 4 edges. Thus2 edges will be removed from the graph

02

Remove the extra edges.

Since a tree cannot contain any single circuit and there are two tangents present in the graph (abd, bce).then suffices to remove one edge from either triangle.

The tree will be as

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

Show that a directed graph \({\bf{G = }}\left( {{\bf{V,E}}} \right)\) has an arborescence rooted at the vertex r if and only if for every vertex \({\bf{v}} \in {\bf{V}}\), there is a directed path from r to v.

Draw a game tree for him if the starting position consists of three piles with one, two, and three stones, respectively. When drawing the tree represent by the same vertex symmetric positions that result from the same move. Find the value of each vertex of the game tree. Who wins the game if both players follow an optimal strategy?

How many edges must be removed from a connected graph with n vertices and m edges to produce a spanning tree?

Show that a tree with n vertices that has \({\bf{n - 1}}\) pendant vertices must be isomorphic to \({{\bf{K}}_{{\bf{1,n - 1}}}}\).

In this exercise we will develop an algorithm to find the strong components of a directed graph \({\bf{G = }}\left( {{\bf{V,E}}} \right)\). Recall that a vertex \({\bf{w}} \in {\bf{V}}\) is reachable from a vertex \({\bf{v}} \in {\bf{V}}\) if there is a directed path from v to w.

Explain how to use breadth-first search in the directed graph G to find all the vertices reachable from a vertex \({\bf{v}} \in {\bf{G}}\).
Explain how to use breadth-first search in \({{\bf{G}}^{{\bf{conv}}}}\) to find all the vertices from which a vertex \({\bf{v}} \in {\bf{G}}\) is reachable. (Recall that \({{\bf{G}}^{{\bf{conv}}}}\) is the directed graph obtained from G by reversing the direction of all its edges.)
Explain how to use part (a) and (b) to construct an algorithm that finds the strong components of a directed graph G, and explain why your algorithm is correct.

See all solutions

Recommended explanations on Math Textbooks

Pure Maths

Read Explanation

Discrete Mathematics

Read Explanation

Probability and Statistics

Read Explanation

Geometry

Read Explanation

Mechanics Maths

Read Explanation

Applied Mathematics

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