圖的運(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é)果都往往僅限于針對(duì)某種或某些類(lèi)型的圖的最小圈基結(jié)構(gòu)，而從圖的運(yùn)算的角度考慮最小圈基的結(jié)構(gòu)，這方面的工作確是鮮為人知的，本文正是首先由一般的情況著手，再擴(kuò)展到射影平面的相關(guān)結(jié)論。 首先，我們研究2-連通的簡(jiǎn)單平面圖的運(yùn)算對(duì)最小圈基的影響：設(shè)G<,1>，G<,2>為2-連通的簡(jiǎn)單平面圖

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

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

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