how to prove this is a matroid in greedy solving?

168 Views Asked by At

Suppose we have a finite set called P and we have partitioned it into separate subsets

p1, p2, ... pj

we define q as all subsets S which at most have one member of each pi. so

q = { s:|intersect(s,pi)| <= 1, for i = 1...j }

prove that (P,q) is a matroid when its independent sets are q.

1

There are 1 best solutions below

0
On

1.P is finite as stated in qusetion 2.q has inheritance because when we choose B all of its subset still has at most one member of pi 3.q has substitution property as when we have |A| < |B| then B has some memebers of Pi that are not in A so we can add them to A and still it has at most one member of Pi