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

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

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

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

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

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

6、一個有限集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的一個獨立集.對于不在I中E的子集，我們稱之為相關(guān)集.極小的相關(guān)集稱為擬陣的圈，我們可以用擬陣的

7、圈集合去定義擬陣.
　　令E為一個含有有限個元素的集合.令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的一個極大獨立集被稱為擬陣M的基，表示為B(M).擬陣M中一個基B(M)的元素個數(shù)定義為擬陣

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

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

10、f(e)，其中，E+(v)和E-(v)分別表示方向在點上出邊的集合和入邊的集合.一個k-流(D，f)是處處非零的(或簡稱為k-NZF)如果f(e)≠0，對于任意的e∈E(G)都成立.
　　設(shè)圖G是無向圖，A是一個非平凡的阿貝爾加群（單位元為0），A*是A中非零元素所構(gòu)成的集合.我們定義F(G，A)={f|f:E(G)→A}和F*(G,A)={f|f:E(G)→A*}.對于每一個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的處處非零A-流(簡稱A-NZF)指的是一個函數(shù)f∈F*（G，A)使得(e)f=0成立.如果一個圖G有一個處處非零的k-流當(dāng)且僅當(dāng)圖G有一個處處非零的Zk-流.
　　對于任意的b∈Z(G，A)，如果有一個函數(shù)f∈F*(G，A)使得(

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