随机可分解的多重图与等可填充的多重图

摘要

分解与填充问题是图论的主要研究内容之一,在网络设计、组合优化理论、结晶学及运筹学等领域都有十分重要的意义.多重图是图论的主要研究对象之一,同时也是图论中的一个活跃的研究领域.多重图的研究结果可以应用于计算机网络、智能交通、通讯网络等领域,发挥着不容忽视的作用.图论中的分解与填充问题有多种,本论文研究了其中的两类:随机H-可分解的多重图与H-等可填充的多重图的特征刻画问题.若图M含有自环或者重边,则称M是多重图.设H是多重图M的一个给定子图,若多重图M的每一族边不交的同构于H的子图都可以扩展为M的一个分解,则称M为随机H-可分解的.设H1,H2……,Hl为多重图M的一个H-填充,若不含同构于H的子图,则称H1,H2,…,H1为M的一个极大H-填充.若M中不存在多于I个同构于H的两两不交的子图,则称H1H2,…,H1为M的一个最大H-填充.若M的每个极大H-填充都是它的最大H-填充,则称M为H-等可填充的.随P3-可分解的简单图、随机P4-可分解的简单图、P3-等可填充的简单图的特征已经被刻画.本论文完全刻画了随机P3-可分解的多重图和随机P4-可分解的多重图的特征,然后刻画了P3-等可填充的多重图的特征.

目录

封面

声明

中文摘要

英文摘要

目录

第 一 章 引 言

第二章随机可分解的多重图

§2.1 基本概念

§ 2 .2随机巧-可分解的多重图

§ 2 .3随机巧-可分解的多重图

第三章等可填充的多重图

§3.1 基本概念

§3.2 P 3- 等可填充的多重图

第 四 章 结 束 语

参考文献

攻读硕士期间所发表论文

致谢