擬陣基的交圖的性質(zhì).pdf

1、圖論和擬陣?yán)碚撛诙兰o(jì)經(jīng)歷了空前的發(fā)展.圖論起源于著名的哥尼斯堡七橋問(wèn)題.在圖論的歷史中，還有一個(gè)最著名的問(wèn)題-四色問(wèn)題.四色問(wèn)題又稱四色猜想，是世界近代三大數(shù)學(xué)難題之一.四色猜想的提出來(lái)自英國(guó).1852年，畢業(yè)于倫敦大學(xué)的弗南西斯·格思里來(lái)到一家科研單位搞地圖著色工作時(shí)，發(fā)現(xiàn)了一種有趣的現(xiàn)象:”看來(lái)，每幅地圖都可以用四種顏色著色，使得有共同邊界的國(guó)家都被著上不同的顏色.”1872年，英國(guó)當(dāng)時(shí)最著名的數(shù)學(xué)家Cayley正式向倫敦?cái)?shù)學(xué)學(xué)

2、會(huì)提出了這個(gè)問(wèn)題，于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問(wèn)題.世界上許多一流的數(shù)學(xué)家都紛紛參加了四色猜想的大會(huì)戰(zhàn).1878-1880年兩年間，著名律師兼數(shù)學(xué)家Kapel和Taylor兩人分別提交了證明四色猜想的論文，宣布證明了四色定理.但后來(lái)數(shù)學(xué)家Heawood以自己的精確計(jì)算指出肯普的證明是錯(cuò)誤的.不久，Taylor的證明也被人們否定了.于是，人們開始認(rèn)識(shí)到，這個(gè)貌似容易的題目，其實(shí)是一個(gè)可與費(fèi)馬猜想相媲美的難題.二十世紀(jì)三十年代，Whit

3、ney在他的論文中，作為對(duì)矩陣和向量的獨(dú)立性的抽象概括，首次提出了擬陣的概念.同時(shí)，擬陣也抽象了很多圖的性質(zhì).擬陣?yán)碚摓榻M合優(yōu)化問(wèn)題和設(shè)計(jì)多項(xiàng)式算法提供了強(qiáng)有力的工具.圖的支撐樹及擬陣的基都是組合理論的基本研究對(duì)象.一個(gè)連通圖的樹圖能夠反映該圖的不同支撐樹之間的變換關(guān)系.因此，研究一個(gè)圖的樹圖有助于我們更好地了解該圖的性質(zhì).同樣的一個(gè)擬陣的基圖能夠反映該擬陣的不同基之間的變換關(guān)系.因此，研究一個(gè)擬陣的基圖有助于我們更好地了解該擬陣的性質(zhì)

4、.近些年來(lái)，樹圖和擬陣的基圖被推廣得到了一些新的圖類.為了研究擬陣中圈的性質(zhì)，P.Li和G.Liu提出了擬陣圈圖的概念，并且研究了擬陣圈圖的連通度，圈圖中的路和圈的性質(zhì).為了進(jìn)一步研究擬陣中基的性質(zhì)，Y.Zhang和G.Liu提出了擬陣基的交圖的概念.
　　設(shè)G是一個(gè)圖，圖G的點(diǎn)集和邊集分別記為V(G)和E(G).包含G的每個(gè)點(diǎn)的路稱為G的一條哈密爾頓路;同樣的，包含G的每個(gè)點(diǎn)的圈稱為G的一個(gè)哈密爾頓圈.如果一個(gè)圖存在一個(gè)哈密爾頓

5、圈，則稱之為哈密爾頓的.如果對(duì)于一個(gè)圖G的任意兩個(gè)頂點(diǎn)來(lái)說(shuō)，G都有一條哈密爾頓路連接他們，則稱G是哈密爾頓連通的.如果對(duì)一個(gè)圖G的任意一條邊來(lái)說(shuō)，G都有一個(gè)含這條邊的哈密爾頓圈，則稱G是邊哈密爾頓的，或者稱G是正哈密爾頓的，寫作G∈H+.如果對(duì)一個(gè)圖G的任意一條邊來(lái)說(shuō)，G都有一個(gè)不包含這條邊的哈密爾頓圈，則稱G是負(fù)哈密爾頓的，寫作G∈H-.如果G既是正哈密爾頓的，又是負(fù)哈密爾頓的，我們稱G是一致哈密爾頓的.
　　一個(gè)擬陣M就是對(duì)于

