2.10 Trees

Graph Algorithm


The algorithm STAR MARK starts with a simple undirected graph, \(G\), with a finite set of vertices, \(V\), and a set of one or more edges, \(E\). Initially, all edges are unmarked. Then, STAR MARK proceeds to mark some of the edges, by repeatedly performing the following steps until no further step is possible:

  1. Choose any unmarked edge \(e \in E\) such that there is currently no path of marked edges between the endpoints of \(e\).
  2. Mark edge \(e\).
Preserved Invariants

Which of the following predicates are preserved invariants as well as hold for the start state?

  1. Predicate 1 is true for the start state, since by definition there is at least one edge, but it is not preserved.
  2. Predicate 2 is a preserved invariant and vacuously holds for the start state, which has no marked edges.
  3. Predicate 3 is vacuously true for the start state, but it is not preserved.
  4. Predicate 4 is true for the start state but is not preserved.
Derived Variables

Choose the property that best describes each of the following derived variables.

Answer with the strongest applicable property. For example, for a variable that is constant, the answer should be "constant", even though it is also both weakly increasing and weakly decreasing.

  1. # of unmarked edges
    In every iteration, the number of unmarked edges decreases by 1.
  2. # of marked edges
    In every iteration, the number of marked edges increases by 1.
  3. (# of unmarked edges) + (# of marked edges)
    In every iteration, the number of marked edges increases by 1 and the number of unmarked edges decreases by 1. So, their sum remains constant and is always equal to the initial number of unmarked edges in the graph.
  4. (# of marked edges) - (# of unmarked edges)
    In every iteration, the number of marked edges increases by 1 and the number of unmarked edges decreases by 1. So, their difference increases by 2.
  5. (# of connected components) in \(G'\) with vertices in \(V\) and edges in \(M\), where \(M\) is the set of marked edges
    Each newly marked edge connects 2 vertices that previously had no path of marked edges between them, so these 2 vertices belonged to different connected components of \(G'\), and the newly marked edge "joins" these components into one. As a result, the number of components in \(G'\) decreases by 1.