论文部分内容阅读
一个连通图称为多重median图，如果任取它点集中的三个点u, v, w，至少有一个顶点同时在一条最短u, v?路，一条最短u, w?路以及一条最短v, w?路上。Median图是图的重要的一种结构特性，常见的树和超立方图都是median图。多重median图作为median图的一种自然推广，对研究图的结构和性质具有重要的意义。本文主要对多重median图的性质进行了研究，有以下几个方面：多重median图与部分立方图的关系；多重median图的区间导出子图仍是多重median图；通过粘点、粘边图运算后的多重median图；给出并运用多重median图的禁止子图来探究其在删边图运算下的性质。 全文共包含五章。第一章，主要介绍了图论的发展史以及median图、多重median图的研究现状。 第二章主要研究了多重median图和部分立方图的关系。首先给出median图是部分立方图的一种证明，紧接着证明除了median图之外的多重median图——严格多重median图都包含一个K2,3作为它的子图，最后通过证明K2,3不是部分立方图来证明严格多重median图都不是部分立方图。 第三章主要给出了多重median图的区间导出子图仍是多重median图的证明。 第四章首先证明了多重median图经过粘点和粘边运算后仍是多重median图，从而为构造多重median图提供了方法；接着利用多重median图的禁止子图给出了平面多重median图删去一条特定的边之后不再是多重median图的证明，并提出了一些问题和猜想。 第五章对本文的研究内容进行了简单的总结和展望，以期对接下来的研究起到一定的作用。