6、一個(gè)有限集E，令I(lǐng)為集合E中非空子集族，它滿足如下的條件:
　　(I1)(O)∈I;
　　(I2)若I2∈I且I1(∈)I2，則I1∈I;
　　(I3)若I1，I2∈I并且|I1|＜|I2|，則存在e∈I2\I1，使得I1∪{e}∈I.
　　那么我們稱M=(E，I)為定義在有限集E上的擬陣.當(dāng)I∈I(M)，我們稱I為M的一個(gè)獨(dú)立集.對(duì)于不在I中E的子集，我們稱之為相關(guān)集.極小的相關(guān)集稱為擬陣的圈，我們可以用擬陣的

7、圈集合去定義擬陣.
　　令E為一個(gè)含有有限個(gè)元素的集合.令C為集合E中非空子集族，它滿足如下的公理:
　　(C1)(O)(∈)C;
　　(C2)若C1，C2∈C且C1(∈)C2，則C1=C2;
　　(C3)若C1≠C2，C1，C2∈C并且存在e∈C1∩C2，則恒有C3∈C滿足C3(∈)(C1∪C2)-e.
　　擬陣M的一個(gè)極大獨(dú)立集被稱為擬陣M的基，表示為B(M).擬陣M中一個(gè)基B(M)的元素個(gè)數(shù)定義為擬陣

8、M的秩.令B(M)表示擬陣M中基的集合.同樣我們也可以用擬陣的基來(lái)定義擬陣:
　　(B1)所有的基的基數(shù)相同;
　　(B2)如果B1，B2∈B且x∈B1，則存在y∈B2，使得(B1\{x})∪{y}∈B.擬陣M=(E，B)的基圖是這樣的一個(gè)圖G，其中V(G)=B，E(G)={BB'|B，B'∈B，|B\B'|=1}，注意在這里圖G的頂點(diǎn)和M的基用同樣的符號(hào)表示.
　　現(xiàn)在我們給出擬陣基的交圖的概念.定義擬陣M的基的交圖

9、G=G(M)的頂點(diǎn)集V(G)=B，邊集E(G)={BB'|B，B'∈B，|B∩B'|≠0}.這里B和B'既代表G的頂點(diǎn)，也代表M的基.
　　下面我們給出整數(shù)流，也就是處處非零的k-流的定義:
　　給定一個(gè)圖G，設(shè)D為圖G的一個(gè)方向，設(shè)函數(shù)f:E(G)→Z，使得-k＜f(e)＜k，對(duì)于任意的e∈E(G)都成立.序偶(D，f)稱為圖G的k-流，如果對(duì)于任意的v∈V(G)，它滿足平衡條件:∑e∈E+(v)f(e)=∑e∈E-(v)

10、f(e)，其中，E+(v)和E-(v)分別表示方向在點(diǎn)上出邊的集合和入邊的集合.一個(gè)k-流(D，f)是處處非零的(或簡(jiǎn)稱為k-NZF)如果f(e)≠0，對(duì)于任意的e∈E(G)都成立.
　　設(shè)圖G是無(wú)向圖，A是一個(gè)非平凡的阿貝爾加群（單位元為0），A*是A中非零元素所構(gòu)成的集合.我們定義F(G，A)={f|f:E(G)→A}和F*(G,A)={f|f:E(G)→A*}.對(duì)于每一個(gè)f∈F(G，A)，f的邊界函數(shù)(e)f(v):V(G)

11、→A的定義如下:(e)f（v）=∑e∈E+(v)f(e)-∑e∈E-(v)f(e)，其中“∑”指的是阿貝爾群里的加法.我們定義Z(G，A)={b|b:V(G)→A，∑v∈V(G)b（v）=0}.一個(gè)圖G的處處非零A-流(簡(jiǎn)稱A-NZF)指的是一個(gè)函數(shù)f∈F*（G，A)使得(e)f=0成立.如果一個(gè)圖G有一個(gè)處處非零的k-流當(dāng)且僅當(dāng)圖G有一個(gè)處處非零的Zk-流.
　　對(duì)于任意的b∈Z(G，A)，如果有一個(gè)函數(shù)f∈F*(G，A)使得(

12、e)f=b成立，那么我們稱f是一個(gè)處處非零(A，b)-流(簡(jiǎn)稱(A，b)-NZF).
　　Jaeger等人推廣了整數(shù)流的概念，提出了A-連通的概念，一個(gè)無(wú)向圖G稱為A-連通的，如果G的每一個(gè)定向G'對(duì)于每一個(gè)函數(shù)b∈Z(G'，A)，都存在一個(gè)(A，b)-NZF，記作G∈.同樣的，G有A-NZF當(dāng)G有定向G'使得G'有A-NZF.A-連通性的概念是Jaeger等人提出的，A-NZF與A-連通性有密切關(guān)聯(lián).
　　本文主要研