Given that you can answer the two problems in a variety of ways, what would be the "optimal" solutions/proofs for these two problems?

 

 

Matroids
A matroid is an ordered pair (S, I), in which S is a finite and nonempty set, while I is a nonempty
collection of subsets of S, called the i​ ndependent
​
subsets of S, so that the following two
properties hold:
1: if A belongs to I and B ⊆A, then B belongs to I (hereditary property);
2: if A and B belong to I and |A| > |B|, then there is an x in A \ B such that B ∪ {x} belongs to I
(exchange property).
This is a good example of a matroid, which is called a ​graphic
​ matroid. Fix an arbitrary
undirected graph G = (V,E). Define I as the set of all acyclic subsets of E, so, the set of
all subsets A of E such that the graph (V,A) is acyclic. (E, I) is a matroid.
An independent set A of a matroid
​ is​ maximal if it’s not properly contained within any other
independent set. In the case of a graphic matroid, the maximal independent sets correspond
to the spanning forests of the graph G. (If G is connected, then the maximal independent
sets correspond to the spanning trees of G.) It is not difficult to prove that every spanning
forest of a given undirected graph has the same number of edges. (More precisely, if a graph
G = (V,E) has k connected components, then every spanning forest of G has |V| - k edges.)
This fact can be seen as a special case of the following result concerning arbitrary matroids,
which is an easy consequence of the exchange property: All maximal independent subsets of
a given matroid have the same cardinality. ​ ​ The Matroid Greedy Algorithm
A ​weighted matroid is a matroid (S, I) where each element of S has an associated weight.
A fundamental matroid optimization problem is the following: Given a weighted matroid,
determine a minimum-weight maximal independent set. (The weight of an independent set
is dened as the sum of the weights of the elements of the set.)
In the special case of a graphic matroid, the problem of determining a minimum-weight
maximal independent set corresponds to the minimum spanning forest problem. Recall
that Kruskal's algorithm can be used to solve the minimum spanning forest problem. Can
Kruskal's algorithm be generalized to solve the minimum-weight maximal independent set
problem for arbitrary matroids? Yes, Kruskal's algorithm is a special case of the​ matroid
greedy algorithm, which does just that. The matroid greedy algorithm works as follows.
First, we sort the elements of S in nondecreasing order of weight, breaking ties arbitrarily, and
we initialize A to the empty set, which is guaranteed to be independent. (That the empty set is
independent follows from the hereditary property, and the requirement that there is at least one
independent set.) Then, we consider each x in S in turn, in the order established by the sort.
When we consider x, we add it to A if and only if A∪ {x} is independent. After considering all of
the elements of S, we claim that the set A is a minimum-weight maximal independent set. The
proof of this claim is similar to the proof of correctness of Kruskal's algorithm. The same framework can be used to determine a maximum-weight maximal
independent set. The only difference is that we sort the elements of S in nonincreasing order,
rather than in nondecreasing order.
Recall that one of the consequences of our analysis of Kruskal's algorithm was that
every MST has the same distribution of edge weights. This result generalizes to arbitrary
weighted matroids: Given a weighted matroid M, if A and B are two maximum-weight (resp.,
minimum-weight) maximal independent sets of M, then for any weight z, the number of elements
in A with weight z is equal to the number of elements in B with weight z. A Matroid Based on an Edge-Weighted Bipartite Graph
Let G = (U, V,E) be an undirected bipartite graph, where U denotes the set of “left" vertices,
V denotes the set of “right" vertices, and each edge e in E has one endpoint in U and one
endpoint in V . Further assume that each edge e in E has an associated nonnegative weight
weight(e). A matching of G is a subset M of E such that each vertex in U∪V is incident on
at most one edge of M. Given a matching M of G, each vertex of G that is incident on some
edge of M is said to be matched by M; the remaining vertices are unmatched. The weight of
a matching M of G, denoted weight(M), is defined as ∑​e∊M​ weight(e). A maximum-weight
matching (MWM) of G is a matching M of G such that weight(M) ≥ weight(M’) for all
matchings M’ of G.
Problem 1​:
Let G = (U, V,E) be a bipartite graph with nonnegative edge weights. Let us say that a subset A
of U is independent if some MWM of G matches every vertex in A. Let Ä„ denote the set of all
independent subsets of U. ​Prove that (U,Ą ) is a matroid.
While the definition of the matroid (U,Ä„ ) of the above problem is based on a bipartite graph
where the edges have weights, the elements of U do not have weights, so this is not a weighted
matroid. Now assume that each vertex u in U has an associated real priority, denoted priority(u).
Furthermore, for any subset U’ of U, let us dene the priority of U’, denoted priority(U’), as
∑​u∈U’​priority(u). The matroid greedy algorithm (with the priorities playing the role of the weights)
can be used to determine a maximum-priority maximal independent set of matroid (U,Ä„ ). In
fact, just as Kruskal's algorithm can generate (by appropriate tie-breaking) any MST of a given
connected, edge- weighted graph, the matroid greedy algorithm can generate (by appropriate
tie-breaking with respect to the priorities of the left vertices) any maximum-priority maximal
independent set of matroid (U,Ä„ ). Given a bipartite graph G = (U, V, E) with nonnegative edge
weights, and where each vertex u in U has an associated priority, we say that an MWM M of G
is greedy if the set of left vertices matched by M is a maximum-priority maximal independent
set of matroid (U,Ä„).
We remark that it is easy to give an equivalent characterization of the set of greedy MWMs that
does not rely on matroid terminology. First, we can argue that the set of left vertices matched by
an MWM M of G is a maximal independent set of the matroid (U;A) if and only if M is a maximum-cardinality MWM (MCMWM) of G. Next, for any MWM M of G, dene priority(M) as the
sum of the priorities of the left vertices matched by M. Using this definition, we find that an MWM
of G is greedy if and only if it is a maximum-priority MCMWM of G.
Problem 2:
Let G = (U, V, E) be a bipartite graph with nonnegative edge weights and where each left vertex
has a real priority. Let U​0​ and U​1​ be subsets of U such that U​0​ ⊆ U​1​, let u be a vertex in U​0​, and
for i in {0, 1}, let G​i​ denote the subgraph of G induced by U​i​ ⋃ V .​ Prove that if u is not matched
in any greedy MWM of G​0​, then u is not matched in any greedy MWM of G​1​.

• 1493366345-Matroids.pdf

ComputerScienceExpert

(11)

Status NEW Posted 28 Apr 2017 07:04 AM My Price 11.00

-----------

Attachments

file 1493366350-Solutions file 2.docx preview (51 words )

H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------. ----------- Th-----------ank----------- yo-----------u -----------

Not Rated(0)

• Buy Answer