圖的運(yùn)算與最小圈基的結(jié)構(gòu).pdf

1、關(guān)于圖的最小圈基的研究從產(chǎn)生發(fā)展到現(xiàn)在，眾多的學(xué)者包括數(shù)學(xué)家，生物學(xué)家，物理學(xué)家等等已經(jīng)提出了許多相關(guān)的方法。但應(yīng)該指出的是，到目前為止，這些算法和結(jié)果都往往僅限于針對某種或某些類型的圖的最小圈基結(jié)構(gòu)，而從圖的運(yùn)算的角度考慮最小圈基的結(jié)構(gòu)，這方面的工作確是鮮為人知的，本文正是首先由一般的情況著手，再擴(kuò)展到射影平面的相關(guān)結(jié)論。 首先，我們研究2-連通的簡單平面圖的運(yùn)算對最小圈基的影響：設(shè)G<,1>，G<,2>為2-連通的簡單平面圖

2、，B<,1>為G<,1>的最小圈基，B<,2>為G<,2>的最小圈基。 1、當(dāng)圖G<,1> ∩G<,2>=x即G<,1>，G<,2>相交于一個點(diǎn)時，圖G的最小圈基為G<,1>，G<,2>的最小圈基的并集。 2、當(dāng)圖G<,1> ∩G<,2>={x，y}即G<,1>，G<,2>相交于兩個點(diǎn)時，由于圖的運(yùn)算使圖的圈基維數(shù)增加了1，圖G的最小圈基為G<,1>，G<,2>的最小圈基的并集以及一個新圈。 3、當(dāng)圖G<,1>

3、∩G<,2>=P<,xy>即G<,1>，G<,2>相交于一條過x，y兩點(diǎn)的最短路時，圖G的最小圈基為圖G<,1>，G<,2>的最小圈基的并集。 4、當(dāng)圖G<,1> ∩G<,2>=P<,xy>，即G<,1>，G<,2>相交于一條過x，y兩點(diǎn)的非最短路，且圖G<,1>，G<,2>中所有的二度節(jié)點(diǎn)都位于路P<,xy>上。我們分兩種不同的情況在定理2.2.4和定理2.2.5中做出了詳盡論述。其中主要的思想是通過圖的運(yùn)算引進(jìn)了新的通過點(diǎn)x

4、，y的最短路，對原最小圈基做出相應(yīng)的運(yùn)算。 在第三章中討論2-連通的在射影平面上可大邊寬度嵌入圖的最小圈基結(jié)構(gòu)，并且就這樣的大邊寬度嵌入圖有唯一最長而圈和不唯一最長而圈兩種情況在定理3.1.2和定理3.1.3中做了詳盡論述?？紤]一個圖的圈空間中圈基的組合結(jié)構(gòu)，證明了一個圖的所有最小圈基具有唯一結(jié)構(gòu)，即任意的兩個最小圈基之問存在1-1對應(yīng)，使得相互對應(yīng)的圈具有相同長度。由此可知，任兩個最小圈基中所含k-圈(k≥3)的數(shù)目相同。