离散数学 课件 第6、7章 代数系统、图

第6章 代数系统第一节代数运算第二节 代数系统的一般概念第三节 同态和同构第四节 同余关系第五节 商代数和积代数第六节 典型的代数系统第一节代数运算一、基本概念二、二元运算的性质三、二元运算中的特异元素一、基本概念1、二元运算2、n元运算3、二元运算的封闭性1、二元运算X:集合f:X2→X的映射f为X中的二元运算解释：一个运算符联系着两个运算分量f(<x,y>)=z 运算符运算分量运算分量运算结果xfy=zx,y,z∈Xz∈X封闭性2、n元运算X:集合f:Xn→X的映射f为X中的n元运算运算的阶<x1,x2,…,xn>f=xx1,x2,…,xn,x

X2、二元运算的封闭性注意：任意一个二元运算必须满足封闭性A:集合f:A2→B的映射B

A二元运算是封闭的二元运算举例设A={x|x=2n,nN}问：乘法运算是否封闭？对加法运算呢？乘法运算：对于任意的2r

、2sA2r

2s=2r+sA∴乘法运算在A上封闭；加法运算：21+22=6

A∴加法运算在A上不封闭；举例判断乘法运算是否在下列各N的子集上封闭？(1)A1={0,1}(2)A2={1,2}(3)A3={x|x为素数}(4)A4={x|x为偶数}(5)A5={x|x为奇数}√×√√×2

2=4A22

3=6A3定理*:X中的二元运算S1

XS2

X*在S1和S2上是封闭的*在S1∩S2上也封闭证明对任意的两个元素x,y

S1∩S2

x,y

S1∧x,y

S2*在S1和S2上封闭

x*y

S1∧x*y

S2

x*y

S1∩S2

*在S1∩S2上也封闭二、二元运算的性质1、封闭性（通性）2、交换性3、可结合性4、可分配性5、吸收律1、封闭性（通性）*:X中的二元运算对于任意的x,y∈Xx*y∈X在集合X上满足封闭性2、交换性*:X中的二元运算对于任意的x,y∈Xx*y=y*x*运算是可交换的3、可结合性*:X中的二元运算对于任意的x,y,z∈Xx*y*z=x*(y*z)=(x*y)*z*运算是可结合的二元运算性质举例

设Q是有理数集合，Q上的二元运算定义为：

a*b=a+b-ab a,b∈Q问*是否可交换？可结合？解答(1)交换性：b*a=b+a-ba=a+b-ab=a*b∴*运算满足交换律(2)结合性：a*(b*c)=a*(b+c-bc)=a+(b+c-bc)-a(b+c-bc)=a+b+c-ab-ac-bc+abc(a*b)*c=(a+b-ab)*c=(a+b-ab)+c-(a+b-ab)c=a+b+c-ab-ac-bc+abc=a*(b*c)∴*运算满足结合律解答二元运算性质举例 A是非空集合，*是A上的二元运算，并定义为：a*b=b,证明*是可结合的。a*(b*c)*是可结合的(a*b)*c=c=a*c=b*c=c4、可分配性*,△

:X中的二元运算对于任意的x,y,z∈Xx*(y△z)=(x*y)△(x*z)(y△z)*x=(y*x)△(z*x)*对△可分配5、吸收律*,△

:X中的可交换的二元运算对于任意的x,y∈Xx*(x△y)=x△(x*y)=xx*和△满足吸收律二元运算性质举例

在N上定义两个二元运算*和△，对任意的x,y∈N，有：

x*y=max(x,y)x△y=min(x,y)验证：*和△满足吸收律。解答x*(x△y)=x*(min(x,y))=max(x,min(x,y))=x>yx=yx<ymax(x,y)=max(x,x)=max(x,x)=xxxx△(x*y)=x△(max(x,y))=min(x,max(x,y))=x>yx=yx<ymin(x,x)=xmin(x,x)=xmin(x,y)=x*和△满足吸收律三、二元运算中的特异元素1、幺元e（左幺元el

、右幺元er

）2、零元θ（左零元θl

、右零元θr

）3、逆元（左逆元xl

、右逆元xr

）4、等幂元5、可约的（可消去的）6、由运算表求特异元素1、幺元e（左幺元el

、右幺元er

）*

:X中的二元运算(

x)(→)x∈X(

el

)(∧)el∈Xel*x=x左幺元(

x)(→)x∈X(

er

)(∧)er∈Xx*er=x右幺元定理*

:X中的二元运算如果X对运算*同时存在el和erel=er=e(

x)(→)x∈X(

e)(∧)e∈Xx*e=xe*x=幺元单位元素e若存在则必唯一证明(1)el=er=ex*e=e*x=xel*er

el是*的左幺元=erer是*的右幺元=el=ex*e=e*x=xx∴e是*唯一的幺元(2)幺元是唯一的证明(续)假设e′是*的另一个幺元e≠e′e*e′=ee*e′=e′e′是幺元e是幺元e=e′幺元举例

问实数集合R上的加法运算和乘法运算的幺元各是什么？实数集合R上的加法运算：幺元是0实数集合R上的乘法运算：幺元是12、零元θ（左零元θl

、右零元θr

）*

:X中的二元运算(

x)(→)x∈X(

θl

)(∧)θl∈Xθl*x=θl左零元(

x)(→)x∈X(

θr

)(∧)θr∈Xx*θr=θr右零元定理*

:X中的二元运算如果X对运算*同时存在θl和θrθl=θr=θ(

x)(→)x∈X(

θ)(∧)θ∈Xx*θ=θθ*x=零元θ若存在则必唯一零元举例

问实数集合R上的加法运算和乘法运算的零元各是什么？实数集合R上的加法运算：实数集合R上的乘法运算：无零元零元是03、逆元（左逆元xl

、右逆元xr

）*

:X中的二元运算*运算存在幺元ex∈X(

xl)(∧)xl

∈Xexl

*x=x的左逆元左可逆的(

xr)(∧)xr

