同态

距离正侧图

作业

学号：201421130027 姓名：裴慧辉

第六章 同态

6.1 基础知识

如果Y X ,和Z 是图，并且f 是从X 到Y 的同态映射，g 是从Y 到Z 的同态映射，那么f g 是X 到Z 的同态映射。

证明 显然f g 是X 到Z 的映射，又y x ,∈()X V ，若y x ~，则()()y f x f ~，因而()()()()y f g x f g ~，即()()()()y f g x f g ~，故f g 是X 到Z 的同态。

现在，定义一个关系""→:Y X ,是图，如果X 到Y 有同态映射，

则有Y X →。由于两个同态的合成仍是同态映射，""→是一个可传递的关系。因为恒等映射是同态映射，那么对任意图X 都有X X →，因此""→也是反身的。而关系""→并不是偏序的，因为它

不是反对称的。即如果Y X

→和X Y →，这并不能说明Y X =（如X

是二部图，Y 是2K ）。 如果X 和Y 是图，并且有从X 到Y 的同态映射及Y 到X 的同态映射，那么我们称X 和Y 是同态等价。X 到Y 的同态映射称为是满射，如果Y 的每个顶点都是X 的某个顶点的像。若有X 到Y 的满同态和Y 到X 的满同态，那么X 和Y 同构。

如果f 是X 到Y 的同态映射，那么Y 的每个顶点y 的原像()y f 1-叫做f 的纤维。f 的纤维决定了一个叫做f 的零的()X V 的分类π，定义一个图πX ，点集是π的元素，π的两个元之间有边若存在X 的边，它的端点在这两个元中。从X 到πX 有一个自然的同态映射。

证明从一个图到另一个图没有同态映射通常是比较困难的事，但有两个比较有用的参数。一个图Y 是r 可着色的当且仅当存在Y 到r K 的同态映射，所以，如果存在X 到Y 的同态映射，则我们有r K Y X →→，所以()()r Y X =≤χχ。因此，若()()Y X χχ>，那么X 到Y 没有同态映射。若X 有长为l 的奇圈，并且Y 的任意一个奇圈的长度都大于l ，那么X 到Y 没有同态映射，因为奇圈的同态像一定是比它长度小的奇圈。我们把一个图X 的最小奇圈的长度叫做X 的奇围长。X 的奇围长是它的任一同态像的奇围长的上

界。

6.2 核

图X称为核，如果X到自身的任何同态映射都是双射，或者等价地，如果它的自同态幺半群是它的自同构群。我们将会看到每个图都有核，并且它的所有核都是同构的。我们用?X来标记X 的核。如果Y是X的核并且f是X到Y的同态映射，那么Y

f|一定是Y的自同构。f和这个自同构的逆的合成是Y上的恒等映射。因此，X的核都是收缩。

图X称作是-χ临界的，如果它的任一真子图的色数都比()X

χ小。-χ临界图不可能有到它的任一真子图的同态映射。因此，它一定是自身的核。这提供了一大类核，包括所有完全图和奇圈。引理6.2.1 X和Y是核，那么X和Y是同态等价的当且仅当它们是同构的.

证明假设X和Y是同态等价的，并且Y

:是它们

X

g→

X

f→

:和Y

之间的同态映射，因为g

g 一定都是双射，那么f和g都

f 和f

是双射，所以X和Y是同构的。反过来是显然的。

引理6.2.2 每个图X都有核，它是X的导出子图并且在同构的意义下是唯一的.

证明因为X是有限的并且恒等映射是同态映射，满足X到它存在同态映射的X的子图族是有限的且是非空的，因此在包含的意义下，这个子图族存在一个极小的子图Y。这个极小的子图Y就是X的核，因为若g是Y到Y的同态映射，显然存在X到Y的同态

映射f ，那么g X f g Im :→ 是满同态，由Y 的选择知Y g =Im ，故g 是满的，因而也是单的，故Y 是X 的核。由于核是收缩，它自然是X 的导出子图。现在，假设1Y 和2Y 是X 的核，i i Y X f →:，那么1221:|Y Y Y f →和2112:|Y Y Y f →，由引理6.2.1,1Y 和2Y 是同构的。

