图的同构关系判定中必要条件的补充.pdfVIP

第 21卷 第6期 四川理工学院学报 (自然科学版) Vo1．21No．6 JOURNAL OF SICHUAN UNIVERSITY OF 2008年 l2月 SCIENCE ＆ENGINEERING(NATURALSCIENCE EDITION) DeC．2008 文章编号 ：1673-1549(2008)06-0046-03 图的同构关系判定中必要条件的补充 黄元清，曾 薇 (四川理工学院计算机科学系，四JII自贡643000) 摘 要：文章通过对图的同构关系的分析，提 出了2个图同构的新的必要条件，并举例讨论 了增加这个必要 条件后，在简化证明2个图不同构的过程中的实际效果。 关键词：图形；图的同构；一一对应的映射；必要条件 中图分类号：TP31l 文献标识码：A 1问题 的提 出 且保持相同的关联关系，即对应结点对所构成的边相对 图论是现代数学的重要分支，是数学与计算机科学 应 。 以及数学与其它学科相互渗透和相互影响的桥梁，是建 在 图论的实际应用中，快速、准确判定出2个图是 立和处理离散数学模型的一个重要的工具。由于客观现 否同构是非常重要的。然而，这种判定有时又是非常困 实中的许多状态都可 以由图来描述 、并用图论的相关知 难的。因为到 目前为止还没有找到判定两个图是否同构 识来解决。因此，图论是一 门实用性很强的新兴的工具 的简单方法或算法。要判定2个图是否同构，还只能根 性学科 。 据定义来完成。 图论中的 “图”主要有 3种表示方法，即：一个图可 实际操作中，根据 图的实际情况，一般采用下面的 以用图形 ，用数学公式 以及用矩阵来表示。其 中，一个 图 2种方法判定 2个 图是否同构： 的图形是 由一些结点(它对应客观现实中处理的实际问 当2个 图比较简单而且又能直观的认定是同构图 题所涉及的对象)和经过两个结点之问的连线，即边 (它 时，对其同构性的判定相对 比较简单。在这种情况下，可 对应客观现实中处理的实际问题所涉及对象之间的关 以通过对图的旋转、翻转 以及对结点的移动或对边的变 系)所组成的。 形等手段，找到结点与结点以及边与边之间 (在保持相 用图形来表示一个图，具有简单、直观等优点。但 由 同关联关系情况下)的对应关系，以此得到两个图同构 于在这种表示法中，结点的位置及连线的长度和形状可 的证明。 以任意，因此，这种表示法不具有唯～性，即一个图可 以 但当2个图比较复杂，无法直观的认定是否同构， 有多个 图形。有些图形尽管外表形状差异很大，但都表 或者可以初步认定不同构时，对其同构性的判定则比较 示同一个图。 麻烦。因为要 由定义证明2个 图的结点与结点之间、边 这些外观不同，但都表示同一个图的不同图形之间 与边之间不存在这种在保持相同关联关系下的对应关 的关系称为是同构关系。 系，往往需要在一定范围内对结点的各种不同的对应情 定义、设无 向图G= ，D 和 G= ，E。若其结点 况进行”穷举”。这样做既费时又可能不精确、不严密。为 问存在一一对应 的映射 ：：ui~u ，且边 e=( )是 G中 此，现在的教材及参考书上通过对定义的分析，给出了 的一条边 ，当且仅当： 判定两个图同构的3个必要条