∈Xex*xr

=x的右逆元右可逆的x是左可逆的x是右可逆的x是可逆的定理*

:X中的二元运算*运算存在幺元e*运算可结合元素x∈X是可逆的xl=xr=x-1x的逆元x-1若存在则必唯一证明(1)左逆元等于右逆元xl*x*xr*是可结合的=(xl*x)*xrxl*x=e=e*xr=xrxl*x*xr*是可结合的=xl*(x*xr)x*xr=e

=xl*e=xlxl=xr证明(2)xl=xr=x-1唯一幺元e的逆元是其本身，零元不可逆假设x1-1和x2-1是x的两个逆元x1-1

≠x2-1x1-1

=x1-1*ex2-1是x的逆元=x1-1*(x*x2-1)*是可结合的=(x1-1*x)*x2-1x1-1是x的逆元=e*x2-1=x2-1举例 (1)实数集合R上的加法运算：求每个实数的逆元

(2)实数集合R上的乘法运算：求每个实数的逆元解答实数集合R上的加法运算无零元e=0x+(-x)=0=ex-1=-x实数集合R上的乘运算e=1θ＝0x

1/x=1=ex-1=1/xx≠04、等幂元x*x幺元和零元都是等幂元*

:X中的二元运算x∈X=x等幂元5、可约的*

:X中的二元运算a∈X对每一个x,y∈X(a*x=a*y)

x=y或者(x*a=y*a)

x=y可约的可消去的定理*

:X中的二元运算*运算可结合a∈Xa是可逆的a是可约的证明a*x=a*yx=ya是可逆的,a的逆元为a-1a-1*(a*x)*是可结合的=(a-1*a)*x=e*x=xa-1*(a*x)a*x=a*y=a-1*(a*y)*是可结合的=(a-1*a)*y=e*y=yx=ya是可约的6、由运算表求特异元素左幺元:右幺元:某一个元素使得某一行不改变；某一个元素使得某一列不改变；左零元:右零元:某一个元素使得某一行均为该元素；某一个元素使得某一列均为该元素；逆元:幺元所对应的元素互为逆元；等幂元:只考虑主对角线上的元素举例

已知二元运算∆、⊕的运算表，求各运算的特异元素。

解答(1)第1行没改变，所以α为左幺元；第1列没改变，所以α为右幺元；∴

α为幺元(2)无左、右零元；(3)α-1＝α;β-1＝β;γ-1＝γ;(4)α为等幂元。解答(1)第1行没改变，所以α为左幺元；第1列没改变，所以α为右幺元；∴

α为幺元(2)无左、右零元；(3)α-1＝α;β-1＝γ;γ-1＝β;δ-1

＝ε;ε-1=δ;(4)α、δ为等幂元。举例I:整数集合g:I×I→I，且：

g<x,y>=x*y=x+y-xy求出幺元，并指出每个元素的逆元。解答(1)求幺元e：对任意的x∈Ix*y=x+y-xyx*e=x+e-xe幺元的定义=xe=0解答(2)求x的逆元x-1

：x*x-1x*y=x+y-xy=x+x-1-xx-1=0x-1=x/(x-1)∈Ix=0时：x=2时：x-1=0∈Ix-1=2∈I第二节 代数系统的一般概念1、代数系统的定义2、代数系统满足的条件3、子代数系统4、同类型的代数系统1、代数系统的定义X:非空集合Ω:X上运算的非空集合V=<X,Ω>:代数系统{ω1，ω2，…，ωn}<X,ω1，ω2，…，ωn>有限代数系统|X|为V的阶解释：一个非空集合X,连同若干个定义在该集合上的运算ω1，ω2，…，ωn所组成的系统称为代数系统。2、代数系统满足的条件（1）非空集合X；（2）有一些建立在集合X上的运算；（3）这些运算在集合X上是封闭的。代数系统举例<I+，+><ρ(S)，∪，∩>是是代数系统举例N4={0，1，2，3},i+4j=(i+j)(mod4)问：<N4

，+4>是代数系统吗？+401230123验证+4在N4集合上是否满足封闭性0123123023013012由运算表可知运算满足封闭性<N4

，+4>是代数系统3、子代数系统V=<S，Ω>:代数系统S′≠φS′

S每一个运算ω∈Ω在S′上均封闭V′=<S′，Ω>是一个代数系统V′为V的子代数系统子系统或子代数子代数系统举例<I,+>是一个代数系统设E：偶数集合则：<E,+>是<I,+>的子代数系统。4、同类型的代数系统V1=<S1，Ω1>:代数系统V2=<S2，Ω2>:代数系统存在一个双射函数f:Ω1→Ω2每一个ω∈Ω1和f(ω)∈Ω2具有相同的阶同元运算V1和V2是同类型的代数系统类型映射ωf同类型的代数系统举例V1=<Nm,+m,

m>和V2=<R,+,

>是同类型的代数系统吗？其中：i+mj=(i+j)(modm)i

mj=(i

j)(modm)解答双射函数（类型映射）f:f(+m)=+,f(

m)=

且+m和+、

m和

均为二元运算所以：V1=<Nm,+m,

m>和V2=<R,+,

>是同类型的代数系统。同类型的代数系统举例V1=<Nm,+m>和V2=<I,+,

>是同类型的代数系统吗？V1=<I,+，-

>和V2=<R,+,

>是同类型的代数系统吗？其中：“-”为取负运算。（不是）（不是）不存在双射函数不是同元运算不是同元运算第三节 同态和同构一、同态二、同构一、同态1、同态的定义2、同态的特点3、满同态、单一同态、自同态1、同态的定义<A，∘><B，*>同类型的代数系统A上的二元运算B上的二元运算存在一个映射g：A→B对任意的a,b∈Ag(a∘b)=g(a)g(b)*运算的象象的运算从<A，∘>到<B，*>的一个同态映射<A，∘>与<B，*>同态解释两个代数系统同态：（1）两个代数系统同类型；（2）运算的象=象的运算2、同态的特点（1）g映射可以是内射、单射、满射、双射；（2）g(S1)