引理6.2.3 两个图X 和Y 是同态等价的当且仅当它们的核是同构的.

证明 若存在同态映射Y X f →:，那么我们有一系列同态映射：??→→→Y Y X X ，它们的合成是?X 到?Y 的同态映射。因此，若X 和Y 是同态等价的，那么?X 和?Y 也是。

另一方面，若存在同态映射??→Y X f :，那么我们有一系列同态映射：Y Y X X →→→??，它们的合成是X 到Y 的同态映射。因此，若?X 和?Y 是同态等价的，那么X 和Y 也是。

因此，两个图是同态等价的当且仅当它们的核也是同态等价的，由引理6.2.1，两个核是同态等价的当且仅当它们同构。所以，结论得证。

我们将""→看作核的同构类的集合上的关系，那么上面的证明可以得到下面的结果。

推论6.2.4 关系""→在核的同构类上是偏序的.

证明 我们已经知道关系""→在图的同构类上是可传递的和反身的，因此，它在核的同构类上依然成立。由引理6.2.1，若X 和Y 是核，并且Y X →，X Y →，那么X 和Y 同构。所以""→是反对称的，因而是偏序的。

6.3 积

X 和Y 是图，

它们的积Y X ?有点集()()Y V X V ?，并且()()y x y x '',~,当且仅当x x '~，y y '~。将()y x ,映成()x y ,的映射是Y X ?到X Y ?的同构映射。容易验证6263222C K C K K ????，所以若21Y X Y X ???，这不能推出21Y Y ?。连通图的积是连通的当且仅当其中至少有一个

图不是二部图。

在()X V 中固定点x ，Y X ?中形如()y x ,的点构成了一个独立集。所以，映射

()x y x P X ,:

是Y X ?到X 的同构映射。我们称这个映射为Y X ?到X 的投影。类似的，有从Y X ?到Y 的投影映射。

定理 6.3.1 Y X ,和Z 是图，若X Z f →:和Y Z g →:，那么存在唯一的一个同态映射Y X Z ?→:?满足? X P f =和? Y P g =. 证明 若有同态映射X Z f →:和Y Z g →:，那么映射

()()()z g z f z ,: ?

自然是Z 到Y X ?的同态映射，且满足? X P f =和? Y P g =。?是由f 和g 唯一确定的。

若X 和Y 是图，我们用()Y X Hom ,来表示所有X 到Y 的同态映射集。

推论6.3.2 对任意图Y X ,和Z

()()()|,||,||,|Y Z Hom X Z Hom Y X Z Hom ?=?.

一个偏序集是一个网格，如果它的每对元有一个最小的上界

和一个最大的上界。这是核的同构类集合的另一性质。 引理6.3.3 核的同构类集是网格，其中偏序由""→定义. 证明 X 和Y 都是核，显然地，

()??→?→Y X Y X X 且()??→?→Y X Y X Y .

对任意核Z ，若Z X →和Z Y →，那么

()Z Y X Y X →?→??.

因此，()??Y X 是X 和Y 的最小的上界。

对于最大的下界，显然地，

()X Y X Y X →?→??且()Y Y X Y X →?→??.

对任意核Z ，若X Z →和X Z →，那么

()??→?→Y X Y X Z .

因此，()??Y X 是X 和Y 的最大的下界。

若X 是图，那么点集(){}()x V x x x ∈,导出了X X ?的一个子图，它与X 是同构的。我们称它为积的对角线。一般的，Y X ?不包含一个子图同构于X ，如积32K K ?，它同构于6C ，因而不包含同构于3K 的子图。

下面，我们介绍与积紧密相关的另外一种结构。假设X 和Y 是图，有同态映射F X f →:及F Y g →:。()f X ,和()g Y ,的次直积是由点集()()()()(){}y g x f Y V X V y x =?∈:,导出的子图。若X 是连通的二部图，它有到2K 两个同态映射21,f f 。假设Y 是连通的且2:K Y g →。那么，()i f X ,和()g Y ,的两个次直积就是Y X ?的分支。

6.4 映射图

F 和X 是图，映射图X F 的点集是()X V 到()F V 的函数集，两个这样的函数f 与g 相邻当且仅当若v u ,在X 中相邻，那么，()u f 和()v g 在F 中相邻。X F 中的顶点有环当且仅当相应的函数是同态映射。

