Problems 16-3: Acyclic subgraphs a. Let G = (V, E) be an undirected graph. Using

Question

Problems 16-3: Acyclic subgraphs
a. Let G = (V, E) be an undirected graph. Using the definition of a
matroid, show that (E,l) is a matroid, where A ?l if and only if A is
an acyclic subset of E.
b. The incidence matrix for an undirected graph G = (V, E) is a |V | ×
|E| matrix M such that Mve = 1 if edge e is incident on vertex v, and
Mve = 0 otherwise. Argue that a set of columns of M is linearly
independent over the field of integers modulo 2 if and only if the
corresponding set of edges is acyclic. Then, use the result of
Exercise 16.4-2 to provide an alternate proof that (E,l) of part (a) is
matroid.
c. Suppose that a nonnegative weight w(e) is associated with each
edge in an undirected graph G = (V, E). Give an efficient algorithm to
find an acyclic subset of E of maximum total weight.
d. Let G(V, E) be an arbitrary directed graph, and let (E,l) be defined so
that A ?l if and only if A does not contain any directed cycles. Give
an example of a directed graph G such that the associated system
(E,l) is not a matroid. Specify which defining condition for a matroid
fails to hold.
e. The incidence matrix for a directed graph G = (V, E) is a |V |×|E|
matrix M such that Mve = -1 if edge e leaves vertex v, Mve = 1 if edge
e enters vertex v, and Mve = 0 otherwise. Argue that if a set of
columns of M is linearly independent, then the corresponding set of
edges does not contain a directed cycle.
f. Exercise 16.4-2 tells us that the set of linearly independent sets of
columns of any matrix M forms a matroid. Explain carefully why the
results of parts (d) and (e) are not contradictory. How can there fail to
be a perfect correspondence between the notion of a set of edges
being acyclic and the notion of the associated set of columns of the
incidence matrix being linearly independent?

Explanation / Answer

