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

Use backtracking to try to find a coloring of each of the graphs in Exercises 7–9 of Section 10.8 using three colors.

Short Answer

Expert verified

By using the backtracking process get the coloring of the exercise 7-9 by using the three colors.

Step by step solution

Achieve better grades quicker with Premium

  • Unlimited AI interaction
  • Study offline
  • Say goodbye to ads
  • Export flashcards

Over 22 million students worldwide already upgrade their learning with Vaia!

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

02

Result for exercise 7.

Use the order is a, b, c, d.

Let us start with vertex a. The vertex does not have a color assigned to it yet thus color is blue.

Now move to the next vertex b, which is connected to a and thus cannot be colored blue.

Apply the same procedure for vertex c and d respectively thus cannot be colored blue.

Now at the vertex d. The vertex does not have a color assigned to it; thus, color is green.

When backtracking to the last vertex without a color, which is b. b is connected to d and thus cannot be colored green.

Now, at vertex b. The vertex does not have a color assigned to it yet, thus we color it red.

03

Solution for exercise 8.

Use the order is a, e, f, b, d, c. If we use the wrong order, then we are not able to color the graph with only three colors.

Let us start with vertex a. The vertex does not have a color assigned to it yet thus color is blue.

Now move to the next vertex e, which is connected to a and thus cannot be colored blue.

Apply the same procedure for vertex f,b,d,c respectively thus cannot be colored blue.

Now at the vertex c. The vertex does not have a color assigned to it; thus, color is green.

When backtracking to the last vertex without a color, which is d. d is not connected to a green vertex thus is colored green.

Thus, the last vertex without a color which is e. e is connected to c and thus cannot be colored green.

Now, at vertex e. The vertex does not have a color assigned it yet, thus we color it red.

Thus, the last vertex without a color which is d. d is not connected to the red vertex and thus be colored red.

04

 Result for exercise 9.

Use the order is a, b, c, d, e. If use the wrong order, then it is not able to color the graph.

Let us start with vertex a. The vertex does not have a color assigned to it yet thus color is blue.

Now move to the next vertex b, which is connected to e and thus cannot be colored blue.

Apply the same procedure for vertex c,d,e respectively thus cannot be colored blue.

Now at the vertex e. The vertex does not have a color assigned to it. Thus, color is green.

When backtracking to the last vertex without a color, which is d. d is not connected to a green vertex thus is colored green.

Thus, the last vertex without a color which is b. b is connected to c.

Therefore, by using the backtracking process get the coloring of the exercise 7-9 by using the three colors.

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

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.

Which connected simple graphs have exactly one spanning tree?

Give an upper bound and a lower bound for the height of a B-tree of degree k with n leaves.

Suppose that we vary the payoff to the winning player in the game of nim so that the payoff is n dollars when n is the number of legal moves made before a terminal position is reached. Find the payoff to the first player if the initial position consists of

a) two piles with one and three stones, respectively.

b) two piles with two and four stones, respectively.

c) three piles with one, two, and three stones, respectively.

Show that there is a unique minimum spanning tree in a connected weighted graph if the weights of the edges are all different.

See all solutions

Recommended explanations on Math Textbooks

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