匹配擬陣(matching matroid)一類特殊的擬陣.它是建立在圖G=<V,E)上的擬陣.節點集V的子集A為此擬陣的獨立集，若且唯若圖G有匹配覆蓋A.例如，當G為三角形時，若其頂點為a,b,c，則相應的匹配擬陣的獨立集為{a},{b},{c},{a,b},}a,c}，(b,c).
基本介紹
- 中文名：匹配擬陣
- 外文名：matching matroid
匹配擬陣(matching matroid)一類特殊的擬陣.它是建立在圖G=<V,E)上的擬陣.節點集V的子集A為此擬陣的獨立集，若且唯若圖G有匹配覆蓋A.例如，當G為三角形時，若其頂點為a,b,c，則相應的匹配擬陣的獨立集為{a},{b},{c},{a,b},}a,c}，(b,c).
“擬陣”這個詞是由Hassler Whitney最早開始使用的。他曾研究矩陣擬陣，其中S是給定矩陣的各個行，如果這些行在通常意義下是線性無關的，則他們是獨立的。有限擬陣定義 有限擬陣有很多等價的定義方式。獨立集 Independent sets：就獨立來說...
第一個是研究圖和擬陣的處處非零流，群連通度（非齊次處處非零流）和模(2s+1)-定向的問題。第二個是研究與等密圖和擬陣相關的問題。我們的第一個目標是Tutte的3-流猜想和5-流猜想以及Jaeger關於圖的模(2s+1)-定向的猜想。我們...
同時，也出現了各種統一性的理論研究，如超圖、擬陣以至於組合幾何，其發展更是日新月異，圖論還廣泛而且愈來愈深入地滲透和套用到其他科學中去，除原來在物理學和化學中的套用又得到廣泛和深入的發展之外，還深入到了生物學和生物工程...
匹配擴張為最大匹配、分數匹配擴張為分數完美匹配等問題。這些問題都是匹配理論中研究的新問題。本研究不僅開闢了匹配理論與分數圖論研究的新領域，而且為研究圖的完美匹配計數問題、完美匹配擴張問題、擬陣的獨立集系統提供新的方法。
4. 5. 2 擬陣理論 習題二 4. 6 倒稱矩陣與層次分析 4. 7 正交拉丁方 4. 8 區組設計與區組矩陣 4. 8. 1 BIBD問題 4. 8. 2 區組關聯矩陣 4. 8. 3 Hadamard矩陣 4. 8. 4 區組設計的構作 4. 9 魔矩陣密碼 習...
主要研究內容有：線性組合最最佳化問題；網路上的最最佳化問題；獨立系統和擬陣，擬陣是組合最佳化中一個基本而重要的概念，許多組合問題都可化為擬陣問題。貪心算法是求擬陣的最優獨立集的簡單算法；交錯鏈算法是求解最優交問題的基本算法。對...
圖論中的著名算法有求最小生成樹的Kruskal算法、求最短路的Dijkstra算法和Floyd算法、求二部圖最大匹配(指派問題)的匈牙利算法、求一般圖最大匹配的Edmonds"花”算法、求網路最大流和最小割的標號法等。貪心法與擬陣 貪心法是求解關於...
82 擬陣 8.2.1 遺傳系統及示例 8.2.2 擬陣的性質 8.2.3 生成函式 8.2.4 擬陣的對偶 8.2.5 擬陣的子式與可 平面對偶 8.2.6 擬陣的交 8.2.7 擬陣的並 8.2.8 習題 83 拉姆齊理論 8.3.1 鴿巢原理的再...
圖論與算法圖論、組合論、代數系統、數理邏輯、離散數學中的空間、矩陣和擬陣、Turing機和計算複雜度理論,每篇配有難易適當的足夠作業題。 全書概念與理論明晰嚴謹,注重算法與套用,文字洗鍊生動,立論深入淺出,可讀與可教性強。 [2] 離...
因此，把以偏截元為其獨立集的擬陣，稱為截元擬陣，對於截元擬陣，其對偶擬陣一般不再是截元擬陣，但是，截元擬陣和匹配擬陣本質上是一回事，因為：一個擬陣是匹配擬陣，若且唯若它是截元擬陣，這同時表明截元擬陣在組合論中的重要...
8．2 擬陣 遺傳系統和示例 擬陣的性質 生成函式 擬陣的對偶性 擬陣的子式和可平面圖 擬陣的交 擬陣的並 習題 8．3 Ramsey理論 鴿巢原理的再研究 Ramsey定理 Ramsey數 關於圖的Ramsey理論 Sperner引理和頻寬 習題 8．4 其他極值問題...