论文部分内容阅读
图同态作为工具经常出现在各个应用领域,尤其是在图的着色理论以及计算机科学的语法理论,并且在实际生活中,涉及任务分配的实际问题往往可以转化为图同态的存在与优化问题.在七十年代初期,P.Hell在他的博士论文中分析了一类特殊的图同态——收缩,打开了图同态研究的新局面,图的核(最小收缩)成为图同态的重要课题.近二十年来,核的研究得到很大程度的推广,出现了伪核,核完全图,壳等一系列重要概念.本文的工作是讨论弱核,伪核与壳相关性质以及与核关系紧密的同态图与图的笛卡尔积的性质. 本文共分五章, 第一章简要介绍课题背景,研究内容和主要结果; 第二章给出图,图同态和群的基本结果,并初步给出核,伪核,弱核,壳,图的笛卡尔积等的性质; 第三章首先给出核的性质的汇总,以及提供一些常用的实例;然后刻画弱核和伪核的性质,给出一些判断弱核和伪核的充要条件和不平凡的例子;最后分析了壳与弱核的相关性质. 第四章介绍图的笛卡尔积与幂等图,并利用同态图为工具,给出了图的笛卡尔积和幂等图的重要性质.