平面图最小平衡二部划分的上界

发布时间：2018-04-05 18:20

  本文选题：可平面图　切入点：哈密尔顿圈　出处：《南京师范大学》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的边数e(V1,V2)最少.关于平面图的平衡二部子图的研究有一个猜想：任意一n个顶点的平面图G(V,E)必含有一个平衡二部子图G(V1,V2)使得e(V1,V2)≤n. Genghua Fan等[8]证明了对任意一个无可分离三角形的平面图必含有一个平衡二部子图G(V1,V2),使得e(V1,V2)≤n+1. 本文在文献[8]的基础上主要研究了含有哈密尔顿圈平面图的平衡二部子图的大小 第一章我们主要给出了一些基本的概念及与本文相关的结果,第二章研究了当哈密尔顿平面图含有近似等边三角形(定义见正文)时,最小平衡二部子图的上界.第三章讨论了一种特殊结构与其平衡二部子图之间的关系,即当平面图G(V E)为含有哈密尔顿圈的二部图时,最小平衡二部子图的上界.第四章从内部三角形的角度来研究最小平衡二部图的上界,当S-内部三角形的最长边与最短边之差为d时,含有哈密尔顿圈平面图的最小的平衡二部子图与d之间的关系.
[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.鑻�G(V1,V2)鏄疓(V,E)鐨勪竴涓�浜岄儴瀛愬洠�

本文编号：1715916