假设?是X 到Y 的同态映射，若f 是()Y V 到()F V 函数，那么? f 是()X V 到()F V 的函数，因此，?决定了()Y F V 到()X

F V 的一个映射，我们称它为?的伴随映射。

定理6.4.1 若F 是图，?是X 到Y 的同态映射，那么?的伴随映射是Y F 到X F 的同态映射.

证明 假设f 和g 在Y F 中相邻并且1x 和2x 在X 中相邻，那么

()()21~x x ??，

所以()()()()21~x g x f ??，即()()()()21~x g x f ?? 。因此，? f 和? g 在X F 中相邻。

定理6.4.2 对任意图X F ,和Y ，()Y

X Y X F F ??. 证明 显然Y X F ?和()Y

X F 的点集的大小相同。我们先在这两个点集间定义一个自然的双射，然后再证明它是同构映射。

假设g 是()Y X V ?到()F V 的映射。对任意给定的()Y V y ∈，映射

()y x g x g y ,:

是X F 的一个元，所以，映射

y g g y :Φ

是()Y X F 的一个元。那么映射g g Φ 就是()Y X F V ?到()()Y X F V 的双射。 设()Y X F V g f ?∈,且g f

~。若()Y V y y ∈21,且21~y y ，对任意()X V x x ∈21,，

21~x x ，有

()()2211,~,y x y x ，

而由g f ~，

()()2221,~,y x g y x f ，

那么

()()21~y y g f ΦΦ.

相似的，若g f

~不成立，那么g f ΦΦ~也不成立。因此，结论得

证。 推论6.4.3 对任意图X F ,和Y ，()()|F Y,Hom ||F Y,X Hom |X =?. 证明 由定理6.4.3知，()Y

X Y X F F ??，它们自然有相同数目的环，环的数目就是它们的同态映射的数目。

引理6.4.4 若X 至少有一条边，()X V 和()F V 的常值函数集导出了X F 的一个子图与F 同构.

证明 对任意给定的()F V y ∈，y f 是()X V 到()F V 的常值函数，即对任意x ∈()X V ，()y x f y =。那么{}F y y f ∈到()F V 有一个自然的双射。设

21~y y f f ，则若()()()21212121~,~,,x f x f x x X V x x y y ∈，即21~y y 。类似地，

若21~y y f f 不成立，则21~y y 不成立。所以F 与{}()X F y y F V f ?∈的导出

子图同构。

6.5 计数同态映射

通过计数同态映射，我们将会得到映射图的一些其他性质。 引理6.5.1 给定图X 和Y ，假设对所有图Z ，有

()()|Y Z,Hom ||X Z,Hom |=，

那么X 和Y 同构.

证明 用()B A Inj ,表示从图A 到B 的所有单同态构成的集合。我们要证明对所有图Z ，()()|Y Z,Inj ||X Z,Inj |=。令Z 分别为X 和Y ，那么有X 到Y 和Y 到X 的单同态。由于X 和Y 一定有相同的顶点数，那么单同态当然也是双射，因而X 与Y 同构。

我们对图Z 的顶点数进行归纳来证明()()|Y Z,Inj ||X Z,Inj |=。当Z 只有一个顶点时，这是显然的。

我们可以根据零元来划分图Z 到任意图W 的同态映射，所以

()()∑=π

π|,Z Inj ||W Z,Hom |W ，

一个同态映射是单的当且仅当它的零元是离散划分，用δ来标记它。所以

()()()∑≠=δ

ππ|,Z Inj |-|W Z,Hom ||W Z,Inj |Y .

现在，将W 分别替换为X 和Y ，由归纳假设，

()()∑∑≠

≠=δπδπππ|,||,Z Inj |Y Z Inj X ， 所以

()()|,||,|Y Z Inj X Z Inj =.

引理6.5.2 对任意图X F ,和Y ，Y X Y

X F F F ???. 证明 对任意图Z ，有

()

()()()()()()()()

()|F Z,Hom ||F Z,Hom ||

F Y,Z Hom ||F X,Z Hom ||,X Z Hom ||,Y X Z Hom ||F Z,Hom |Y X Y X ?=???=???=??=?F Y Z F 由推论6.3.2知，()()()

