離散システムの不変な階層構造を求めて : グラフからマトロイドへ

概要

論文の詳細を見る
Hierarchical decompositions of discrete physical/engineering systems are considered by means of graph and matroid theory. First, a graph-theoretic method, called the Dulmage-Mendelsohn (DM-) decomposition, is described. Though the DM-decomposition is unique from the graph-theoretic viewpoint, the resulting hierarchy cannot be regarded as a physically inherent structure since it varies with mathematical descriptions employed. This critical observation leads to a new method based on matroid theory for systems analysis. A class of matrices, layered mixed(LM-)matrices, is introduced as a mathematical tool for describing the combinatorial structure of discrete systems. An LM-matrix has a canonical block-triangular decomposition, called the combinatorial canonical form(CCF) , which reveals the "invariant" hierarchy. The CCF is an extension of the DM-decomposition and can be computed by a fast algorithm.
一般社団法人日本応用数理学会の論文
1991-09-13