S2

像点集单一同态满同态同构同态示意图S1x1x2x3S2gg(x1)=y1g(x2)=y1g(x3)=y3y1y3g(x1∘x3)=g(x1)*g(x3)=x1∘x3y1*y3y1*y3g(x2∘x3)=g(x2)*g(x3)=y1*y3x2∘x3g(S1)同态举例其中：g:N→{0,1}，且定义为：g(n)=0(n

N)证明：<N，×><{0，1}，×>同态证明（1）显然<N,×>与<{0,1},×>同类型；（2）运算的象=象的运算对任意的m,n

N运算的象=g(m×n)=0象的运算=g(m)×g(n)=0×0=0所以：<N，×>与<{0，1}，×>同态3、满同态、单一同态、自同态(1)如果g为满射函数，则称g为关于类型映射f的满同态；(2)如果g为单射函数，则称g为关于类型映射f的单一同态；(3)若V1=V2，且类型映射f为恒等函数，则称g为关于类型映射f的自同态。自同态举例其中：g:I→I，且定义为：g(n)=3n(n

I)证明：<I，+><I，+>自同态证明(1)显然<I，+>与<I，+>同类型,且f(+)=+；(2)运算的象=象的运算对任意的m,n

N运算的象=g(m+n)=3(m+n)=3m+3n=g(m)+g(n)=象的运算所以：<I，+>与<I，+>同态,且是自同态。满同态的特点满同态对性质的保持是单方向的，即： <X,∘>与<Y,*>满同态<X,∘>的性质，<Y,*>均保持交换律结合律分配律吸收律幺元零元逆元等幂元交换律、结合律设<X,∘>与<Y,*>满同态，则：（1）若∘运算可交换，则*运算也可交换；（2）若∘运算可结合，则*运算也可结合；分配律V1=<S1，Ω1>V2=<S2，Ω2>满同态f:类型映射*

Ω1∆

Ω1*对∆可分配f(*)对f(∆)也可分配

Ω2幺元、零元、逆元设<X,∘>与<Y,*>满同态，则：(1)若∘有幺元e，则*有幺元g(e);(2)若∘有零元

，则*有零元g(

);(3)若xX有逆元x-1,则g(x)Y有逆元g(x-1)满同态的特点举例<I,+,

>和<N3,+3,

3>满同态，则：(1)＋可交换，f(＋)=+3也可交换；(2)

可交换，f(

)=

3也可交换；(3)＋可结合，则f(+)＝+3也可结合；(4)

可结合，则f(

)＝

3也可结合；满同态举例（续）(5)对“＋”存在e=0,则:对“+3”存在e=g(0)=0;(6)对“

”存在e=1,则:对“

3”存在e=g(1)=1;(7)对“

”存在零元

=0,则:对“

3”存在零元=g(0)=0;(8)对“＋”，8的逆元是-8,则:对“+3”g(8)=2g(-8)=g(-9+1)=(-9+1)(mod3)=1(mod3)=1满同态举例（续）2+31=(2+1)(mod3)=0=e2和1互为逆元单一同态举例证明：<R，＋><R，

>单一同态实数集合g:R→R对于xRg(x)=2x证明(1)显然<R,+>和<R,

>同类型(2)运算的象=象的运算对于任意的x,y

R，有：g(x+y)=2x+y=2x

2y=g(x)

g(y)(3)g映射是单射函数y=2x二、同构1、同构的定义2、同构的特点3、自同构1、同构的定义<A，∘><B，*>同类型的代数系统A上的二元运算B上的二元运算存在一个双射映射g：A→B对任意的a,b∈Ag(a∘b)=g(a)g(b)*运算的象象的运算从<A，∘>到<B，*>的一个同构映射<A，∘>与<B，*>同构同构满足的条件（1）同类型（2）g为双射函数（|S1|＝|S2|）（3）运算的象＝象的运算同构举例S={a,b,c,d},运算∘见表(a)P={1,2,3,4},运算*见表(b)则<S,∘>与<P,*>同构。∘abcdadabdbdbcdcadccdabaa表(a)*123412224211423323141134表(b)解答（1）显然<S,∘>与<P,*>同类型；（2）寻找双射函数g：S→P由表(a)的第4行和表(b)的第1行可知：g(a)=2,g(b)=4在<S,∘>中c是等幂元在<P,*>中3是等幂元g(c)=3g(a)=2,g(b)=4,g(c)=3,g(d)=1变换运算表g1,2列交换2,4列交换1,2行交换2,4行交换一致2、同构的特点（1）g为双射函数；（2）g(X)=YS1x1x2S2gx1∘x2g(x1)*g(x1)g(x1)g(x2)同构对运算保持相同的性质设<X,∘>与<Y,*>同构，则：(1)若∘有幺元e,则*有幺元g(e),反之亦然；(2)若∘有零元

,则*有零元g(

),反之亦然；(3)若xX有逆元x-1,则g(x)Y有逆元g(x-1),反之亦然；(4)若∘运算可交换,则*运算也可交换,反之亦然；(5)若∘运算可结合,则*运算也可结合,反之亦然；3、自同构

若V1=V2，且类型映射f为恒等函数，则称g为关于类型映射f的自同构。同构举例证明：<R+,

><R,+>同构给定：g:R+→R,g(x)=lnx证明(1)显然<R+,

>和<R,+>同类型；(2)g(x)=lnx是双射函数；(3)运算的象＝象的运算:对于任意的a,b

R+g(a

b)=ln(a

b)=lna+lnb=g(a)+g(b)所以：<R+,

>和<R,+>同构。第三节 同余关系一、代换性质二、同余关系一、代换性质V=<G,Ω>:代数系统R:G上的等价关系ω

Ω:n元运算对任意的a1,b1,a2,b2,…,an,bn