|F Z,Hom ||F Z,Hom ||F Z,Hom |X Y X

Y F ?=?，因此，Y X Y X F F F ???。

6.6 积和染色

回忆若Y X →，则()()Y X χχ≤，由于X 和Y 都是Y X ?的同态像，所以有()()(){}Y X Y X χχχ,min ≤?.S.Hedetniemi 已经猜想对于所有的图X 和Y ，()()(){}Y X Y X χχχ,min =?。

Hedetniemi 的猜想的等价论述是若图X 和图Y 都不是n 染色的，那么Y X ?也不是n 染色的。当2=n 时，我们可以通过证明两个奇圈的积仍包含奇圈来证明上面的论述。当3=n 时，El-Zahar 和Sauer 在1985年已经证明了。

定理6.6.1 假设()n X >χ.X n K 是n 可着色的当且仅当对于所有满足()n Y >χ的图Y ，()n Y X >?χ.

证明 由推论6.4.3，

()()

|,||,|X n X n n X n K K Hom K K X Hom =?, 所以X n K X ?是n 可着色的。那么，若()n X >χ并且只要()n Y >χ，()n Y X >?χ，X n K 一定是n 可着色的。

反过来设()n K X n <χ，Y 是满足()n Y >χ的图，那么Y 到任何n 可着色的图都没有同态映射，所以

()

()|,||,|0n X n K Y X Hom K Y Hom ?== 因此，()n Y X >?χ。

定理6.6.2 映射图1

+n K n K 是n 可着色的. 证明 我们构造1+n K n K 的一个n 染色φ。对任意1+∈n K n K f ，一定有两个不同的顶点j i ,使得()()j f i f =。定义()f φ是f 的值域中至少是两个顶点的像的最小值。若()()g f φφ=，那么对于某两个不同的顶点

i '和j '，有

()()()()j g i g j f i f '='==.

因为i 不可能同时等于i '和j '，所以g f

~不成立。因此φ是1+n K n K 的

正常的n 染色。 推论 6.6.3 假设图X 包含大小为1+n 的团，那么X n K 是n 可着色的.

证明 因为，由定理6.4.1，1+→n K n X n K K .由定理6.6.2，1+n K n K 是n 可着色的，所以X n K 也是n 可着色的。

定理 6.6.4 n

K n K 中所有的环都是孤立点.由没有环的顶点导出的n

K n K 的子图是n 可着色的. 证明 假设n

K n K f ∈且f 是n K 的正常的n 染色。若g 与f 相邻，那么对于()()()j f i g i K V j n ≠∈,\，所以，()()i f i g =。因此，f g =。 对于n

K n K 中无环的任一顶点f ，至少有两个不同的顶点j i ,使得()()j f i f =，所以我们可以像定理6.6.2中一样来定义n K n K 中无环的顶点的导出子图的正常的n 染色。

定理6.6.5 若X 是连通的且非n 可着色的，那么X n K 包含着唯一

的一个-n 团，即常值函数.

证明 由引理 6.4.4，在X n K 中由常值函数导出的子图是-n 团，我们只需证明这是唯一的-n 团。

若()n X >χ且f 是X 到n

K n K 的同态映射，那么，由定理6.6.4，f 一定将X 中的每个顶点映到n

K n K 中同一个环。由于n K 只有!n 个环，所以

()

|,|!n K n K X Hom n = ()|,|n n K X K Hom ?=

()|,|n n K K X Hom ?=

()|,|X n n K K Hom =.

所以，n K 到X n K 只有!n 个同态映射，所以X n K 包含着唯一的-n 团。

上面的证明说明若()n X >χ，那么从n K X ?到n K 只有!n 个同态映射。因此，n K X ?是唯一n 染色的。

定理6.6.6 假设2≥n ，X 和Y 是连通图且包含着一个-n 团.若X 和Y 都不是n 可着色的，那么Y X ?也不是n 可着色的.

证明 n x x ,,1 和n y y ,,1 分别是X 和Y 中的团。假设有X 和Y 到n K 的同态映射f ，考虑导出的Y 到X n K 的同态映射。由定理6.6.5，

