Matroid(拟阵) 线性代数中的线性无关概念回顾 Theoretical Foundation for Greedy 组向量:a=10,0},b=1,1,0},c=0,20} orithms d={1,1,1},e={0.0.0}.f={0,1,0} application ·所有线性无关向量组构成的集合 l={{a}.{b},@每o}.t{ab}.{ac},{ad a.吾.鲁.…… 的特征:如果{ab}属于l则{a,{b}都属于 清华大学們学院宋恒 清华大学软件学院宋 Matroids 拟阵定义(续) Definition: A matroid is an ordered pair 1. I is a nonempty family of subsets of s, called the independent subsets of s, such that if B∈ I and AcB, then a∈l.Wesa atisfying the following 3 conditions: that I is hereditary if it satisfies this property. Note that empty set is necessarily a member 1. S is a finite nonempty set 2. If A in l. B in s, then there is some element A such that AU x∈l We say that M es the exchange 清华大学学院未恒 清华大学软件学院宋 Concepts detail Example 1. Linear algebra 1. I is a set whose elements are subset of Let S=(a, a2, a3,...,a be a set of n and I =all subsets of s). 2. Every element in I is a set whose elements are independent 1. Proof M=S, I) is a Matroid! 1. The element inI is independent subset of s 3. A subset of independent elements must 1. LetA E I and b is a subset of A, It is trivial that B is in 4. If one independent set is small than another, then it can be expands to the same size with elements in the other set 清华大学轼字院宋恒 消华大学软件学院宋5 清华大学软件学院宋斌恒 25 Matroid（拟阵） •Theoretical Foundation for Greedy Algorithms. •Its application 清华大学软件学院宋斌恒 26 线性代数中的线性无关概念回顾 •一组向量： a={1,0,0}, b={1,1,0}, c={0,2,0}, d={1,1,1}, e={0,0,0}, f={0,1,0} •所有线性无关向量组 构成的集合 • l ={f,{a}, {b}, {c}, {d}, {f}, {a,b}, {a,c}, {a,d}, {a,f}, {}, {},… … } • l 的特征：如果{a,b}属于l 则{a}, {b}都属于l 清华大学软件学院宋斌恒 27 Matroids • Definition: A matroid is an ordered pair M = (S, l ) satisfying the following 3 conditions： 1. S is a finite nonempty set 清华大学软件学院宋斌恒 28 拟阵定义（续） 1. l is a nonempty family of subsets of S, called the independent subsets of S, such that if B Î l and A Í B, then A Î l . We say that l is hereditary if it satisfies this property. Note that empty set is necessarily a member of l . 2. If A in l , B in l , and |A|<|B|, then there is some element x Î B-A such that A U {x} Î l . We say that M satisfies the exchange property 清华大学软件学院宋斌恒 29 Concepts detail 1. l is a set whose elements are subset of S 2. Every element in l is a set whose elements are independent. 3. A subset of independent elements must be independent too. 4. If one independent set is small than another, then it can be expands to the same size with elements in the other set 清华大学软件学院宋斌恒 30 Example 1. Linear algebra • Let S={a1 , a2 , a3 , … , an } be a set of n independent vectors, and l ={all subsets of S}. 1. Proof M={S, l } is a Matroid! 1. The element in l is independent subset of S. 1. Let A Î l and B is a subset of A, It is trivial that B is in l . 2. If |A|<|B|, then there exists an element b in B-A such that A U {b} is an element of l. 1. Its trivial too!