圖的生成樹和最大虧格.pdf

1、虧格是圖的一個(gè)拓?fù)洳蛔兞?根據(jù)Duke關(guān)于圖虧格的內(nèi)插定理,最大虧格的界定對(duì)于研究圖的虧格分布具有重要意義.
　　本文主要研究一個(gè)圖的生成樹與圖的最大虧格之間的關(guān)系以及它在圖的上可嵌入性方面的應(yīng)用.其主要結(jié)果如下:（1）通過圖G的生成樹變換,我們可以改變一個(gè)生成樹T與其余樹G-E（T）的連通分支的奇偶性.由此,給出了黃元秋和劉彥佩定理的一個(gè)新的證明.特別地,設(shè)T為圖G的一棵最優(yōu)樹,記G’是在G中加入一對(duì)關(guān)于T相鄰的邊e’和e”所得

2、到的圖.則ξ（G’）≤ξ（G）.從而γM（G’）≥γM（G）+1;特別地,若G是上可嵌入的,則G’也是上可嵌入的.
　　結(jié)合上面的結(jié)論,我們給出了由最優(yōu)樹所確定的基本圈全體的一個(gè)性質(zhì):基本圈全體可以被分解成兩部分:其一,{C1,C2,C3,C4,…,C2k-1,C2k),k=γM（G）,C2k-1∩C2i≠（?）,（1≤i≤k）;其二,{C2k+1,C2k+2,…,C2k+s),s=ξ（G）,（這里ξ（G）為圖G的Betti虧數(shù)）

3、,且任意兩個(gè)基本圈不相交.（2）借助于生成樹變換理論,我們得到一個(gè)關(guān)于局部連通圖G的最優(yōu)樹奇連通分支的遍歷性結(jié)果:對(duì)于局部連通圖G,若ξ（G）=1,則給定頂點(diǎn)x∈V（G）,一定存在一棵最優(yōu)樹T使得x屬于G關(guān)于T的奇連通分支.在此基礎(chǔ)上,給出LNebesk（?）定理的一個(gè)新證明.將其推廣,我們得到一些新的上可嵌入圖類,比如:G1,G2是局部連通圖,S={e1,e2,…,ek},（k≥2）是一邊集,在G1,G2中加入邊集S,使得S中的每條邊