n y y ,,1 在X n K 中的像包含常值映射。或者说，()i y x f ,作为x 的一个函数，对于每个i y 都是固定的。类似的可证明()y x f i ,作为y 的函数对每个i x 也是固定的。那么()()()222111,,,y x f y x f y x f ==。所以，相

邻的两个顶点()11,y x 和()22,y x 被映到n K 的同一个顶点，与f 是同态映射矛盾。

上述定理的一个结论是若X 和Y 都不是偶图，那么Y X ?也不是偶图。

推论 6.6.7 图X 的每个顶点都在一个-n 团中且()n Y >χ，那么()n Y X >?χ.

证明 假设有Y X ?到n K 的同态映射f 。考虑导出的从X 到Y n K 的

映射f Φ。因为Y n K 没有环，X 的每个-n 团都被一一地映到Y n K 中唯一的团上。X 的每个顶点都在一个-n 团中，所以X 的每个顶点被映到这个-n 团。所以，f Φ是X 到n K 的同态映射，这与()n X >χ矛盾。

6.7 唯一染色图

若图X 的色数为n ，那么X 的每个n 染色都将X 的顶点集划分成n 个独立集；反过来，每个将()X V 划分成n 个独立集的分类实际上给出了!n 个正常的n 染色。我们称一个图是唯一n 染色的，如果它的色数为n ，并且将它的点集分为n 个独立集的分类只有一种。不难看出如果图X 至少有n 个顶点，那么它是唯一n 染色的当且仅当从X 到n K 只有!n 个同态映射。最简单的例子就是至少有一条边的连通二部图是唯一2染色的。

关于唯一染色图有很多与Hedetniemi 猜想有关的猜想。这些猜想源于下面的结果，在定理6.6.5的证明中已经陈述过。 定理6.7.1 若X 是连通图并且()n X >χ，那么n K X ?是唯一n 染色的.

引理6.7.2 若X 是唯一n 染色的，那么X 的每个正常的n 染色都是X n K 的孤立点.

证明 设f 是X 的正常的n 染色且()X V x ∈。由于X 是唯一n 染色的，除了()x f 的其他1-n 种颜色一定在x 的某个邻点上表现。所以若f g ~，那么()()x f x g =，则X n K 中与f 相邻的顶点只有f 自身。

用()X n K λ标记X n K 中无环的顶点集的导出子图。我们可以列出

下面的猜想：

()n B 若X 是唯一n 染色的并且Y 是非n 可着色的连通图，那么Y X ?是唯一n 染色的。

()n D 若X 是唯一n 染色的，那么()X n K λ是n 可着色的。 ()n H 若()()1+==n Y X χχ，那么()1+=?n Y X λ。

猜想()n H 对于所有的正整数n 成立与Hedetniemi 的猜想等价。我们将要证明()()()n n n H D B ??。

假设()n B 成立，X 是唯一n 染色的。若Y 是()X n K λ的任意子图，

那么Y 到X n K 的同态映射有多于!n 个（对于!n 个环中的每个环，都相应的存在一个同态映射，还有恒等映射），所以，

()()

1!|,||,|+≥=?n K Y Hom K Y X Hom X n n . 这说明Y X ?不是唯一n 染色的，由()n B ，()n Y ≤χ。所以，()n B 蕴含()n D 。

但()n D 也蕴含()n B 。因为若Y 是连通的，()n Y >χ且()X n K λ是n 可着色的，那么Y 到X n K 的同态映射只能是映到环的映射。所以，

()

()|,||,|!n X n K Y X Hom K Y Hom n ?== 那么，Y X ?是唯一n 染色的。

我们将用下面的引理来证明()n D 蕴含()n H 。

引理6.7.3 若()n X >χ，那么存在X n K 到()X n K λ的同态映射.

证明 X P 是n K X ?到X 的投影映射，?是导出的从X n K 到n K X n K ?的同态映射。若X n K g ∈，那么g 不是X 得正常的n 染色，所以存在

()X V v u ∈,，使得()()v g u g =。现在，()X P g g =?，因此，对()n K V j i ∈?,，

()g ?将()i u ,和()j v ,映到()u g 。所以()g ?不是n K X ?得正常的染色，这

说明它不是环。

