Accession Number : AD0682354

Title :   MINIMUM PARTITIONS AND THE SHANNON SWITCHING GAME.

Descriptive Note : Interim rept. Jul 66-Jul 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