上頁　1│2│3│4　次頁

相異代表系古今談 （第 2 頁）

張鎮華

 

首頁 | 搜尋

．原載於數學傳播第十卷第一期
•對外搜尋關鍵字
 
2.第二把鑰匙：擬陣理論

擬陣理論最早溯源1930年，代數學家范德瓦登 (Van der Waedern) 在他的代數書上， 將線性獨立和代數獨立的概念公設化， 但真正將這件事情做得很徹底則是1935年惠特尼 (Whitney) 的一篇論文， 他將圖網上的「沒有迴路」和代數中「獨立」的概念， 共同熔於一爐，鍛就出擬陣這把金鑰。

這之後，伯考夫、馬克藍 (Mac Lane)、迪兒臥斯 (Dilwurth) 等人由束理論 (lattice theory) 及幾何觀點做了一些研究，雷多在組合學的應用上即無窮擬陣也有重要的成果。但真正將擬陣炒紅的應該是榻德 (Tutte) 在擬陣和網圖的研究，以及雷多在研究相異代表系時引進擬陣。自此之後，圖網論、擬陣和相異代表系的研究相結合，造成1960年代的淘金盛潮，納斯威廉 (Nash-Williams)、艾德模斯 (J. Edmonds)、佛兒克森 (Fulkerson)、布勞弟 (Brualdi)、彌兒斯基 (Mirsky)、婆費特 (Perfect) 等人， 諸家紛起，創下輝煌的霸業。

所謂擬陣是一有序對 $M=(S,\vartheta)$，其中 S 是有限集合，$\vartheta$ 是 S 的一個子集族，並且滿足下面三個公設。

(I1) $\phi\in \vartheta$。
(I2) 若 $X\subseteq Y\in \vartheta$,則 $X\in \vartheta$。
(I3) 若 $X,Y\in \vartheta$且|X|>|Y|, 則存在 $x\in X\setminus Y$ 使得 $Y\bigcup \{x\}\in \vartheta$。

$\vartheta$的元素(是S的一個部分集合)稱為獨立集,仿照線性代數或圖網理論, 我們也可以定義出相依、基底、序、生成集、迴路$\cdots\cdots$等等概念。

例 4： S 是矩陣A的所有行 $A_1,\cdots\cdots,A_n$所成的集合, $\vartheta$是所有S的線性獨立子集所成的集合,則$(S,\vartheta)$ 是一擬陣。
例 5： G=(V,E)是一圖網,V為其頂點集,E為邊集, $\vartheta$是所有E不含迴路的子集所成集合族, 則$(E,\vartheta)$是一擬陣。
例 6： $A_1=(A_1,\cdots\cdots,A_n)$是一集合族, $S=A_1\bigcup \cdots\cdots \bigcup A_n$, $\vartheta=\{ X\subseteq S$:對所有 i恒有 $\vert X\bigcap A_i\vert\leq 1 \}$,則$(S,\vartheta)$是一擬陣。 這個擬陣和研究A的相異代表系有密切的關係。

   

上頁　1│2│3│4　次頁

 回頁首
 
（若有指正、疑問……，可以在此 留言 或 寫信 給我們。）
EpisteMath

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有


編輯：林君怡 ／ 校對：黃怡碧 ／ 繪圖：簡立欣 最後修改日期：4/26/2002