现在假设()n D 成立并且设图X 满足()n X >χ。由定理6.7.1，n K X ?是唯一n 染色的，所以()n D 蕴含()X n K λ是n 可着色的。因此，

由引理6.7.3，X n K 是n 可着色的。那么，

()()0|,||,|==?X n n K Y Hom K Y X Hom .

因此，Hedetniemi 的猜想成立。

6.8 折叠和覆盖

我们将X 到Y 的同态映射称为单折叠，如果它有一个纤维包含距离为2的两个顶点，并且其他纤维都是单点集。比如，三个顶点的路到2K 的两个同态映射是单折叠。若一个同态映射是某些

单折叠的合成，那么这个同态映射称为折叠。

引理6.8.1 若f 是连通图X 到它的真子图Y 的收缩，那么f 是折叠.

证明 我们对()X V 的大小作数学归纳。假设f 是X 到Y 的收缩，即f 是X 到Y 的同态映射且Y f |是恒等映射。因为X 是连通的，所以一定存在()Y V y ∈和()()Y V X V x \∈相邻。现在，f 固定y 且将x 映到y 在Y 中的邻点z 。

设π是()X V 的一个分类，{}z x ,是其中的一个元且其他元都是单点集。X 到1X X =π有一个自然的同态映射1f 。

由于1f 的零是f 的零的一个加细，有从1X 到Y 的同态映射2f 满足f f f =12 。因为1f 将

Y 的每个顶点都映到它自身，

所以Y 是1X 的一个子图，且2f 是1X 到

Y 的一个收缩。最后，1f 是单折叠且由假设2f 是折叠，所以f 是折叠。

我们称一个同态映射为局部单映射，如果同一个纤维中的两点的最短距离至少是3.当然，任何自同构都是局部单映射。 引理 6.8.2 图X 到图Y 的每个同态映射都可以表示为f 和g 的合成g f ，其中f 是局部单映射，g 是折叠.

证明 设π是h 的零。如果v u ,是X 的顶点，用v u ≈表示u 和v 在π的同一元中并且要么相等要么在X 中的距离为2。这是()X V 的一个反身的，对称的关系。因此它的传递关闭是一个等价关系，这决定了()X V 的一个分类π'。自然地存在一个X 到π'X 的同态映射g 及从π'X 到Y 的同态映射f 满足g f h =。

显然地，g 是折叠。我们下面证明f 是一个局部单映射。若不然，设βα，是π'X 中距离为2且满足()()βαf f =的顶点。设γ是βα，在π'X 中公共的邻点。那么，一定存在()α1-∈g u 与()γ1-∈'g u 相邻且存在()β1-∈g v 与()γ1-∈'g v 相邻。但是v u '',由X 中一条长为偶数的路相连，因此对v u ,也成立。这说明v u ,一定在π'的同一元中，与v u ,的选取矛盾。

X 到Y 的同态映射f 称为局部同构，如果对Y 中的每个顶点y ，导出的从()y f 1-中的一个顶点的邻点集到y 的邻点集的映射是双射。我们称f 为覆盖映射如果它是满的局部同构，在这种情况下，称X 覆盖了Y 。如果f 是局部同构，那么它的每个纤维都是X 的独立集，且每个纤维之间要么没有边要么有一个匹配。若X 的

像是连通的，那么每个纤维的大小相同。这个数目称为覆盖的指标γ，并且X 称为Y 的-γ折叠覆盖。从图X 到图Y 的覆盖映射可能不止一个，所以我们总是用()f X ,来定义Y 的一个覆盖图，其中f 是X 到Y 的局部同构。

若()f X ,是Y 的一个覆盖并且1Y 是Y 的一个导出子图，那么

()11Y f -覆盖1Y 。

这说明关于Y 的覆盖的问题可以分解为它的连通分支的覆盖的问题。若Y 是连通图且()f X ,是Y 的一个覆盖，那么X 的每个连通分支都覆盖了Y 。

引理6.8.3 如果X 覆盖Y 并且Y 是树，那么X 是同构于Y 的连通分支的不相交的并.

证明 设f 是X 到Y 的覆盖映射。因为f 是局部同构，若()X V x ∈，那么()()()x d x f d X Y =。这说明X 的任意圈的像在Y 中也是圈，因此X 的围长不可能比Y 的围长小，而Y 是不含圈的，所以X 也是。

