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

摘要

给定图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之间的关系.

目录

声明

摘要

前言

第1章 绪论

1．1 基本概念

1．2 平面图的平衡二部子图问题及已有的结论

1．3 本文的主要结果

第2章 含有近似等边三角形平面图的平衡二部子图

2．1 本章的主要结论

2．2 引理的证明

2．3 定理的证明

第3章 哈密尔顿二部平面图

3．1 本章的主要结论

3．2 引理的证明

3．3 定理的证明

第4章 含有-内部三角形平面图的平衡二部子图

4．1 本章的主要结论

4．2 引理的证明

4．3 定理的证明

参考文献

致谢