Ga1Rb1a2Rb2…anRbn(<a1,a2,…,an>)ω(<b1,b2,…,bn>)ωRR关于ω具有代换性质代换性质举例 <I,+,

>为代数系统，I中的等价关系如下：对任意的a,b

I，aRb|a|=|b|问：等价关系R对于运算＋和是否具有代换性质？

解答（1）对加法运算“＋”：设a、-a、b

I∵|a|=|-a|aR(-a)∵|b|=|b|bRb|a+b|≠|-a+b|(a+b)(-a+b)R关于“＋”不具有代换性质解答（续）（2）对乘法运算“×

”：设i1、i2、j1、j2

I若i1Ri2

则|i1|=|i2|若j1Rj2

则|j1|=|j2|∴|i1×j1|=|i2×j2|

∴(i1×j1)R(i2×j2)即：对于乘法运算“×”来说，R具有代换性质。二、同余关系V=<G,Ω>:代数系统R:G上的等价关系R关于每一个运算ω

Ω都具有代换性质R为<G,Ω>上的同余关系。同余关系举例 <N,+>为代数系统，在N上定义一个模m同余关系≡m

证明：≡m关于＋具有代换性质，且是<N,+>上的同余关系证明x1,y1,x2,y2

Nx1≡my1x2≡my2(x1+x2)≡m(y1+y2)x1≡my1x1=p1m+r1y1=p2m+r1x2≡my2x2=q1m+r2y2=q2m+r2p1,p2,q1,q2,r1,r2

N0≤r1

、r2≤m-1x1+x2=p1m+r1+q1m+r2=(p1+q1)m+(r1+r2)y1+y2=p2m+r1+q2m+r2=(p2+q2)m+(r1+r2)(x1+x2)≡m(y1+y2)≡m是同余关系第五节 商代数和积代数一、商代数二、积代数一、商代数1、商代数的定义2、正则映射1、商代数的定义R:代数系统V=<X,∘>上的同余关系<X/R,⊗>:V=<X,∘>关于R的商代数V/R(1)对于x1,x2

X[x1]R[x2]R=⊗[x1∘x2]R(2)X/R={[x]R|x

X}商集二、积代数A1=<G1,*>A2=<G2,⊕>同类型的代数系统A1×A2=

<G1×G2,∆>:A1与A2的积代数∆定义为：对任意的<a1,b1>,<a2,b2>

G1×G2<a1,b1>∆<a2,b2>=<a1*a2,b1⊕b2>A1,A2:A1×A2的因子代数积代数举例F2=<N2,+2,×2>F3=<N3,+3,×3>求：F2×F3解答N2={0,1}N3={0,1,2}则：N2×N3={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>}设：F2×F3=<N2×N3,+23,×23>+23、×23的运算表<0,2>+23<1,0>=<0+21,2+3

0

>=<1,2

><0,2>×23<1,0>=<0×21,2×3

0

>=<0,0

>第六节 典型的代数系统一、半群二、群一、半群1、半群2、可交换半群3、独异点（含幺半群）4、可交换含幺半群5、子半群6、循环半群1、半群<S,*>:代数系统*:二元运算*运算是可结合<S,*>:半群2、可交换半群<S,*>:半群*运算是可交换<S,*>:可交换半群3、独异点（含幺半群）<S,*>:半群*运算有幺元e<S,*>:含幺半群独异点<S,*,e>4、可交换含幺半群<S,*>:独异点*运算是可交换S,*>:可交换含幺半群半群举例

下列各代数系统是否为半群？若是半群，是什么半群？(1)<N,+>(2)<N,×>(3)<ρ(S),∩>，其中S为非空集合。(4)<ρ(S),∪>其中S为非空集合。半群可交换半群含幺半群e=0可交换含幺半群半群可交换半群含幺半群e=1可交换含幺半群半群可交换半群含幺半群e=S可交换含幺半群半群可交换半群含幺半群e=φ可交换含幺半群半群举例I:整数集合，对于下列*运算，哪些代数系统<I,*>是半群?⑴a*b=ab⑵a*b=a解答⑴对任意的a,b,cI

(a*b)*c=ab*c=(ab)c=abc，a*(b*c)=a*bc=

，不是半群所以(a*b)*c≠a*(b*c)。解答:a*b=a⑵*的封闭性是显然的;(a*b)*c=a*c=a,a*(b*c)=a*b=a，*是可结合运算是半群5、子半群<S,*>:半群H

S集合H在运算*作用下封闭<H,*>是<S,*>的子半群<S,*,e>:含幺半群H

S集合H在运算*作用下封闭<H,*,e>是<S,*,e>的子含幺半群子含幺半群e

H子半群举例例：<S，*>是一个半群，*运算的运算表如下：问：(1)<{c,d},*>(2)<{b,c,d},*>(3)<{b,c},*>(4)<{c},*>(5)<{a,b},*>是<S，*>的子半群吗？子半群含幺子半群子半群含幺子半群子半群子半群不是子半群子含幺半群举例集合A=

0,2,4

(1)<A,×6>是含幺半群;(2)<A,×6>不是<N6,×6>的子含幺半群。

解答

<A,×6>的幺元是4，所以<A,×6>是独异点；

<N6,

6>的幺元是1。而1

A,，因此<A,

6>不是<N6,

6>的子含幺半群。定理<S,*,e>:含幺半群*运算表中任何两行或两列都是不相同的证明a,b

Sa≠b假设a行和b行完全相同a*e=b*e

a=b与a≠b矛盾结论成立元素的幂的定义

在含幺半群<S,*,e>中，任意元素aS,它的幂被定义为：

a0=ea1=aa2=a*a…

ak+1=ak*a6、循环半群<S,*>:半群<S,*,e>:含幺半群存在一个元素gS对任意的aS都有一个相应的nNa=gn循环半群循环含幺半群生成员循环含幺半群举例

