Minimum Partitions and the Shannon Switching Game

摘要

The report treats the problem of obtaining a minimum partition of the column vectors of a matrix into linearly independent subsets. An interesting interpretation of this problem in terms of linear graphs is then considered. This is accomplished by first presenting an exposition of Edmonds' algorithm for obtaining a minimum partition of a matroid into independent subsets, and then applying this result to the special cases of linear graphs and matrices. It is shown that a minimum partition problem relative to the incidence matrix of a graph G is equivalent to partitioning the edges of G into a minimum number of subsets, such that the edges in each subset form a forest in G. An application of the minimum partition algorithm is then made to determine optimal strategies and an algorithm for the Shannon Switching Game. (Author)