Example 2. linear algebra Example 3. Graph Let s=a a)be a set of n vectors, and I =A is subsets of S: As s=all edges in an undirected graph G) elements are linearly independent y ·={Acs: A defines a sub-graph G=ⅣV,A Proof M=(S, I ]is a Matroid too such that Ga is acyclic, that is Ga is a forest] This proof is somewhat harder than the one for the last example.如何利用线性代 ·定理:M={s,1} is a matroid! 数的知识来证明? 清华大学們学院宋恒 清华大学软件学院宋 证明 Pigeon hole principle: There exists one tree T in G such that it intersects more than one 1. Hereditary: is easy to prove,证明什 whose vertices u and v belongs two trees in 2. Exchange property: needs some tricks! GA【保证下一步加入(uv)后无环】 1.设A和B是1的元素,且|A<B, then Ga and AUI(u, v)) is another subset of s, and it defines a subgraph such that it is acyclic GB are two forests of Graph G 2. Ga has less tree than in G 3. How many trees are there in GA? 清华大学学院未恒 清华大学软件学院宋 Properties of Matriod Illustration of the same size of maximum independent subset Theorem 16.6: All maximal independent subsets in a matroid have the same size The prove is trivial a graphic matroid for a connected, undirected graph G. Every independent subset of m. must be a free tree with exactly VF1 edges that connect all the vertices of g. such a tree is called a spanning tree How to do in linear algebra? 清华大学轼字院宋恒 消华大学软件学院宋6 清华大学软件学院宋斌恒 31 Example 2. Linear algebra •Let S={a1 , a2 , a3 , … , an } be a set of n vectors, and l ={A is subsets of S: A’s elements are linearly independent }. Proof M={S, l } is a Matroid too! •This proof is somewhat harder than the one for the last example. 如何利用线性代 数的知识来证明？ 清华大学软件学院宋斌恒 32 Example 3. Graph •S = {all edges in an undirected graph G} • l = {AÍS: A defines a sub-graph GA={V, A} such that GA is acyclic, that is GA is a forest} •M＝{S, l } •定理：M={S, l } is a Matroid! 清华大学软件学院宋斌恒 33 证明 1. Hereditary： is easy to prove，证明什 么？ 2. Exchange property： needs some tricks! 1. 设A和B是l 的元素，且 |A|<|B|, then GA and GB are two forests of Graph G, 2. GB has less tree than in GA . 3. ? How many trees are there in GA? 清华大学软件学院宋斌恒 34 – Pigeon hole principle: There exists one tree T in GB such that it intersects more than one tree in GA .【 GB中树少】 – In tree T, there exists at least an edges e whose vertices u and v belongs two trees in GA【保证下一步加入(u,v)后无环 】 – A U {(u,v)} is another subset of S, and it defines a subgraph such that it is acyclic. 清华大学软件学院宋斌恒 35 Properties of Matriod •Theorem 16.6: All maximal independent subsets in a matroid have the same size. •The prove is trivial. 清华大学软件学院宋斌恒 36 Illustration of the same size of maximum independent subset Properties •A graphic matroid for a connected, undirected graph G. Every independent subset of MG must be a free tree with exactly |V|-1 edges that connect all the vertices of G. Such a tree is called a spanning tree of G. •How to do in linear algebra?