论文部分内容阅读
近年来,用代数的方法解决图论中的问题越来越受到关注,并且已经形成了一套理论──代数图论,而图的同态与同构就是其中之一,很多时候,图的同态与同构作为一种工具被广泛应用,尤其是与图的着色有关的问题,超图是有限集合的子集系统,是最一般的结构并且在离散数学中起着非常重要的作用,而超图的同构已于1972年被Berge提出,并得到了很多相应的结果,但超图的同态却尚未提出,本文参照图的同态,提出了超图的同态,继而利用超图的同态研究了超图的相关问题,并得出了相应的结果,整篇文章中,我们处理了与超图同态有关的问题,并分为4个部分阐述:
第一部分:给出了超图同态的概念及其一些基本性质,得出了与强色数有关的一个基本性质。
第二部分:定义r-一致超图的核与收缩,证明了r-一致超图的核在同构意义下是唯一的并得到了关于核与收缩的结果。
第三部分:定义了两个r-一致超图的积,与映射超图,得到了与映射超图,积超图相关的结果,通过同态计数导出了映射超图的有趣性质。
第四部分:提出了积超图的强色数猜想: Xs(H1×H2)=min{Xs(H1),Xs(H2)}通过映射超图的性质研究此猜想,并证明了在某些特殊情况下此猜想的正确性。