上頁 1234 次頁

相異代表系古今談 (第 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的相異代表系有密切的關係。

   

上頁 1234 次頁

回頁首
 
(若有指正、疑問……,可以在此 留言寫信 給我們。)
EpisteMath

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


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