本文選題：可平面圖　切入點：哈密爾頓圈　出處：《南京師范大學(xué)》2014年碩士論文

【摘要】：給定圖G,及V(G)的一個二部劃分V1,V2,我們用G(V1,V2)來表示G的一個二部子圖,G(V1,V2)的每條邊有一個頂點在V1中,另一個在V2中.若G(V1,V2)是G(V,E)的一個二部子圖,且V1,V2滿足||V1|-|V2||≤1,則稱圖G(V1,V2)是G(V,E)的一個平衡二部子圖.G(V E)的最小平衡二部子圖問題是指尋找G(V,E)的一個平衡二部子圖G(V1,V2)使得連接V1,V2的邊數(shù)e(V1,V2)最少.關(guān)于平面圖的平衡二部子圖的研究有一個猜想：任意一n個頂點的平面圖G(V,E)必含有一個平衡二部子圖G(V1,V2)使得e(V1,V2)≤n. Genghua Fan等[8]證明了對任意一個無可分離三角形的平面圖必含有一個平衡二部子圖G(V1,V2),使得e(V1,V2)≤n+1. 本文在文獻[8]的基礎(chǔ)上主要研究了含有哈密爾頓圈平面圖的平衡二部子圖的大小 第一章我們主要給出了一些基本的概念及與本文相關(guān)的結(jié)果,第二章研究了當(dāng)哈密爾頓平面圖含有近似等邊三角形(定義見正文)時,最小平衡二部子圖的上界.第三章討論了一種特殊結(jié)構(gòu)與其平衡二部子圖之間的關(guān)系,即當(dāng)平面圖G(V E)為含有哈密爾頓圈的二部圖時,最小平衡二部子圖的上界.第四章從內(nèi)部三角形的角度來研究最小平衡二部圖的上界,當(dāng)S-內(nèi)部三角形的最長邊與最短邊之差為d時,含有哈密爾頓圈平面圖的最小的平衡二部子圖與d之間的關(guān)系.
[Abstract]:Given a bipartite partition of a graph G, and a bipartite partition of V _ (1) V _ (2), we denote a bipartite subgraph of G (G ~ (1) V _ (1) V _ (2)) with one vertex in V _ 1 and another in V _ 2.鑻(V1,V2)鏄疓(V,E)鐨勪竴涓簩閮ㄥ瓙鍥，

本文編號：1715916