论文部分内容阅读
分解与填充问题为图论中非常重要而又基本的问题，不仅对研宄图的结构性质有重要意义，而且在网络设计中有很强的应用价值.图论中的分解与填充问题有多种，本论文研宄了其中密切相关的两类：随机H-可分解图与H-等可填充图的刻画问题.若图G中每个H-可分解子图的H-分解都可以扩充为图G的一个H-分解，则称G为随机H-可分解的.若G的每个极大H-填充都是它的最大H-填充，则称G为H-等可填充的.本文刻画了所有的随机巧U巧-可分解图、随机C3-可分解的图和一些特殊的巧U巧-等可填充的图，并把C3-等可填充问题转化成了其它的等价问题.