a. Let G = (V, E) be an undirected graph. Using the definition of a matroid, sho
ID: 3622808 • Letter: A
Question
a. Let G = (V, E) be an undirected graph. Using the definition of amatroid, show that (E,l) is a matroid, where A ?l if and only if A is
an acyclic subset of E.
Explanation / Answer
Dear, a. G=(V,E) be an undirected graph Show that (E,l) is a matroid, where A belongs to l if and only if A is an acyclic subset of E. Proof: E is a finite set, l is a hereditary, since a subset of forest is a forest. We can say another way that removing edges from an acyclic set of edges cannot create cycles. We need to show that (E,l) is a Matroid MG. Take two forests GA=(V,A) and GB=(V,B) are forests of G and that |B| >|A| i.e., A and B are acyclic set of edges and B contains more edges than A does. It follows from theorem B.2 that a forest having k edges contains exactly |V|-k trees. Thus forest GA contains |V| - |A| trees, and forest GB contains |V| - |B| trees. Since forest GB has fewer trees than forest GA does, forest GB must contain some tree T whose vertices are in two different trees in forest GA. Moreover since T is connected, it must contain an edge (u,v) such that vertices u and v are in different trees in forest GA. Since the edge (u,v) connects vertices in two different trees in forest GA, the edge (u,v) can be added to forest GA without creating a cycle. Therefore M satisfies the exchange property, completely the proof that MG is matroid. Given matroid M=(E,l) we call an element x does not belong to A an extension of A belong to l if x can be added to A while preserving independence i.e., x is an extension of A if A U {x} belong to l. As example consider graphic matroid MG. If A is an independent set of edges then edge e is an extension of A if and only if e is not in A and the addition of e to A doesnot create a cycle. If A is an independent subset in a matroid M, we can say that A is maximal if it has no extensions i.e, A is maimal if it is not contained in any larger independent subset of M.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.