Reference no: EM131086005

ASSIGNMENT 5-

(1) Consider the complete bipartite graph K_4,4 with vertex partition (A, B) where A = {a, b, d, f}, B = {g, h, i, j}. Weights are placed on edges as follows:

c_ag = 2 c_ah = 7 c_ai = 1 c_aj = 2

c_bg = 3 c_bh = 4 c_bi = 3 c_bj = 2

c_dg = 6 c_dh = 5 c_di = 5 c_dj = 5

c_fg = 2 c_fh = 6 c_fi = 2 c_fj = 3

The following vector y is a feasible solution for the dual to the maximum weight perfect matching linear program for the given graph: y_g = y_h = 0, y_i = y_j = -1, y_a = 7, y_b = 4, y_d = 6, y_f = 6.

Use this to find a maximum weight perfect matching in the graph, and an optimal solution for the dual problem.

(2) Consider the following alternate definition of a matroid: A matroid M consists of a pair (E, B) where E is a set and B is a set of subsets of E called bases such that:

• B ≠ ∅.
• No proper subset of a set in B is in B.
• If B₁, B₂ ∈ B, then for any e ∈ B1 there exists f ∈ B₂ such that (B₁\{e}) ∪ {f} ∈ B.

(a) Show that if M = (E, I) is a matroid, and B is the set of maximal independent sets (with respect to set inclusion) in I, then (E, B) is a matroid under the alternate definition given above.

(b) Conclude the following statements:

• If V is a finite dimensional vector space, and U is a set of vectors in V , then all bases for span(U) have the same size.
• All spanning forests in a graph have the same number of edges.

(3) An independence system is a pair (E, I) where E is a set, and I is a collection of subsets of E such that

• ∅ ∈ I.
• If J' ⊆ J ∈ I, then J' ∈ I.

The sets in I are called independent sets. Suppose that (E, I) is an independence system, and that for any set of weights c ∈ R^E, the greedy algorithm finds an optimal independent set. Prove that (E, I) is a matroid.

(4) (a) Suppose M is matroid, representable over Q, given by the matrix (I|P) where I is the n × n identity matrix, and P is a n × m matrix with rational entries. Show that the dual of M is represented by the matrix (-P^T|I).

(b) Consider the matroid given by the column vectors in the matrix

considered over F₂, the finite field with two elements. Is this matroid representable over Q?

(5) A circuit in a matroid (E, I) is a subset of S ⊂ E that is minimally dependent; that is, it is minimal under set inclusion amongst subsets of E that are not independent. Show that if C₁, C₂ are circuits, C₁ ≠ C₂, and if e ∈ C₁ ∪ C₂, then there exists a circuit C such that C ⊆ (C₁ ∪ C₂)\{e}. State consequences in both graph theory and linear algebra.