Mathematics for Computer Science

Chapter 11 Simple Graphs358

000

001

010

011

100

101

110

111

Figure 11.27 H 3.

Problem 11.35.

Procedurecreate-spanning-tree

Given a simple graphG, keep applying the following operations to the

graph until no operation applies:

1. If an edgehu—viofGis on a cycle, then deletehu—vi.


2. If verticesuandvofGare not connected, then add the edge
   hu—vi.

Assume the vertices ofGare the integers1;2;:::;nfor somen 2. Proce-
durecreate-spanning-treecan be modeled as a state machine whose states are all
possible simple graphs with vertices1;2;:::;n. The start state isG, and the final
states are the graphs on which no operation is possible.

(a)LetGbe the graph with verticesf1;2;3;4gand edges

fh 1 — 2 i;h 3 — 4 ig

What are the possible final states reachable from start stateG? Draw them.