
Accession Number : AD0682354
Title : MINIMUM PARTITIONS AND THE SHANNON SWITCHING GAME.
Descriptive Note : Interim rept. Jul 66Jul 67,
Corporate Author : MICHIGAN UNIV ANN ARBOR SYSTEMS ENGINEERING LAB
Personal Author(s) : White,Lee J.
Report Date : JAN 1969
Pagination or Media Count : 114
Abstract : 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)
Descriptors : (*GAME THEORY, COMBINATORIAL ANALYSIS), (*COMBINATORIAL ANALYSIS, GRAPHICS), MATHEMATICAL MODELS, FLOW CHARTING, SET THEORY, MATRICES(MATHEMATICS), ALGORITHMS, THEOREMS
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE