[科普中國(guó)]-圈擬陣

圈擬陣(circuit matroid)亦稱多邊形擬陣，是一類特殊的擬陣，它是建立在圖G=(V,E)上的一類擬陣M(G)。設(shè)G是一個(gè)圖，E=E(G)是G的邊集。定義I?2E為這樣的一個(gè)集合： X∈I當(dāng)且僅當(dāng)X(作為G的子圖)不含有極小圈，那么(E，I)是一個(gè)擬陣，這個(gè)擬陣通常稱為G的圈擬陣(cycle matroid)，記作M(G)。此結(jié)論可由以下例子得出：設(shè)G是一個(gè)圖，其邊集為E=E(G)，當(dāng)X?E是G的一個(gè)無(wú)圈子圖(即不含有極小圈的子圖)，則X的任意子集Y也是G的一個(gè)無(wú)圈子圖。當(dāng)X1，X2?E是G中的兩個(gè)無(wú)圈子圖并且|X1|