若()y x f =，那么连接y 的每条边是连接x 的边在f 下的像。那么，Y 中由y 开始的每条路也是由X 中由x 开始的路在f 下的像。所以，在X 中存在一棵树T 使f 是T 到Y 的同构映射。因此，Y 是X 的一个收缩。由于X 的每个连通分支都覆盖了Y ，由引理

6.8.1知，Y 与X 的每个连通分支同构。

我们称Y 的指数为γ的覆盖()f X ,是平凡的，如果X 同构于γ个不相邻的Y 的并，而且f 的限制到每个Y 都是同构映射。由引理6.8.3知，树的任意覆盖都是平凡的。

立方体Q 有一个性质：对于每个顶点x ，在Q 中存在唯一的

一个顶点与x的距离为3。所以()Q

V可以分成四对，这些点对就是Q到4K的覆盖映射的纤维。

类似的，十二面体覆盖了Petersen图，Petersen图的线图覆盖了

K。Hoffman-Singleton图中与一个固定点距离为2的42 5

个点是

K的6-折叠覆盖。

7

如果()f

Y,都是F的覆盖，那么它们的子直积也是。

X,和()g

6.9 无三角形的核

尽管我们在6.2节中证明了每个图都有一个核，但举出核的例子仍是非平凡的。临界图提供了这样的一类图。由于任何同态映射都将三角形映成三角形，所以构造包含许多三角形核的图相对比较容易。在这部分，我们构造不包含三角形的核。

引理6.9.1 X是一个连通的非二部图，如果每个arc

2都在X的

-

一个最短的奇圈中，那么X是核.

证明f是X到X的同态映射，所以f将X的最短奇圈映到相同长度的奇圈，圈上任何两个顶点在f下的像是不同的。因为每个-

2都在一个最短的奇圈上，这说明f是一个局部单同态，因arc

此，由引理6.8.1，f不可能将X映到它的真子图上。

如果图X的两个顶点v

u,有相同的邻点集，那么X一定不是

核，因为有X到u

X\的收缩。一个图称为是简化的，如果它没有

孤立点并且不同的顶点的邻点集是不同的。

现在，假设X不包含三角形。如果v

u,是X中距离至少为3

的两个顶点，那么通过加一条边uv仍不包含三角形。继续这个过

程，可以看到任意无三角形的图X 都是一个直径为2的无三角形图的生成子图。

引理6.9.2 X 是简化的直径为2的不包含三角形图.对任意一对不相邻的顶点v u ,，存在一个顶点与u 相邻但不与v 相邻. 证明 若不然，假设()()v N u N ?。因为X 是简化的，存在一个顶点w 与v 相邻但不与u 相邻。由于X 不包含三角形，w 不和u 的任何邻点相邻，所以u 和w 的距离至少是3.

引理6.9.3 X 是不包含三角形的图且直径为2，那么X 是核当且仅当它是简化的.

证明 显然，若X 不是简化的，X 不是核。现在假设X 是简化的，我们下面证明每个arc -2在X 的5-圈中，这样由引理6.9.1，结论就得证。

设()w v u ,,是arc -2，w 是与u 距离为2的顶点。因为()w N 不包含()u N ，一定有w 的一个邻点w '与u 距离为2。现在，w '一定有一个邻点v '与u 相邻。由于X 没有三角形，v v ≠'，所以()v w w v u '',,,,是一个5-圈。

6.10 Andrasfai 图

我们定义一族Cayley 图()k And ,它们中的每一个都是简化的直

径为2的不包含三角形的图。对任意整数1≥k ，令13-=k Z G ，

C 是13-k Z 中模3余1的元的集合。现在我们用()k And 标记Cayley 图()C G X ,。()2And 与5-圈同构，()3And 是bius o

M 带。 引理6.10.1 对于2≥k ，Cayley 图()k And 是简化的直径为2的不

环的同态与反同态(大学优秀论文)

齐齐哈尔大学 毕业（设计）论文 题目环的同态与反同态 学院理学院 专业班级数学与应用数学专业062班 学生姓名赵娜 指导教师李立 成绩 2010年 6 月 16 日

