A Graphical Representation of Matroids
A Graphical Representation of Matroids
复制标题
拟阵的图形表示
DOI：
10.1137/0125060
复制
发表时间：
1973
影响因子：
1.9
通讯作者：
M. Tobey
中科院分区：
文献类型：
--
作者：
C. Holzmann;P. G. Norton;M. Tobey
拟阵的基图是其点为拟阵的基的图。如果两个碱基恰好相差一个元素，则它们是相邻的。给出了拟阵等价的定义，并证明了两个拟阵等价当且仅当它们的基图同构。特别是，如果 M 和 $M_1 $ 是具有同构基图的不可分拟阵，则 M 与 $M_1 $ 或其对偶同构。因此，对拟阵的研究被简化为对一类图的研究：基础图。对基础图中的邻域结构进行了详细研究，并用于建立上述结果。结果中包括可分离拟阵的图形分类，它给出了惠特尼分解定理的新证明。
A base graph of a matroid is the graph whose points are the bases of the matroid. Two bases are adjacent if they differ by exactly one element. A definition of equivalence of matroids is given and it is shown that two matroids are equivalent if and only if their base graphs are isomorphic. In particular, if M and $M_1 $ are nonseparable matroids with isomorphic base graphs, then M is isomorphic to either $M_1 $ or its dual. Thus, the study of matroids is reduced to the study of a class of graphs: the base graphs. A detailed investigation of the structure of neighborhoods in the base graph is carried out and this is used to establish the above result. Included in the result is a graphical classification of eparable matroids which gives a new proof of Whitney’s decomposition theorem.