a) Let G = fg1, g2, . . . , gkg be the independent set returned by GREEDYBASIS(M,w). If any otherelement could be added to G to get a larger independent set, the greedy algorithm would have added it.Thus, G is a basis.For purposes of deriving a contradiction, suppose there is an independent set H = fh1, h2, . . . , h`gsuch thatkXi=1w(gi> (`Xj=1w(hi.(Without loss of generality, we assume that H is a basis. The exchange property now implies that k = `.Now suppose the elements of G and H are indexed in order of decreasing weight. Let i be thesmallest index such that w(gi) < w(hi), and consider the independent setsGi1 = fg1, g2, . . . , gi1g and Hi = fh1, h2, . . . , hi1, hig.By the exchange property, there is some element hj 2 Hisuch that Gi1 [ fhjg is an independent set. Wehave w(hj) w(hi) > w(gi). Thus, the greedy algorithm considers and rejects the heavier element hjbefore it considers the lighter element giBut this is impossible—the greedy algorithm accepts elements .in decreasing order of weight.

b)Let be a schedule in which every task in X is on time. Let it be the tth task in X to becompleted. On the one hand, we have (it) t from part(a), since otherwise, we could not have completed t 1other jobs in X before itOn the other hand, (i .t) D[i], because itis on time. We conclude thatD[it] t, which immediately implies that jX(t)j t.Now suppose jX(t)j t for every integer t. If we perform the tasks in X in increasing order ofdeadline, then we complete all tasks in X with deadlines t or less by day t. In particular, for any i 2 X,we perform task i on or before its deadline D[i]. Thus, X is realistic. ƒWe can dene a canonical schedule for any set X as follows: execute the tasks in X in increasingdeadline order, and then execute the remaining tasks in any order. The previous proof implies that aset X is realistic if and only if every task in X is on time in the canonical schedule for X. Thus, ourscheduling problem can be rephrased as follows:Find a realistic subset X such thatPi2XP[i] is maximized.So we’re looking for optimal subsets after all.

c)If x is in the closure of a set S, we also say that S spans x, or that x depends on S.Note that every element of S is in the closure of S, S cl(S):For the case of a matric matroid, x is in the closure of S if x in in the usual span of S, that is, if x is alinear combination of elements of S. This follows from the fact that if x is a linear combination of S, thenthe space spanned by S [ fxg is the same as the space spanned by S, and so (S) = (S [ fxg). Conversely,if (S) = (S [ fxg), then the subspace spanned by S has the same dimension as the larger space spannedby S [ fxg, and so the two subspaces are equal, implying that x is itself in the space spanned by S.For the case of a graphic matroid, an edge e is in the span of another set of edges S unless the graphwith edges S [ fxg has fewer connected components than the graph with edges S (assuming we keep all thevertices form the underlying graph around). So clearly, e is spanned by S exactly when the two endpointsof e are already connected by edges in S. Noticed that we could equivalently say that e =2 S is in the closureof S exactly when e [ S0is a circuit, for some S0 S. This principle holds in any matroid, as we will seeshortly.For the case of a uniform matroid Uk;n, of rank k on a set of size n, we see that the closure of a setS is just S, when jSj < k, and the whole matroid otherwise. This is relatively straightforward from thedenitions.The term closure" has certain connotations in mathematics, so it behooves us to prove the followingthree properties, which are generally taken to be the dening attributes of a closure operation:(S1) If S is a set, then S cl(S).(S2) If S is a set, then cl(cl(S)) = cl(S).(S3) If S T, then cl(S) cl(T).

d)The rst condition, (S1), is rather obvious since if x 2 S, then (S [ fxg) = (S). For (S2), notethat if x 2 cl(cl(S)), then(cl(S) [ fxg) = (cl(S)) = (S);by the lemma, implying(S) (S [ fxg) (cl(S) [ fxg) = (S);so that x 2 cl(S).For (S3), suppose that x 2 cl(S). Then (S [ fxg) = (S), so that(T [ fxg) = (T [ (S [ fxg)) (T) + (S [ fxg) (T (S [ fxg)) (T) + (S [ fxg) (S) = (T);so that x 2 cl(T).Properties (S1-3) establish that closure is in fact a proper closure operator. We can dene a set to beclosed if it equals its closure, or equivalently by (S2), if it is the closure of some set. The intersection oftwo closed sets is closed, and the closure of any set is just the intersection of the closed sets containing it.If the union of any two closed sets was closed, we would have a topological space. This would actually beequivalent to the identitycl(S [ T) = cl(S) [ cl(T);for any S and T. However, this is rarely the case for matroids5Instead, we have an odd property, the .MacLane-Steinitz exchange property:(S4) If x =2 cl(S), but x 2 cl(S [ fyg), then y 2 cl(S [ fxg).To prove this, it helps to rst prove the following alternative characterization of closure, which is some-times taken to be the denition of closure:

e)First, suppose that (a) is true. Then obviously x 2 cl(S), by (S1) above. Next, suppose that (b) istrue. Then for some T S, fxg [ T is a circuit, which implies that T is independent. So we have n(T) = 0and n(T [ x) = 1. Then by inequality (N3),n(S [ fxg) = n(S [ T [ fxg) n(S) + n(T [ fxg) n(T) = n(S) + 1:so therefore(S) (S [ fxg) = jS [ fxgj n(S [ fxg) jSj + 1 (n(S) + 1) = jSj n(S) = (S):So x 2 cl(S).Finally, it remains to show that if x 2 cl(S), and x =2 S, then (b) holds for some T. Let I be a maximalindependent subset of S. Then jIj = (S) = (S[fxg), so I is also a maximal independent subset of S[fxg.Therefore I [ fxg is not independent, and contains some circuit C. If x =2 C, then C I, contradicting thechoice of I. Therefore x 2 C, and we are done.With this result, (S4) is easy to prove.

f)For (R1), note that by the semimodular inequality,M(E) M(S) + M(E n S);so thatMD(S) = M(E n S) + jSj M(E) jSj m(S) 0;and since M(E n S) M(E), we haveMD(S) = M(E n S) + jSj M(E) jSj:So (R1) holds in MD.Next, for (R2), suppose that S T E. Then E n S = (E n T) [ (T n S), so again applying thesemimodular inequality,M(E n S) M(E n T) + M(T n S) M(E n T) + jTj jSj;so thatMD(S) = M(E n S) + jSj M(E) M(E n T) + jTj M(E) = MD(T);establishing (R2).

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.