摘要 环的同态与反同态在代数学中具有非常重要的地位, 因此研究环的同态与反同态是尤为重要的. 本文主要从环的同态的性质、环的反同态的性质、环的同态与反同态的应用三个方面研究了环的同态与反同态. 通过利用环的同态的一些基本性质诱导出环的反同态所具有的性质, 给出了环的反同态的性质. 这些反同态性质有些是环的同态所具有的, 还有些是同态所不具有的, 这些性质为以后研究反同构问题提供了有利条件. 本文重点研究了无零因子环的幂自同态、有限交换幺环的自同态以及矩阵上的反自同态与反自同构, 还有商环的结构以及在此基础上又研究了反商环的结构, 展现了环的同态与反同态的鲜明对比. 最后研究了同态与反同态在向量空间中和在证明商环同构等问题中的应用, 体现了环的同态与反同态的广泛应用, 从而反映了研究环的同态与反同态的重要性. 关键词：环；同态；反同态；无零因子环；商环

Abstract The problems of the homomorphism and the anti-homomorphism are very important positions in algebra. It is particularly important to study the homomorphism and the anti-homomorphism. This article mainly studies the homomorphism and the anti-homomorphism of ring from the three aspects whice are the homomorphism properties, the anti-homomorphism properties and the application of the homomorphism and the anti-homomorphism. This article induces the anti-homomorphism with the properties through reference some basic properties of the homomorphism. Moreover, I give the properties through the anti-homomorphism of ring. In these properties, some belong to the homomorphism, but some do not. These properties provide favorable conditions for the research on the isomorphism in future. This paper mainly studies power endomorphism of no zero factor ring, endomorphism of finite commutative unitary ring and matrix anti-endomorphism and anti-automorphism, the structure quotient ring also, and on this basis. I study the structure of anti-quotient ring, shows a sharp contrast of the homomorphism and the anti-homomorphism. Finally, I study the application of the homomorphism and anti-homomorphism in vector space and the problem of proofing quotient ring isomorphism. It reflects the widely applied of the homomorphism and the anti-homomorrphism, Thus those reflects the importance of studying the homomorphism and the anti-homomorphism. Key words: Ring; Homomorphism; Anti-homomorphism; No zero factor ring; Quo-tient ring

S3,S4的自同态和自同构(近世代数)

题目：S3，S4的自同态和自同构学院：数学与统计学院 专业：数学与应用数学 姓名： 学号： 指导教师： 时间： 2012年6月17日

摘要 本文讨论了三次对称群S3和四次对称群S4各自所拥有的子群，以及找出S3，S4各自的自同态，自同构，检验各自的子群在自同态和自同构下是否保持不变。 关键词: 对称群，子群，不变子群，自同态，自同构。 一、S 4和S 4 的子群：

假如对于代数运算 和 来说，有一个A到A的同态映射存在，我们就说，这个映射是一个同态满射，并说，对于代数运算 和 来说，A与A同态。 假如对于代数运算 和 来说，有一个A到A的同构映射存在，我们就说，对于代数运算 和 来说，A与A同构。 S 3 ={(1),(12),(13),(23),（123），（132）}， S 4 ={(1)， (12),(34),(13),(24)，（14），(23)， (123),(132),(134),(143),(124),(142),(234),(243), (1234),(1243),(1324),(1342),(1423),(1432), (12)(34),(13)(24),(14)(23)}. 其中,在S 3 里，(1)、(12) 、(13) 、(23)的逆元就是它们自己本身, （123）与（132）互为逆元。 在S 4 里，(1) 、(12) 、(34) 、(13) 、(24) 、（14）、(23) 、(12)(34) 、(13)(24) 、(14)(23) 的逆元就是它们自己本身，（123）与（132）互为逆元，(134)与(143)互为逆元, (124)与(142) 互为逆元，(234)与(243) 互为逆元，(1234)与(1432) 互为逆元，(1243)与(1342) 互为逆元，(1324)与(1423) 互为逆元。 S 3的子群有H 1 ={（1）}， H 2 ={（1），（12）}， H 3 ={（1），（13）}， H 4 ={（1），（23）} ， H 5 ={（1），（123），（132）}， H 6=S 3 。 其中H 1和H 6 为S 3 的平凡子群。