设S={a,b,c,d}，定义S中的二元运算*，*运算的运算表如下：(1)证明<S,*>是一个循环含幺半群，并给出它的生成员；(2)把<S,*>中的每一个元素都表示成生成员的幂；(3)列出<S,*>中所有的等幂元。解答(1)由运算表可知：e=ab和d均为生成员(2)生成员的幂的形式：b0=ab1=bb2=b*b=cb3=b2*b=c*b=dd0=ad1=dd2=d*d=cd3=d2*d=c*d=b(3)a为等幂元定理

每一个循环半群（或含幺循环半群）都是可交换半群（或可交换含幺半群）。证明<S,*>:循环半群g:生成员对任意的a,bX都存在m,nNa=gmb=gna*b=gm*gn=gm+n=gn+m=gn*gm=b*a*运算是可交换的<S,*>是可交换半群二、群1、群的定义2、阿贝尔群3、循环群4、子群1、群的定义（1）<S，*>是代数系统；（2）“*”运算满足结合律；（3）<S，*>中存在幺元e；注意：群中无零元群含幺半群（4）<S，*>中任意一个元素都有逆元素；群举例<R，×>和<R-{0}，×>是群吗？为什么？解：<R，×>:0是<R，×>的零元，而零元是不可逆的。<R-{0}，×>：（1）<R-{0}，×>是代数系统；（2）存在幺元e=1;（3）“×”可结合；（4）对任意实数x,x-1=1/x不是是有限群和无限群

设<S，*>是一个群，若集合S是有限集则称<S，*>是有限群，|S|称为有限群的阶数。 若集合S是无限集则称<S，*>是无限群。注意：群的运算表中没有两行或两列是相同的定理<A，*>:群对于任意的a,b∈A方程a*x=by*a=b在A中都有唯一的解证明(1)证明方程有解：x=a-1*by=b*a-1方程的解是:①左式＝a*x＝

a*(a-1*b)（*运算可结合）=(a*a-1)*b=e*b=b=右式②左式＝y*a＝

(b*a-1)*a（*运算可结合）=b*(a-1*a)=b*e=b=右式证明（续）（2）证明方程有唯一的解：假设方程有其他的解分别为x1,y1,则：a*x1=b

a-1*a*x1=a-1*b(a-1*a)*x1=a-1*be*x1=a-1*b

x1=a-1*b同理：y1＝b*a-1定理<A，*>:群对于任意的a,b,c∈A(a*b=a*c)∨(b*a=c*a)

消去律

b=c证明设a的逆元是a-1，则：a*b=a*c

a-1*a*b=a-1*a*c(a-1*a)*b=(a-1*a)*ce*b=e*c

b=c同理：b*a=c*a

b=c定理对于任意的a,b∈A，有：(a*b)-1=b-1*a-1<A，*>:群证明由逆元的定义：x*x-1=x-1*x=e要证明：(a*b)-1=b-1*a-1即证明:(a*b)*(b-1*a-1)=(b-1*a-1)*(a*b)=e(a*b)*(b-1*a-1)=a*(b*b-1)*a-1=a*e*a-1=a*a-1=e(b-1*a-1)*(a*b)=b-1*(a-1*a)*b=b-1*e*b=b-1*b=e2、阿贝尔群<A，*>:群“*”:可交换阿贝尔群交换群3、循环群

若群<A，*>中每个元素均是它的某个元素a的整数幂，则称<A，*>是由a生成的循环群。a称为<A，*>的生成元素。定理<G,*>:有限循环群a:生成元素|G|=ne:幺元an=eG={a,a2,a3,…,an=e}使an=e的最小的正整数元素a的阶或周期循环群举例设G={[0]，[1]，[2]，[3]}（1）<G,+4>是循环群吗？（2）找出生成元。[a]+4[b]=[a+4b]解答（1）

<G,+4>是循环群；（2）生成元：[1],[3][1]1=[1][1]2=[1]+4[1]＝[2][1]3=[1]2+4[1]＝[2]+4[1]=[3][1]4=[1]3+4[1]＝[3]+4[1]=[0]=e[1]的周期为4解答（续）生成元：[3][3]1=[3][3]2=[3]+4[3]＝[2][3]3=[3]2+4[3]＝[2]+4[3]=[1][3]4=[3]3+4[3]＝[1]+4[3]=[0]=e[3]的周期为44、变换群A:非空集合PA:从A到A的所有双射函数的集合∘:函数的复合运算<PA,∘>:群变换群|A|!变换群举例A={1,2,3}f1={<1,1>,<2,2>,<3,3>}=IAf2={<1,1>,<2,3>,<3,2>}f3={<1,2>,<2,1>,<3,3>}f4={<1,3>,<2,2>,<3,1>}f5={<1,2>,<2,3>,<3,1>}f6={<1,3>,<2,1>,<3,2>}∴PA={f1,f2,f3,f4,f5,f6}变换群举例（续）（1）∘在PA上封闭；（2）∘可结合；（3）幺元存在，e=f1（4）每个元素均可逆：f1-1=

f1，f2-1=

f2，

f3-1=

f3，

f4-1=

f4，f5-1=

f6，

f6-1=

f5◦f1f2f3f4f5f6f1f1f2f3f4f5f6f2f2f1f6f5f4f3f3f3f5f1f6f2f4f4f4f6f5f1f3f2f5f5f3f4f2f6f1f6f6f4f2f3f1f55、子群<H，*>是<A，*>的子群<A，*>:群H

SH≠Φ<H，*>也是一个群平凡子群<A，*>:群<H，*>是<A，*>的一个子群H={e}或H=A<H，*>是<A，*>的平凡子群判断子群的方法（1）含幺元；（2）封闭性；（3）每个元素均可逆；子群举例求出<Z6，+6>的所有子群。解答e=[0][1]-1=[5],[5]-1=[1][2]-1=[4],[4]-1=[2][3]-1=[3],[0]-1=[0](1)<{[0]},+6>(2)<{[0],[3]},+6>,(3)<{[0],[2],[4]},+6>(4)<Z6，+6>是<Z6，+6>的子群。拉格朗日定理<G,*>:有限群|G|=n<H,*>:<G,*>的子群|H|=mm|nm是n的因子推论任何素数阶的群不可能有非平凡子群。第7章 图第1节 图的基本概念第2节 子图与图的运算第3节 路径、回路和连通性第4节 图的矩阵表示第5节 欧拉图和哈密顿图第6节 平面图与欧拉公式第7节 二部图与匹配第8节 树第9节 根树及其应用第1节 图的基本概念1、图的定义2、无向图、有向图、混合图3、邻接结点、邻接边4、自环、平行边、简单图5、度（入度、出度）6、奇结点、偶结点7、孤立结点、端点（悬挂点）、悬挂边8、零图、平凡图、d度正则图、完全图1、图的定义图G是一个三元组:<>ΨGV(G),E(G),非空结点集合边的集合从E(G)到结点无序偶（有序偶）集合上的函数有向边、无向边边的曲、直、长、短以及结点的位置是无关紧要的ΨG(ei)=(vi,vj)结点的无序偶无向边用连接vi和vj的无向线段表示ΨG(ei)=<vi,vj>结点的有序偶有向边用连接vi和vj的有向线段表示vi为边ei的起点vj为边ei的终点vivjvivjeiei图的举例G=<V(G),E(G),ΨG>V(G)={a,b,c,d}E(G)={e1,e2,

e3,

e4,

e5,

e6}ΨG(e1)=(a,b)，ΨG(e2)=(a,c)ΨG(e3)=(b,d)ΨG(e4)=(b,c)ΨG(e5)=(d,c)，ΨG(e6)=(a,d)请画出对应的无向图。abdce1e2e3e4e5e6abdce1e2e3e4e5e62、无向图、有向图、混合图（1）有向图：若图G中所有的边都是有向边。（2）无向图：若图G中所有的边都是无向边。（3）混合图：若图G中一些边是有向边，另一些边是无向边。只讨论有向图和无向图3、邻接结点、邻接边关联同一个结点的两条边邻接结点:由一条边相连接的两个结点vivjeivi和vj邻接邻接边:vivjeiei和ej邻接vkej邻接结点、邻接边举例 a、b、c、d四个结点中的任意两个结点都是邻接结点；

e1和e5不邻接；

e4和e6不邻接；

e2和e3不邻接。4、自环、平行边、简单图图G=<V(G),E(G),ΨG>（1）自环:关联于同一个结点的边（2）平行边:关联于同一对结点的两条边（3）简单图:无平行边和自环的图平行边举例

在有向图中，如果边e1和e2关联于同一对结点，但方向相反，则它们不是平行边。5、度（入度、出度）图G=<V(G),E(G),ΨG>v∈V(G)与结点v相关联的边的条数（1）v的度:G是无向图,deg(v)（2）v的出度:G是有向图,以v为起点的边的条数deg+(v)v的入度:以v为终点的边的条数deg-(v)v的度:v的出度和入度之和deg(v)自环的度

对于无向图中的一个自环，给该结点的度增加2； 对于有向图中的自环，给该结点增加一个出度和一个入度，故该结点的度也增加2。结点度的举例给出图1各结点的度；给出图2各结点的出度、入度、度。解答deg(v1)=deg(v4)=3deg(v2)=deg(v3)=2deg+(v1)=1,deg-(v1)=1,deg(v1)=2deg+(v2)=1,deg-(v2)=2,deg(v2)=3deg+(v3)=2,deg-(v3)=0,deg(v3)=2deg+(v4)=2,deg-(v4)=1,deg(v4)=3deg+(v5)=0,deg-(v5)=2,deg(v5)=2(n,m)图图n个结点m条边(n,m)图定理(n,m)图所有结点的度之和等于边数的两倍证明因为：每条边必关联两个结点一条边给它所关联的两个结点的度各增加1为整个图的度数增加2所以：结点的度数总和恰好为边数的两倍。定理验证m=5deg(v1)+deg(v2)+deg(v3)+deg(v4)=3+2+2+3=10=2m定理(n,m)有向图所有结点的出度之和等于入度之和等于边数定理验证m=6deg+(v1)+deg+(v2)+deg+(v3)+deg+(v4)+deg+(v5)=1+1+2+2+0=mdeg-(v1)+deg-(v2)+deg-(v3)+deg-(v4)+deg-(v5)=1+2+0+1+2=m6、奇结点、偶结点偶结点：奇结点：度数为奇数的结点度数为偶数的结点定理在任何图中，必有偶数个奇结点。证明图G=<V(G),E(G),ΨG>|E|=mV1:V2:V中奇结点集合V中偶结点集合偶结点的度数之和偶数偶数奇结点的度数之和偶数|V1|偶数偶数个奇结点7、孤立结点、端点（悬挂点）、悬挂边图G=<V(G),E(G),ΨG>v∈V(G)（1）孤立结点:deg(v)=0（2）端点:deg(v)=1悬挂点（3）悬挂边:与悬挂点关联的边孤立结点、悬挂点、悬挂边举例V5是悬挂点；(v4,v5)是悬挂边;V6是孤立结点8、零图、平凡图、d度正则图、完全图G=<V(G),E(G),ΨG>:简单无向图（1）零图:E=Φ(n,0)图（2）平凡图:|V|=1E=Φ(1,0)图（3）d度正则图:每个结点的度均为d（4）完全图：任意两点间恰有一条边连接Kn举例第2节 子图与图的运算一、子图二、图的运算一、子图1、子图2、真子图3、生成子图4、结点导出子图5、边导出子图1、子图两个图G=<V,E,

>G′=<V′,E′,

′>V′VE′

EG′是G的子图2、真子图两个图G=<V,E,

>G′=<V′,E′,

′>V′VE′EG′是G的真子图3、生成子图两个图G=<V,E,

>G′=<V′,E′,

′>V′=VE′

EG′是G的生成子图子图的举例4、结点导出子图G=<V,E,

>V′VV′≠φV′为结点集合起点和终点均在V′中的边的全体为边集合由V′导出的G的子图G[V′]V′V导出子图G[V-V′]G-V′结点导出子图举例求:(1)由结点集合V′={a,b,d,e}导出的G的子图G[{a,b,d,e}](2)G-{a,d}解答5、边导出子图G=<V,E,

>E′EE′≠φV′={v|v

V∧(

e)(eE′∧v与e关联)}以V′为结点集合以E′为边集由E′导出的子图边导出子图举例求:由边集合E′={e1,e2,e5,e7}导出的G的子图G[{e1,e2,e5,e7}]解答二、图的运算1、可运算的2、边不相交的3、点不相交的4、图的交5、图的并6、图的差7、图的环和8、相对于图G的补图9、相对于完全图的补图1、可运算的G1=<V1,E1,

1>G2=<V2,E2,

2>同为无向图或同为有向图对任意的e

E1∩E2

1(e)=2(e)G1与G2是可运算的可运算的举例问：G1和G2是否是可运算的？解答E1∩E2={e1,e2,e5}

1(e1)=(a,b)

2(e1)=(a,b)

1(e2)=(a,d)

2(e2)=(a,d)

1(e5)=(b,d)

2(e5)=(b,d)G1和G2是可运算的2、边不相交的G1=<V1,E1,

1>G2=<V2,E2,

2>同为无向图或同为有向图G1与G2是不相交的E1∩E2=φV1∩V2=φG1与G2是边不相交E1∩E2=φ3、点不相交的G1与G2是点不相交的G1=<V1,E1,

1>G2=<V2,E2,

2>同为无向图或同为有向图V1∩V2=φ4、图的交G1=<V1,E1,

1>G2=<V2,E2,

2>是可运算的V1∩V2为结点集E1∩E2为边集合G1和G2的交G1∩G25、图的并G1=<V1,E1,

1>G2=<V2,E2,

2>是可运算的V1∪

V2为结点集E1∪

E2为边集合G1和G2的并G1∪

G26、图的差G1=<V1,E1,

1>G2=<V2,E2,

2>是可运算的G1与G2的差:在G1中去掉G2的边所得到的图G1-

G27、图的环和G1=<V1,E1,

1>G2=<V2,E2,

2>是可运算的V1∪

V2为结点集E1⊕

E2为边集合G1和G2的环和G1⊕

G2图运算的举例与如下图所示，求：G1∩G2

G1∪G2G1-G2G2-G1，G1⊕G2

。G1∩G2V1∩V2E1∩E2={a,b,d}={e1,e2,e5}G1∪G2V1∪V2{e1,e2,e3,e4,e5,e6,e7,e8,e9,e10}={a,b,c,d,e}E1∪E2=G1-G2G2

–G1G1⊕G2E1⊕

E2=V1∪V2={a,b,c,d,e}{e3,e4,e6,e7,e8,e9,e10}8、相对于图G的补图G=<V,E>的子图:G′=<V′,E′>:给定另一个图G"=<V",E">（1）E"＝E-E′（2）V"是E"中的边所关联的结点集合G"是子图G′的相对于图G的补图解释(1)E′∩E"＝φ(2)E′∪E"＝E(3)V"仅是E"中的边所关联的结点集合，不包含别的结点:G′∪G"＝G(4)G′与G"的关系不是互逆的。相对补图的举例图G和图G′如下图所示:求图G′相对于图G的补图。解答E"＝E-E′={(a,e),(c,e),(d,e)}V"＝{a,c,d,e}图G′相对于图G的补图为G"G"相对于图G的补图为G"′不是G′没有结点e9、相对于完全图的补图补图是互逆的给定一个图GG中所有结点能使G成为完全图所添加的边图G相对于完全图的补图G的补图补图举例求G1和G2的补图。解答解答第3节 路径、回路和连通性一、路径二、连通性一、路径1、路径2、可达的、不可达的1、路径(1)路径(2)回路(3)简单路径、基本路径(1)路径路径是结点和边的交替序列图G=<V,E>v0,v1…vnVe1,e2…enEei:关联vi-1和vi序列v0e1v1e2…envn:从v0到vn的路路径路径的起点路径的终点路径的长度:路径中边的数目(2)回路起点和终点为同一个结点的路径(3)简单路径、基本路径简单路径:简单回路:基本路径:基本回路:边不重复的路径边不重复的回路点不重复的路径点不重复的回路路径举例(1)AaAcBgChF:(2)AbDdEeBfChF:(3)AbDdEeBcA:从A到F的路径长度为4简单路径不是基本路径从A到F的路径长度为5简单路径基本路径从A到A的回路长度为4简单回路基本回路路径举例v1e2v2e3v3e4v4v4e1v1e2v2e3v3e4v4e1v1简单路径基本路径不是基本路径不是简单路径定理寻找基本路径的方法：v和v’是图G中的结点存在从v到v’的路径存在从v到v’的基本路径从路径中去掉所有的回路证明从v到v′存在路径Pvv′:

v0e1v1e2…elvlvv′若Pvv′不是基本路径结点vi在该路径中不止一次出现v0e1v1e2…eivi

ei+1

…

ejvjej+1…elvlvi=vj在该路径中去掉从vi到vj的边v0e1v1e2…eiviej+1…elvl从v0到vl的路径如此反复去掉所有的回路从v0到vl的基本路径定理应用举例(1)ae2be10de9ae2be4c:(2)ae1ae2be4c:求从a到c的基本路径是从a到c的一条路径,是从a到c的一条路径,求从a到c的基本路径解答(1)ae2be10de9ae2be4c:不是基本路径去掉回路ae2be10de9aae2be4c基本路径(2)ae1ae2be4c:不是基本路径去掉回路ae1aae2be4c基本路径定理n阶图中的基本路径的长度小于n。证明基本路径:点不重复的路径在一个基本路径中有l个不同的结点v0,v1,…,vl-1有l-1条边:e1,e2,…,el-1v0e1v1e2…el-1vl-1基本路径n阶图:有n个不同的结点最多有n-1条边出现在基本路径上n阶图中的基本路径的长度小于n2、可达的、不可达的v1,v2:图G中的结点存在从v1到v2的路径从v1到v2

是可达的否则:从v1到v2不可达v1可达v2

在无向图中:在有向图中:v2可达v1

V2不一定可达v1

二、连通性1、连通图2、基础图3、强连通、单向连通、弱连通4、极大子图5、分支1、连通图G:无向图任意两个结点都相互可达连通图否则:G是非连通图2、基础图把每条有向边改为无向边而得到的无向图有向图的基础图3、强连通、单向连通、弱连通G:有向图(1)强连通图:任意两结点均互相可达(2)单向（侧）连通图:任意两结点必有一结点可达另一个结点(3)弱连通图:G的基础图是连通的连通性举例

判断图G1,G2,G3是强连通图、单向连通图还是弱连通图？解答v2不可达v3v3也不可达v2G1不是单向连通图G1的基础图是连通图G1是弱连通图解答v1可达v3v3不可达v1G2不是强连通图v2可达v3v2可达v1G2是单向连通图解答v1可达v2v2可达v1v1可达v3v3可达v1v2可达v3v3可达v2G3是强连通图4、极大子图G’:G的子图G’具有连通性对于G的任意的具有连通性的子图G’’G’

G’’G’=G’’G’是G的极大连通子图强连通性强连通性强连通单向连通性单向连通性单向连通弱连通性弱连通性弱连通5、分支无向图G的极大连通子图

G的分支（分图）:G的强分支（强分图）:有向图G的极大强连通子图G的单向分支（单向分图）:有向图G的极大单向连通子图G的弱分支（弱分图）:有向图G的极大弱连通子图定理连通无向图恰有一个分支非连通无向图有一个以上的分支举例图G是一个连通无向图其只有一个极大连通子图，就是其本身G。举例图G是一个非连通无向图其有两个极大连通子图G1和G2。定理强连通有向图恰有一个强分支非强连通有向图有一个以上的强分支单向连通单向分支单向连通单向分支弱连通弱连通弱分支弱分支定理G=<V,E>:简单有向图每一个结点都恰处于一个强分支中分支举例求G1、G2的强分支、单向分支、弱分支。解答解答定理无向图G（连通或不连通）恰有两个奇结点必有连接此两结点的路径证明设G中的两个奇结点是v1和v2(1)若G是连通图，则v1和v2之间必有路径；(2)若G是非连通图，则G至少有两个以上的分支因为，在任何一个图中必有偶数个奇结点所以：v1和v2必处于同一个分支中，即：V1和v2之间必有路径。第4节 图的矩阵表示一、邻接矩阵二、可达性矩阵三、完全关联矩阵一、邻接矩阵1、简单无向图的邻接矩阵2、简单有向图的邻接矩阵3、矩阵AAT4、矩阵ATA5、矩阵Am1、简单无向图的邻接矩阵G:简单无向图n阶方阵A=(aij)n×nV={v1,v2,…,vn}邻接矩阵:aij=(vi,vj)

E10否则邻接矩阵举例写出简单无向图G对应的邻接矩阵A。A=abcdeabcde1111111111111100000000000简单无向图邻接矩阵的特点(1)主对角线均为0的对称阵；(2)每一行（列）中“1”的个数是该行所对应的结点的度；(3)所有元素均为“0”的邻接矩阵对应的是零图;(4)除主对角线外所有元素均为“1”的邻接矩阵对应的是完全图。2、简单有向图的邻接矩阵G:简单有向图n阶方阵A=(aij)n×nV={v1,v2,…,vn}邻接矩阵:aij=<vi,vj>

E10否则邻接矩阵举例写出简单有向图G对应的邻接矩阵A。A=v1v2v3v4v1v2v3v40101111010100000简单有向图邻接矩阵的特点(1)不一定是对称阵；(2)每一行中“1”的个数是该行所对应的结点的出度；(3)每一列中“1”的个数是该列所对应的结点的入度；(4)第i行中“1”的个数与第i列中“1”的个数之和，恰为记点vi的度。二、可达性矩阵1、可达性矩阵P2、求可达性矩阵P的方法1、可达性矩阵PG:简单有向图V={v1,v2,…,vn}n阶方阵P=(pij)n×nG的可达性矩阵pij=10从vi到vj至少存在一条路径否则2、求可达性矩阵P的方法(1)回忆两个定理(2)求可达性矩阵P的方法(1)回忆两个定理若存在从vi到vj的路径，则存在从vi到vj的基本路径；n阶图的基本路径长度小于n;(2)求可达性矩阵P的方法A：aij表示从vi到vj长度为1的路径的数目；A2:aij(2)表示从vi到vj长度为2的路径的数目；……An:aij(n)表示从vi到vj长度为n的路径的数目；令：Bn=A+A2+…+An

其中：

Bn中第i行第j列的记入值bij表明：从vi到vj长度小于或等于n的路径的数目若bij≠0，则表明从vi到vj可达。求可达性矩阵P的方法（续）A:简单有向图G的邻接矩阵（1）A2=A∧AA3=A2∧A,…,An=An-1∧A（2）P=A∨A2∨…∨An三、完全关联矩阵：1、无向图的完全关联矩阵2、有向图的完全关联矩阵1、无向图的完全关联矩阵G:无向图V={v1,v2,…,vn}E={e1,e2,…,em}Ae=(aij)n×m图G的完全关联矩阵aij=10vi关联ej否则无向图的完全关联矩阵举例求无向图G的完全关联矩阵AeAe=v1v2v3v41110111000001100e1e2e3e4e51001无向图的完全关联矩阵的特点（1）每一列中只有两个“1”；（2）每一行中“1”的个数是该结点的度数；（3）若某行中的元素均为“0”，则该行所对应