離散二總復習

離散二總復習代數(shù)系統(tǒng)熟練掌握二元運算性質的判斷及證明。掌握代數(shù)系統(tǒng)的同構定義和證明，了解同構性質的保持。熟練掌握半群,獨異點和群的概念。熟悉群的階、群中元素的階以及群的根本性質。掌握子群的證明。熟悉陪集的定義和性質。熟悉Lagrange定理及其推論,學會簡單應用。代數(shù)系統(tǒng)掌握循環(huán)群和循環(huán)周期的概念。掌握有限循環(huán)群生成元及其子群的求法。掌握環(huán)與域的概念。群中的簡單證明主要包括：群中的等式〔元素相等或集合相等〕與元素的階相關的命題群的其它簡單命題，如交換性等經(jīng)常使用的工具：

算律：結合律、消去律和特殊元素相關的等式，如單位元、逆元等。冪運算規(guī)那么和元素的階相關的性質?！踩纾篴為2階元的充分必要條件是a-1=a等〕

根本運算和性質練習1：給定群<G,*>，*的運算表如右圖所示。求解下面群的方程：

b*d-1*x*c=d*c-1解:

b*d-1*x*c=d*c-1∵

d-1=b

c-1=c∴b*b*x*c=d*c∵b*b=c∴c*x*c=d*c

消去c得c*x=d

解得:

x=c-1*d=c*d=b*abcdaabcdbbcdaccdabddabc群中的簡單證明習題2：給定集合G＝{x|x是有理數(shù)且x≠1}，在G上定義二元運算*如下：任何a

,b∈G

a*b=a+b-ab求證<G

,*>是個交換群。證明：封閉、結合、含幺、可逆、交換

群中的簡單證明習題3：

設G為群，任取x∈G

，有x2=e,證明G是交換群。證明：

∵x2=e∴x-1=x

可證明在群G中

群中的簡單證明習題4：

偶數(shù)階群中必含2階元。證明：如果元素x的階大于2，那么x-1≠x，x與它的逆元成對出現(xiàn)，由于群中元素個數(shù)為偶數(shù)個，那么除幺元e外，一定有2階元。

子群的證明習題5：設G為群，a是G中的2階元，證明G中與a可交換的元素構成G的子群。證明：

令H={x|x∈G∧xa=ax},下面證明H是G的子群。首先e屬于H，H是G的非空子集。任取x,y∈H，有

(xy-1)a=x(y-1a)=x(a-1y)-1=x(ay)-1=x(ya)-1=x

a-1y-1=x

ay-1=axy-1=a(xy-1)

因此xy-1屬于H。由判定定理命題得證。

子群的證明習題6：設f和

g都是群<G1,

>到<G2,

>的同態(tài)，證明<C,

>是<G1,

>的一個子群，其中

C={x|x∈G1且f(x)=g(x)}證明：用子群定義證明<C,

>滿足：a)封閉性。任取a,b∈C，∴f(a)=g(a)

f(b)=g(b)

f(a

b)=f(a)

f(b)=g(a)

g(b)=g(a

b)∴a

b∈Cb)證幺元e1∈C,設e1和e2分別是G1和G2中的幺元,因f(e1)=e2=g(e1)∴e1

∈C。c)可逆性：任取x∈C,

f(a)=g(a)a-1∈G1,

f(a-1)=(f(a))-1=(g(a))-1=g(a-1)∴a-1∈C。綜上所述，<C,

>是<G1,

>的一個子群。拉格朗日定理應用實例習題7：

證明6階群G中必含有3階元。應用習題3結論：只含有1階和2階元的群是Abel群。證明：由拉格朗日定理推論可知G中只能含有1,2,3,6階元。假設含有6階元，那么一定含有3階元。假設不含6階元，那么G中含有1個幺元和5個2階元，且為交換群。假設只有二階元x,y∈G，那么xy=yx∈G，G中只有4個元素；假設另有z∈G，那么xz≠yz∈G，G中有7個元素，所以如果不含有3階元，G中的元素個數(shù)一定不為6。矛盾。習題8：設H1,H2分別是群G的r,s階子群，假設r,s互素，證明H1∩H2={e}。拉格朗日定理應用實例證明：H1

H2是H1和H2的子群。由Lagrange定理，|H1

H2|整除r，也整除s。

從而|H1

H2|整除r與s的最大公因子。

因為(r,s)=1，

從而|H1

H2|=1。

即H1

H2={e}。群的同態(tài)與同構習題9：

定義群G上的函數(shù)f，f(x)=x-1，x∈G

，證明f為自同構當且僅當G為交換群。證明：

必要性：任取x,y∈G,xy=f((xy)-1)=f(y-1x-1)=f(y-1)f(x-1)=yx

充分性：易見f為雙射。任取x,y∈G,有

f(xy)=f(yx)=(yx)-1=x-1y-1=f(x)f(y)循環(huán)群習題10：設群G的運算表如表所示，問G是否為循環(huán)群？如果是，求出它所有的生成元和子群。解：易見a為單位元。

由于|G|=6,|b|=6,所以b為生成元.G=<b>為循環(huán)群.|f|=6,因而f也是生成元|c|=3,|d|=2,|e|=3,因此c,d,e不是生成元。

子群：<a>={a},<c>={c,e,a},<d>={d,a},G

。

環(huán)與域習題11：在整數(shù)環(huán)中定義?和

兩個運算,

a,b∈Z有

a?b=a+b

1,a

b=a+b

ab.證明<Z,?,

>構成環(huán)證明

a,b∈Z有a?b,a

b∈Z,兩個運算封閉。任取a,b,c∈Z，證明?與

可結合，1為?的單位元。2

a為a關于?的逆元。Z關于?構成交換群,關于

構成半群。

關于?滿足分配律。

a

(b?c)=a

(b+c

1)=2a+b+c

ab

ac

1

a

b)?(a

c)=2a+b+c

ab

ac

1<Z,?,

>構成環(huán)環(huán)與域習題12：判斷以下集合和給定運算是否構成環(huán)、整環(huán)和域,如果不構成,說明理由.(1)A={a+bi|a,b∈Q},其中i2=1,運算為復數(shù)加法和乘法(2)A={2z+1|z∈Z},運算為實數(shù)加法和乘法(3)A={2z|z∈Z},運算為實數(shù)加法和乘法(4)A={x|x≥0∧x∈Z},運算為實數(shù)加法和乘法(5),運算為實數(shù)加法和乘法課后習題5-1:(1)(2)5-2:(1)(2)(5)5-3:(3)(5)5-4:(1)(2)(5)5-5:(2)(4)5-7:(3)(5)5-8:(2)(3)(11)第九章：2、4、5、6、8、11、15、17、18第十章：2、8、9、20、34

格與布爾代數(shù)掌握格的定義，了解格的性質及格同態(tài)。能夠證明格中的等式和不等式。能判別格L的子集S是否構成子格。能夠判斷格，分配格，有補格和布爾格。掌握布爾代數(shù)中的運算性質。1、格的定義與性質偏序集構成格的條件：任意二元子集都有最大下界和最小上界。

格的實例：正整數(shù)的因子格，冪集格，子群格。格的性質：對偶原理，格中運算律〔交換、結合、冪等、吸收〕，保序性，分配不等式。

格作為代數(shù)系統(tǒng)的定義。習題1.判斷下述偏序集是否構成格？

如果不是說明理由。

2.求下述命題的對偶命題。

（1）(a∧b)∨b=b

（2）b∨(c∧a)≤(b∨c)∧a習題3.證明題（1）(a∧b)∨b=b

（2）(a∧b)∨(c∧d)≤(a∨c)∧(b∨d)2、子格與格同態(tài)子格判定定理。格L的非空子集S構成L的子格的條件：S對L的兩個運算封閉。

函數(shù)f構成格同態(tài)的條件：f(a∧b)=f(a)∧f(b),f(a∨b)=f(a)∨f(b)格同態(tài)的保序性。習題1.求格L的所有子格。2.任取格L的元素a，令S={x|x∈L且x≤a}，證明S是L的子格。3、分配格與有補格如果格中一個運算對另一個運算是可分配的，稱這個格是分配格。

分配格的兩種判別法：不存在與鉆石格或五角格同構的子格；對于任意元素a,b,c，有a∧b=a∧c且a∨b=a∨cb=c

有界格的定義及其實例。

格中元素的補元及其性質〔分配格中補元的唯一性〕

有補格的定義

習題1.判別下面L是否為分配格。2.求出每個格的所有的補元，說明它們是否為

有補格。

習題3、給出有界格如圖，答復以下問題：a)哪些元素有補元？指出其補元。b)該格是分配格嗎？為什么？c)該格是有補格嗎？為什么？答案：a)a、c、d、f、g

無補元;b和e互為補元;0和1互為補元.b)不是分配格,因為它含有五元素非分配環(huán)格。c)它不是有補格,因為很多元素無補元。4、布爾代數(shù)會判別一個格是布爾格。

證明布爾代數(shù)中的等式。

了解任意有限布爾代數(shù)都與某個冪集格同構。

習題1.設<B,∧,∨,-,0,1>是布爾代數(shù)，證明對于B中任意元素a,b習題2.判斷下述代數(shù)系統(tǒng)是否為格？是不是布爾代數(shù)？〔1〕S={1,3,4,12}，x,y∈S，xy與xy分別表示x與y的最小公倍數(shù)和最大公約數(shù)?！?〕S={0,1,2}，為模3加法，為模2乘法〔3〕S={0,...,n},其中n≥2;任給x,y∈S,xy=max(x,y),xy=min(x,y)。

課后習題小本6-1〔1〕〔2〕〔4〕6-2〔2〕〔5〕6-3〔1〕〔3〕〔4〕〔6〕6-4〔2〕〔6〕〔8〕大本習題十一4、6、8、12圖的根本概念無向圖、有向圖、關聯(lián)與相鄰、簡單圖、完全圖、正那么圖、子圖、補圖；握手定理與推論；圖的同構通路與回路及其分類無向圖的連通性與連通度有向圖的連通性及其分類圖的矩陣表示及根本含義習題1、9階無向圖G中，每個頂點的度數(shù)不是5就是6。證明G中至少有5個6度頂點或至少有6個5度頂點。證明：關鍵是利用握手定理的推論。方法一：窮舉法設G中有x個5度頂點，那么必有(9x)個6度頂點，由握手定理推論可知，(x,9x)只有5種可能：(0,9),(2,7),(4,5),(6,3),(8,1〕它們都滿足要求。方法二：反證法否那么，由握手定理推論可知，“G至多有4個5度頂點并且至多有4個6度頂點〞，這與G是9階圖矛盾。習題2．數(shù)組2,2,2,2,3,3能簡單圖化嗎？假設能，畫出盡可能多的非同構的圖來。解答：只要能畫出6階無向簡單圖，就說明它可簡單圖化。以下圖的4個圖都以此數(shù)列為度數(shù)列，請證明它們彼此不同構，都是K6的子圖。習題3、有向圖D如下圖，答復以下問題：(1)寫出D的鄰接矩陣。(2)D是哪類連通圖?(3)D中v1到v4長度為1,2,3,4的通路各多少條？討論它們的類型〔簡單通路還是初級通路〕。(4)D中v1到v1長度為1,2,3,4的回路各多少條？討論它們的類型〔簡單回路還是初級回路〕。(5)D中長度為4的通路〔不含回路〕有多少條？(6)D中長度4的通路有多少條？其中有幾條是回路？(7)寫出D的可達性矩陣。課后習題第十四章:1、2、3、4、5、6、7、8、9、12、13、14、15、16、17、18、19、20、21、22、23、24、25、26、27、28、30、31、32、35、37、38、39、40、41、4445、46、47、49歐拉圖和漢密爾頓圖掌握歐拉圖、半歐拉圖的定義及判別定理掌握漢密頓圖、半漢密頓圖的定義能夠用漢密頓圖的必要條件和充分條件分別進行判斷。要特別注意的是，不能將必要條件當作充分條件，也不要將充分條件當必要條件掌握歐拉圖和漢密爾頓圖的簡單應用習題1.設G為n〔n2〕階無向歐拉圖，證明G中無橋證明：設C為G中一條歐拉回路，任意的eE(C)，可知Ce是Ge的子圖，由()知Ce連通，所以e不為橋。習題2.某次國際會議8人參加，每人至少與其余7人中的4人有共同語言，問效勞員能否將他們安排在同一張圓桌就座，使得每個人都與兩邊的人交談？解答：設計圖并證明為H圖習題3.距離(公里)如下圖。如何走行程最短？解答：最短的路為ABCDA，距離為36公里課后習題第十五章：1,2,8,9,11,12,13,14,15,16,20,21,22樹掌握無向樹的定義及性質熟練求解無向樹準確求解給定帶權連通圖的最小生成樹掌握根本回路、根本割集的概念，并會計算理解根樹及其分類等概念熟練掌握求最優(yōu)樹及最正確前綴碼的方法掌握二叉樹的遍歷習題1.請畫出K5的所有不同構的生成樹。解答：K5的生成樹T邊數(shù)為4,T的度數(shù)和為8有3棵〔略〕2.一棵正那么二叉樹有e條邊，t個葉結點，請推導出e與t的關系式。解答：根據(jù)正那么m叉樹的公式：(m-1)i=t-1得分支結點數(shù)i=t-1又根據(jù)樹中e=v-1，v是結點數(shù)所以e=(i+t)-1=t-1+t-1=2t-2習題3.一棵樹T有n2個結點度數(shù)為2，n3個結點度數(shù)為3，…nk個結點度數(shù)為k，問它有多少個度數(shù)為1的結點?解答：設有n1個度數(shù)為1的結點，又令T有v個結點，e條邊。T的所有結點度數(shù)總和=n1+2n2+…+knk=2e，因e=v-1∴n1+2n2+…+knk=2(n1+2n2+…+knk-1)∴n1=n3+2n4+…+(k-2)nk+2。習題4.下面序列哪些可以構成一個無向連通圖的結點度數(shù)序列?哪些不能?哪些可以構成連通簡單圖?哪些可能構成歐拉圖?哪些可能構成漢密爾頓圖?哪些可能是完全圖?哪些可能是樹?如果能，請畫出一個那樣的圖；如果不能請說明原因。

a.(1,2,3,3)b.(3,3,3,3)c.(1,1,1,1,2,4)

d.(2,3,3,4,4)e.(2,3,4,4,5)f.(2,2,2,2,4)習題5.畫出基圖為圖所示無向樹的所有非同構的根樹解答：略6.求權值為1,2,3,3,4,6,8的最優(yōu)樹。解答：略課后習題第十六章:1，2，4，10，13，14，17，19，20，23，24，25，26，29，31，33，35，36，37，38，41，42平面圖掌握根本概念：平面圖、平面嵌入、面、次數(shù)、極大平面圖、極小非平面圖、對偶圖掌握極大平面圖的主要性質和判別方法熟練掌握歐拉公式及推廣，并能用歐拉公式及推廣形式證明有關命題