Find a maximum weight perfect matching in the graph

Assignment Help Mathematics
Reference no: EM131086005

ASSIGNMENT 5-

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

cag = 2 cah = 7 cai = 1 caj = 2

cbg = 3 cbh = 4 cbi = 3 cbj = 2

cdg = 6 cdh = 5 cdi = 5 cdj = 5

cfg = 2 cfh = 6 cfi = 2 cfj = 3

The following vector y is a feasible solution for the dual to the maximum weight perfect matching linear program for the given graph: yg = yh = 0, yi = yj = -1, ya = 7, yb = 4, yd = 6, yf = 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 B1, B2 ∈ B, then for any e ∈ B1 there exists f ∈ B2 such that (B1\{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 ∈ RE, 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 (-PT|I).

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

1635_Figure.png

considered over F2, 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 C1, C2 are circuits, C1 ≠ C2, and if e ∈ C1 ∪ C2, then there exists a circuit C such that C ⊆ (C1 ∪ C2)\{e}. State consequences in both graph theory and linear algebra.

Reference no: EM131086005

Questions Cloud

Application-incorporating security into it processes : Security in an organization does not reside in a silo; it is affected by other processes and vice versa. Therefore, security should be integrated into the overall IT process to make it effective.
Determine the amount of entropy produced, in kj/kg k : The temperature rise is brought about adiabatically by stirring the air with a paddle wheel. Determine the amount of entropy produced, in kJ/kg ? K.
Recommend for naming files in business : What kinds of rules would your recommend for naming files in business? For personal use?
How does mcommerce facilitate the purchase : Determine whether these values encourage or discourage use or ownership and why. Is mCommerce an advantage or disadvantage to the purchase?
Find a maximum weight perfect matching in the graph : ASSIGNMENT 5. Consider the complete bipartite graph K4,4 with vertex partition (A, B) where A = {a, b, d, f}, B = {g, h, i, j}. Use this to find a maximum weight perfect matching in the graph, and an optimal solution for the dual problem
What general conclusions can you draw : What general conclusions can you draw?
Interpret the findings derived from each analysis : What are the differences/relationships between the customers who respond the credit card offers in favor of Visa or Mastercard ( question 14) and those who prefer to choose other cards in responding the offer in terms of the belief of "During the..
Determine the mass flow rate of the steam : Determine the mass flow rate of the steam
Differences between local and global marketing : In what facets of marketing strategy and marketing programs do you see the greatest differences between how products are or should be marketed Locally and Globally? Why are these differences important?

Reviews

Write a Review

 

Mathematics Questions & Answers

  Write the matrix of eigenvectors and state its rank

Find the eigenvectors and eigenvalues of the following matrix. Write the matrix of eigenvectors and state its rank. If possible, invert it and show that P-1AP = Λ

  Find the magnitude of the force in newtons

A wrench 0.6 meters long lies along the positive -axis, and grips a bolt at the origin. A force is applied in the direction of at the end of the wrench. Find the magnitude of the force in newtons needed to supply 100 newton-meters of torque to the..

  What is the price range of houses they should consider

If local mortgage rates are 9.5%/year compounded monthly for a conventional 30-yr mortgage, what is the price range of houses they should consider? (Round your answers to the nearest cent.)

  Determine the open intervals

Determine the open intervals on which the graph is concave upward or concave downward. f(x)=x^2/x^2+9

  Buoyancy and terminal velocity

Archimedes principal of buoancy states that an object submerged in a fluid is buoyed up by a force equal to the weight of the fluid the object displaces.

  Find the maximum possible area of a trapezoid

find the maximum possible area of a trapezoid inscribed in a semicircle of radius 1.

  What are the dimensions of the garden

Fencing for the side parallel to the building costs $20 per foot, and material for the other two sides costs $80 per foot. If $1,500 is to be spent on fencing, what are the dimensions of the garden with the largest possible area?

  How much money will it have in the account at end of august

Suppose this ice cream store deposits its receipts in an account paying 5% interest per year compounded continuously. How much money will it have in the account at the end of August?

  Find probability of m ms in a jar

Find Probability Of M Ms In A Jar. A jar contains 15 M&Ms: 4 red, 5 green, and 6 yellow. Two candies are picked from the jar (no replacement).

  Should ho be rejected

Calculate the 95% confidence interval for the population mean, based on the sample mean.

  How many of each is needed to complete the project

Fred is building a fence that is 6 feet tall and 96 feet long. He needs to make a list of supplies needed. Based on the specifications below, please write down how many of each is needed to complete the project.

  Equilibrium under gravity by two inextensible

A body of mass 5 kg is held in equilibrium under gravity by two inextensible light ropes. One rope is horizontal and the other is inclined at an angle ? to the horizontal, as shown in the diagram below.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd