發(fā)布時(shí)間：2018-04-05 18:20

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

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

本文編號(hào)：1715916