论文部分内容阅读
本论文研究了点边赋权连通图上的划分问题，称为点边赋权图上的七一划分问题．对于一个点边赋权连通图G和一个正整数七，把图G划分为几个子图，使得(1)所有子图的点边赋权最小支撑树的权重之和达到最小； (2)所有子图的点边赋权最小支撑树中权重最大者达到最小．我们得到如下结果，． (1)给出一般图G上的和树划分的多项式算法及最小最大树的后一近似算法； (2)给出一些特殊图上的最小最大树划分的多项式时间算法．本论文包括以下四章：第一章：回顾了问题的由来，给出了最近的一些相关研究成果．第二章；给出了文中所出现的定义、概念和符号．第三章：给出一般图上的和树划分最优算法及最小最大树划分七一近似算法及特殊图上的最小最大树划分问题的多项式算法．第四章：给出了相关结论以及未来的研究方向。