離散數(shù)學 課件全套 李小南 第1-6章 集合與運算 -代數(shù)結構

第一章集合與運算離散數(shù)學配套教材：李小南目錄CONTENTS1.11.21.31.41.5集合二元關系等價關系與劃分偏序集與布爾格模糊集1.1集合

目錄CONTENTS010203集合的概念與運算映射和基數(shù)良序性和數(shù)學歸納法01集合的概念與運算集合的概念與運算集合是現(xiàn)代數(shù)學中的一個基本概念，所謂集合就是指具有某些特定性質的對象或事物的全體，構成集合的事物稱為集合的元素或元(element)。例

26個英文字母是一個集合，我國56個民族也是一個集合

表示方法：描述法和列舉法

確定性：集合中的元素是確定的，即一個元素要么屬于一個集合，要么不屬于這個集合互異性：集合中的元素都是不同的無序性：集合中的元素是沒有順序之分性質：確定性、互異性和無序性

02映射和基數(shù)映射和基數(shù)

03良序性和數(shù)學歸納法良序性和數(shù)學歸納法

THANKS感謝觀看第1.2節(jié)二元關系離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025目錄CONTENTS010203關系的定義關系的表示與復合關系閉包01關系的定義關系的定義

02關系的表示與復合關系的表示與復合

03關系閉包關系閉包

同時滿足上述三個性質的關系稱為等價關系。

THANKS感謝觀看第1.3節(jié)等價關系和劃分離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025目錄CONTENTS0102

等價關系與等價類劃分粗糙集01等價關系與等價類等價關系與等價類定義1.3.1滿足自反性、對稱性和傳遞性的關系稱為等價關系。

02劃分劃分

由定理1.3.2可知，雖然劃分和等價關系的定義不同,但其實這兩個概念是描述同一情形的兩種不同方式。

粗糙集粗糙集

建立在等價關系基礎上的粗糙集理論于1982年由波蘭學者Pawlak提出,在機器學習、數(shù)據(jù)分析、決策科學等領域有著廣泛應用。

信息表中有些信息是冗雜的，例如表1.3.1中的尺寸和位置這兩個屬性，對對象的分類能力來說是完全一樣的。因此對信息表進一步處理之前，我們常常要簡化信息表，即要對信息表進行屬性約簡，類似的操作在機器學習中常常稱為特征選擇。

THANKS感謝觀看第1.4節(jié)偏序集與布爾格離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025目錄CONTENTS0102偏序集布爾格01偏序集偏序集

最大元最小元

極小元極大元

02布爾格布爾格

THANKS感謝觀看第1.5節(jié)模糊集離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025目錄CONTENTS02模糊集的表示法01模糊集定義03模糊集的運算01模糊集定義模糊集定義

02模糊集的表示方法模糊集的表示方法模糊集主要有下列表示方法：

(2)序對表示法

(3)向量表示法

(4)Zadeh表示法

03模糊集的運算模糊集的運算

THANKS感謝觀看第二章計數(shù)離散數(shù)學配套教材：李小南m目錄CONTENTS2.1排列與組合2.2鴿巢原理與容斥原理2.3組合型生成函數(shù)2.4排列型生成函數(shù)2.5Catalan數(shù)和Stirling數(shù)2.1排列與組合

兩個原理和排列加法原理

有種方法從一堆物體中選出一個物體,又有種方法從另外一堆物體中選出一個物體,那么從這兩堆物體中選出一個物體有種方法.乘法原理

完成第一件事情分兩步.第一步有種方法,第二步有種方法,則完成這件事情有種方法.例2.1.1

大一學生需要選擇一門選修課以獲得課外學分.選修課分數(shù)學類和人文社科類,其中數(shù)學類有2門選修課,人文社科類有5門選修課,則由加法原理可知大一學生有2+5=7種不同選擇.例2.1.2

班里有10名女生和20名男生,班會上需要一個男生和一個女生發(fā)言,則由乘法原理知選擇的方法有1020=200種.如果班會上需要一個同學發(fā)言,則由加法原理知選擇的方法有10+20=30種.

組合和二項式定理

Sperner定理

第2.2節(jié)鴿巢原理與容斥原理離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025鴿巢原理

例2.2.5在6個人中,或者有3個人兩兩相互認識,或者有3個人兩兩相互不認識.

容斥原理

例2.2.6

1到2014之間不能被3,4和10整除的整數(shù)有多少個？例2.2.7

數(shù)學系某班有50人,15人選修了離散數(shù)學,20人選修了模糊數(shù)學,10選修了拓撲學.5人既選修了離散數(shù)學又選修了模糊數(shù)學,8人既選修了模糊數(shù)學又選修了拓撲學,3人既選修了拓撲學又選修了離散數(shù)學,1人同時選修了這三門課.問有多少人這三門課一門都沒有選？第2.3節(jié)組合型生成函數(shù)離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025多重集的組合計數(shù)方法

例2.3.6求用1分、2分、3分的郵票貼出不同面值郵票的方案數(shù).例2.3.7若有1克砝碼3枚、2克砝碼4枚、4克砝碼2枚,問能稱出那幾種重量？各有幾種方案？

組合型生成函數(shù)的性質

性質2.3.2

求序列1,1,...,1,...的組合型生成函數(shù).

線性常系數(shù)遞推關系的求解遞推關系是計數(shù)的一個強有力的工具,特別是在做算法分析時是必需的,而遞推關系的求解主要是利用組合型生成函數(shù).先看兩個著名的例子.例2.3.9N個圓盤依其半徑大小,從下而上套在AB柱上,如圖2.7所示.每次只允許取一個移到柱B或C上,而且不允許大盤放在小盤上方.若要求把柱A上的n個盤移到柱C上,請計算要移動幾個盤次？現(xiàn)在只有A、B、C三根柱子可用.

下面分情況討論具體計算問題.

第2.4節(jié)排列型生成函數(shù)離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025排列型生成函數(shù)

多重集排列計數(shù)的例子

離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025

Cn012345678N112514421324291430

第3章數(shù)理邏輯離散數(shù)學配套教材：李小南目錄CONTENTS3.13.23.33.43.5命題命題公式與邏輯等價范式推理理論謂詞與量詞3.1命題3.1.1命題的定義定義3.1.1命題（proposition）是一個陳述句，它只能取真或假，而不能是兩者.命題是真的或者假的,真和假是命題的真值.真命題的真值是真的,假命題的真值是假的.命題取真和假中之一的值,通常用1或T表示真,0或F表示假.以下陳述句都是命題.(1)今天是星期二.(2)西安電子科技大學是211工程建設大學.(3)西安著名的“秦鎮(zhèn)涼皮”中的“秦鎮(zhèn)”位于西安市長安區(qū).(4)地球是宇宙中唯一存在生命的星球.(5)2035年中國人口會少于13億.(6)16是偶數(shù)且巴黎是法國的首都.

3.1.2聯(lián)結詞

通常用真值表來表示合取、析取這樣的復合命題的真值.真值表反映了命題所有可能組合對應的復合命題的真值情況.合取和析取的真值表如下所示。0000010110011111

0011011110001101例3.1.3將下列命題符號化.(1)吳穎既用功又聰明.(2)吳穎雖然聰明,但不用功.(3)4或6是素數(shù).(4)小李只能拿一個蘋果或一個梨.(5)只要天冷,小王就穿羽絨服.(6)如果天不冷,則小王不穿羽絨服.(7)若小王不穿羽絨服,則天不冷.

001110110010010111113.1.3條件命題

01011111011010011001011010101111

THANKS感謝觀看第3.2節(jié)命題公式與邏輯等價離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，20253.2.1命題公式

續(xù)例3.2.1這種生成過程可以形象地用一棵樹來表示(如下圖所示).

3.2.2重言式與矛盾式

00111011111000111011

0000110010110101110111111001111011111101111111113.2.3邏輯等價

0000000100010000111110011101111101111111

1110000101001001101000001111

11011100000111100111

（蘊涵等價式）（結合律）（德·摩根律）（蘊涵等價式）

（蘊涵等價式）（德·摩根律）（交換律，結合律）（矛盾律）（零律）（蘊涵等價式）（交換律）

（蘊涵等價式）（結合律）（德·摩根律）（蘊涵等價式）第3.3節(jié)范式離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，20253.3.1析取范式與合取范式

3.3.2主范式

極小項二進制數(shù)十進制數(shù)二進制表示十進制表示000012103113

011000000100110010100001

00000011010001111001101111001111

000010001010010111011111100100101111110100111111

第3.4節(jié)推理理論離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，20253.4.1有效論證

00111110111100100001111100013.4.2推理規(guī)則常用的推理規(guī)則：

附加簡化假言推理拒取式析取三段論假言三段論等價三段論構造性二難推理破壞性二難推理

前提引入(1)置換，結論引入前提引入(2)和(3)假言三段論(4)置換，結論引入前提引入(5)和(6)假言三段論，結論引入(7)置換3.4.3間接證法

例3.4.5用歸謬法證明例3.4.4.證明附加前提(1)置換(2)簡化，結論引入(2)簡化，結論引入前提引入(4)和(5)拒取式，結論引入前提引入(3)和(7)拒取式，結論引入(6)和(8)合取(9)置換，結論引入前提引入(10)和(11)合區(qū)

附加前提前提引入(1)和(2)假言推理，結論引入前提引入(3)和(4)假言三段論，結論引入附加前提CP規(guī)則

附加前提前提引入(1)和(2)假言推理，結論引入前提引入(3)和(4)假言三段論，結論引入附加前提CP規(guī)則第3.5節(jié)謂詞與量詞離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，20253.5.1謂詞

量化命題什么時候為真什么時候為假

3.5.2量化命題的邏輯等價式

3.5.3量化命題的推理規(guī)則

推理過程推理規(guī)則前提引入(1)存在例化，結論引入(2)簡化，結論引入前提引入(4)全稱例化，結論引入(3)和(5)假言推理，結論引入(2)簡化，結論引入(6)和(7)合取(8)存在泛化

續(xù)例3.5.13解從前提到結論的推理過程如下表所示.推理過程推理規(guī)則前提引入(1)全稱例化，結論引入前提引入(3)存在例化(4)簡化，結論引入(2)和(5)假言推理，結論引入(4)簡化，結論引入(6)和(7)合取(8)存在泛化THANKS感謝觀看第四章圖論基礎離散數(shù)學配套教材：李小南目錄CONTENTS4.14.24.34.44.5圖與有向圖樹的性質根樹及其應用最小生成樹和最短路徑歐拉圖和哈密頓圖4.1圖與有向圖什么是圖？哥尼斯堡七橋問題：從家里出發(fā)，七座橋每橋恰通過一次，再回到家里，是否可能？Euler把兩座小島分別用v1，v2兩點來表示，兩岸的陸地用v2，v4來表示，兩地之間的橋用線段表示，于是得到了圖2.Euler將圖2這種圖形稱為圖.圖1：哥尼斯堡七橋問題圖2：哥尼斯堡七橋圖示內容提要4.1節(jié)圖與有向圖圖的定義圖的類型平凡圖有環(huán)圖簡單圖頂點與邊的關系相鄰關聯(lián)頂點的度數(shù)圖的基本定理路徑相關概念通道跡路徑圈子圖、生成子圖、導出子圖、極大連通圖有向圖圖4.1.1一個有限圖4.1.1圖與度序列

圖4.1.1一個有限圖

圖4.1.1一個有限圖

注：每個圖都有一個度序列.反之，并非每個遞減序列都為某個圖的度序列.

4.1.2路徑與連通

圖4.1.2一個不連通圖

圖4.1.2一個不連通圖

子圖生成子圖導出子圖

定義4.1.4圖??的連通分支(connectedcomponent)是指其極大連通子圖.圖??的割點(cut-vertex)(割邊(cut-edge))是指一個頂點(一條邊)且刪除它會增加連通分支的數(shù)目.圖4.1.2一個不連通圖

圖4.1.3有向圖THANKS感謝觀看第4.2節(jié)樹的性質離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025內容提要4.2節(jié)樹的性質樹的定義樹的性質生成樹Cayley公式4.2.1樹的定義及刻畫定義4.2.1一個森林(forest)是指一個無圈圖.一棵樹(tree)是指一個連通的森林.度為1的頂點稱為葉子(leaf).若一個圖的生成子圖是一棵樹,則稱該樹是圖的生成樹(spanningtree).例4.2.1

給西安電子科技大學的所有學生編排學號時形成一棵樹.以01,02,03…表示學院；以10,11,12…表示入學年份為2010,2011,2012…,以1,2,3…表示學院的專業(yè)；以001,002,003,…表示各專業(yè)的學生，結果如圖4.2.1所示,樹中的每個葉子表示一個學生.例如頂點為010的葉子所表示的學生的學號可記為07132010,表示該學生是07學院13級2專業(yè)第10號.圖4.2.1學號樹

4.2.2Cayley公式

圖4

2、3、4個頂點構成樹的圖示

123452314611555度數(shù)為1的頂點不出現(xiàn)在編碼中;頂點在編碼中出現(xiàn)的次數(shù)為度數(shù)減1.圖4.2.2

樹及其Prüfer編碼

THANKS感謝觀看第4.3節(jié)根樹及其應用離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025內容提要4.3節(jié)根樹及其應用根樹的定義及其表示樹高頂點的孩子頂點的后代m元樹(m-ary)完全m元樹二叉樹Huffman算法二叉搜索樹決策樹4.3.1Huffman算法

圖4.2.1學號樹圖4.3.1樹及其根樹表示

樹高為2

3元樹，但不是完全3元樹例：假設傳輸一組數(shù)據(jù)：45533322211110000000.因為ASCII編碼規(guī)定每個字符（包括數(shù)字字符）都占用8位，所以直接傳輸共需

20×8=160位.

解：按照Huffman算法得到的二叉樹如圖4.3.2所示，所以0,1,2,3,4,5的最優(yōu)前綴編碼分別為：0:1;1:011;2:010;3:001;4:0000;5:0001數(shù)字5所需位數(shù)：2×4=8；數(shù)字4所需位數(shù)：1×4=4；數(shù)字3所需位數(shù)：3×3=9；數(shù)字2所需位數(shù)：3×3=9；數(shù)字1所需位數(shù)：4×3=12；數(shù)字0所需位數(shù)：7×1=7.共需要：4+8+9+9+12+7=40位.圖4.3.2編碼樹4.3.2二叉搜索樹和決策樹

圖4.3.3二叉搜索樹圖4.3.3二叉搜索樹

圖4.3.3(a)中給出了一棵完全二叉搜索樹.各頂點的賦值為1,2,...,7.例如，搜索7,先是和4比較,7大于4故而和4的右孩子比較,7又大于6,故再和6的右孩子比較,這樣用了3步就找到了7.如果按照列表1,2,3,...,7則需要7步.

圖4.3.4決策樹

THANKS感謝觀看第4.4節(jié)最小生成樹和最短路徑離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025內容提要4.4節(jié)最小生成樹和最短路徑最小生成樹Kruskal算法Prim算法最短路徑Dijkstra算法4.4.1最小生成樹

加權圖或網絡(weightedgraph,ornetwork)是各邊都標有數(shù)值(稱為邊的權值,我們只考慮非負實數(shù)情形)的圖.一個圖的權是圖中各邊的權之和.最小生成樹問題就是給定一個加權連通圖,尋找一個權值最小的生成樹.圖4.4.1一個加權連通圖

圖4.4.1Kruskal算法產生的生成樹

注：一個加權連通圖的最小生成樹不是唯一的.

Prim算法：從某一頂點出發(fā),將訪問過的頂點和未訪問過的頂點之間的權值最小的邊添加進來,直到所有頂點已被訪問.圖4.4.1一棵連通圖從中間頂點開始.4.4.2最短路徑問題

例4.4.1加權連通圖如圖4.4.2(a)所示，求頂點a到各個頂點的最短路徑長度.圖4.4.2一個加權連通圖(a)(b)12322326433646464655565表4.4.1Dijkstra算法迭代情況THANKS感謝觀看第4.5節(jié)歐拉圖和哈密頓圖離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025內容提要4.5節(jié)歐拉圖和哈密頓圖歐拉圖歐拉跡歐拉回路歐拉跡存在的充要條件哈密頓圖哈密頓圈哈密頓圖的充分和必要條件4.5.1歐拉圖哥尼斯堡七橋問題：從家里出發(fā)，七座橋每橋恰通過一次，再回到家里，是否可能？(一筆畫問題)圖4.5.1哥尼斯堡七橋圖示人們經過多次實驗,都給出了否定的答案,但都未能嚴格證明.1736年,歐拉徹底的解決了這個問題,這一年也被認為是圖論的元年.歐拉用頂點來表示陸地,兩個頂點之間邊的數(shù)目等于兩個陸地之間橋的數(shù)目，于是得到了圖4.5.1(右).這樣問題就轉化為此圖中是否存在一條包含所有邊的閉跡1?

4.5.2哈密頓圖

19世紀,哈密頓爵士發(fā)明了一種游戲:給定正十二面體的一個頂點,找出從此頂點出發(fā)經其它頂點僅一次又回到出發(fā)頂點的路徑.如圖4.5.3所示，正十二面體確定了一個有20個頂點,30條邊的圖.圖4.5.3正十二面體的圖示哈密頓圖與旅行商問題密切相關.在旅行商問題中，旅行商需要在多個城市之間旅行，每個城市只訪問一次，最終回到出發(fā)城市.這個問題是經典的優(yōu)化問題，哈密頓回路就是旅行商問題中的一種解.電路設計：在電路設計中，哈密頓回路可用于優(yōu)化電路的布局和布線，減少布線的長度和交叉.

圖5一些哈密頓圖

上述定理中的條件不是充分的.例4.5.1圖4.5.4中的圖稱為Petersen圖(這兩個圖是Petersen圖的不同畫法,它們是同構的,頂點的標號給出了同構映射).Petersen圖滿足上述條件,下面來說明Petersen圖不是哈密頓圖．圖4.5.4Petersen圖的兩種圖示

THANKS感謝觀看第5章再論圖論離散數(shù)學配套教材：李小南目錄CONTENTS6.16.26.36.46.5二部圖最大匹配及穩(wěn)定匹配圖的連通性平面圖圖的頂點著色6.1二部圖

二部圖和匹配有工作申請者和n項工作,每項工作最多由一個人來做且每個人可接受的工作有若干種,能否有一種工作安排方案,使得n個人都能得到自己滿意的工作?可以用圖對這一問題建立模型:圖的頂點分別為申請者和工作,若人a滿意工作j,就用一條邊連接a和j.這樣問題就變?yōu)槭欠窨梢哉页鰊條相互之間無公共頂點的邊.上述模型中圖的頂點集可以分為兩個集合,使得每個集合中的頂點互不相鄰,這樣的圖稱為二部圖,模型中需要尋找的相互無公共頂點的邊集稱為圖的匹配.

定理5.1.1(k?nig,1936)一個圖是二部圖當且僅當它不含奇圈.證明：必要性.二部圖中的閉合通道都是從某個部集出發(fā)往返于兩個部集間最后再回到出發(fā)的部集,經過了偶數(shù)步,也即二部圖的閉合通道都是偶數(shù)長的.故二部圖不含奇圈.定理5.1.1(k?nig,1936)

一個圖是二部圖當且僅當它不含奇圈.

定理5.1.1(k?nig,1936)

一個圖是二部圖當且僅當它不含奇圈.證明：充分性.

頂點覆蓋

街道上需要有警察來維持治安,假設交叉路口的警察可以監(jiān)管和路口相連的街道,我們往往關心最少安排多少警察可以監(jiān)管整個街道網絡？把上面問題抽象成圖論中的模型,我們就有了下面頂點覆蓋的概念.

在左圖中，等式成立,而右圖中最小頂點覆蓋大小為3,而最大匹配大小為2.注意左圖為二部圖,其實我們有定理5.1.3定理5.1.3(K?nig-Egerváry,1931)設G是(X,Y)-二部圖,則G的最大匹配的大小等于G的最小頂點覆蓋的大小.

定理5.1.3(K?nig-Egerváry,1931)設G是(X,Y)-二部圖,則G的最大匹配的大小等于G的最小頂點覆蓋的大小.

Hall定理有許多證明方法,我們這里利用K?nig-Egerváry定理證明了Hall定理,也可利用Hall定理證明K?nig-Egerváry定理.另外,Hall定理告訴我們可以通過的某些子集的鄰域頂點太少來說明不存在浸潤(X,Y)-二部圖中部集X的匹配.最后我們指出匹配理論是組合數(shù)學及最優(yōu)化學科中最經典且最為重要的內容之一,在諸多領域有著廣泛應用.關于匹配理論更多的介紹可參考由L.Lovász和M.Plummer編著的

MatchingTheory一書.第6.2節(jié)最大匹配及穩(wěn)定匹配離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025最大匹配由上節(jié)，我們知道對于一個二部圖中的匹配M來說,若圖中沒有M增廣路徑,則M就是最大匹配了.這就為我們提供了一種求最大匹配的方法.設M是(X,Y)-二部圖G中的一個給定的匹配(可以是空集),如果M不是最大匹配,則一定存在一條M增廣路徑,此路徑一定是從未被M浸潤的X中頂點出發(fā)并終止于Y中未被M浸潤的頂點的M交錯路徑.

輸入:

(X,Y)-二部圖.G的一個匹配M,U=X-V(M).

例5.2.1考慮圖(a)中的二部圖.二部圖的一個匹配用粗邊M給出.下面就利用最大匹配算法從此匹配開始尋找一個最大匹配.(a)(b)

(a)(b)(c)(d)

(c)(d)

注5.2.1兩種擴展另一種擴展是尋找加權二部圖中的權值最大的匹配.Kuhn(1955)解決了這個問題(由于K?nig和Egerváry的工作是上述算法的基礎,為了紀念這兩位匈牙利數(shù)學家,Kuhn把此算法稱為匈牙利算法).注5.2.1兩種擴展穩(wěn)定匹配

Gale-Shapley算法:每個男士(女士)按照喜好順序給每個女士(男士)排序.最喜歡的排在第一位,依次排列.每位男士向排在第一位的女士求婚.某個女士若有多個追求者,則該女士與她的排序最前面的男士訂婚.若某個女士只有一個追求者,則訂婚.若所有男士都訂婚,則算法終止.剩下的男士(即還沒有訂婚者)繼續(xù)向排在第二位的女士求婚.每位女士在新求婚者,未婚夫(如果在上一步已訂婚)中尋找排序最前面的男士訂婚.繼續(xù)上面的過程,即還未訂婚的男士向還未追求過的最喜歡的女士求婚.而每位女士在新求婚者,未婚夫(如果已訂婚)中尋找排序最前面的男士訂婚.若每個男士都已訂婚(當然同時每位女士也已訂婚)時,算法終止.

注:算法每個階段分二步,一是男士求婚,二是女士選擇;每一階段,都有可能某位女士沒有一人追求,因此也不用做出選擇;女士可以悔婚,也即在上一步已經訂婚,下一步若遇到更心儀的追求者,可以和后者訂婚,和上一步的訂婚者悔婚.Gale-Shapley算法例5.2.2假設有4個男士和4個女士,他們之間的喜好程度由下表給出.現(xiàn)在我們來說明Gale-Shapley算法怎么給出一個穩(wěn)定匹配.

注5.2.2每個穩(wěn)定婚姻問題中存在穩(wěn)定匹配且穩(wěn)定匹配未必唯一.若將Gale-Shapley算法變?yōu)榕壳蠡?則得到的穩(wěn)定匹配和男士求婚的穩(wěn)定匹配未必一樣.且男士或女士求婚的Gale-Shapley算法只能找到所有穩(wěn)定匹配中的兩個.利用Gale-Shapley算法可能得到兩個穩(wěn)定匹配,那么這兩個穩(wěn)定匹配在所有穩(wěn)定匹配中的“地位”怎么樣?或者說這兩個穩(wěn)定匹配和其它穩(wěn)定匹配(如果有的話)的關系如何?為了回答這個問題,我們先介紹幾個概念.

類似可定義男士最差的穩(wěn)定匹配、女士最優(yōu)穩(wěn)定匹配、女士最差穩(wěn)定匹配.注5.2.2:男士最優(yōu)穩(wěn)定匹配是女士最差穩(wěn)定匹配;女士最優(yōu)穩(wěn)定匹配是男士最差穩(wěn)定匹配男士求婚的Gale-Shapley算法產生的穩(wěn)定匹配是男士最優(yōu)穩(wěn)定匹配,女士求婚的Gale-Shapley算法產生的穩(wěn)定匹配是女士最優(yōu)穩(wěn)定匹配.注5.2.2:對于男士的“優(yōu)于”關系是所有穩(wěn)定匹配集合上的一個偏序關系,其實所有的穩(wěn)定匹配在此偏序關系下是一個格.格的最大元是男士最優(yōu)穩(wěn)定匹配,最小元是男士最差穩(wěn)定匹配.對于女士的“優(yōu)于”關系也有類似的結果.

最后我們需要指出我們討論的穩(wěn)定婚姻問題有相當大的局限性,比如男士和女士人數(shù)相等,每一個人要選擇與其性別相反的人并且是一選一,等等.但實際中往往沒有這些限制,比如師范院校學生申請實習學校,首先學生人數(shù)和學校數(shù)量不必相同,其次一個學校一般也可接收多個實習生，因此很有必要去討論穩(wěn)定婚姻問題的若干變形.對穩(wěn)定匹配及各種擴展感興趣的讀者可以參考由D.Gusfiedl和R.W.Irving編著的Thestablemarriageproblem:structureandalgorithms一書.值得一提的是,Gale-Shapley算法的提出者之一、著名數(shù)學家、加州大學洛杉磯分校的Shapley教授因在博弈論領域的杰出貢獻而獲得了2012年諾貝爾經濟學獎.第6.3節(jié)圖的連通性離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025連通度不同圖的連通“程度”可能是不同的,有的連通圖(例如完全圖),刪除一些頂點(或邊)后還是連通的;有些連通圖,刪除一個頂點(或邊)就不連通了(例如圈).本節(jié)我們就來研究圖的連通“程度”

前面我們通過刪除頂點來定義連通度,下面我們通過刪除邊來定義連通度.

Menger定理前面我們用任意兩個頂點間有路徑相連來定義連通圖,而兩個頂點間的不同路徑越多,圖的連通程度似乎就越高.下面說明通過這種方式定義連通程度本質上和前面刪除頂點的定義方式是等價的.

推論5.3.2

多于兩個頂點的圖是2-連通圖當且僅當中的任意兩個邊都在某一個圈上.下面我們把定理5.3.2推廣到一般的-連通圖,就得到了經典的Menger定理.由于證明較繁,我們這里略去(可參考[1,2,5]).先來介紹一個概念.

連通度

第6.4節(jié)平面圖離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025歐拉定理及應用定義5.4.1一個圖G可以圖示在平面上,使得任何兩邊除了頂點外無公共交點,則稱圖G是可平面圖(planargraph).G的這種圖示也稱為G的一個平面嵌入(planarembedding).一個平面圖(planegraph)是指一個可平面圖的一個特定的平面嵌入.平面圖將平面分成許多區(qū)域,這些由邊圍成的區(qū)域稱為面(face).

注歐拉定理最早是以凸多面體形式給出的.雖然我們是在圖論部分給出的歐拉定理,但還是要指出歐拉公式實際上反應了一種拓撲性質.而歐拉定理的推廣也是拓撲學中非常重要的結論之一.拓撲學和圖論有著密切的聯(lián)系,前面提到的圖論起源問題的格尼斯堡七橋問題也被認為是拓撲學的起源.關于歐拉定理的精彩介紹推薦讀者參閱:王敬庚,直觀拓撲(第三版).北京:北京師范大學出版社,2010.另外對拓撲學感興趣的同學,推薦:M.A.Armstrong,BasicTopology,Springer,1983(有中譯本).該書從歐拉定理開始,對拓撲學有引人入勝的介紹.

利用歐拉定理,我們可以給出平面圖邊數(shù)的一個上界

可平面圖的刻畫

例5.3.2證明:Peterson圖(左圖)不是可平面圖.

例5.3.2證明:Peterson圖(左圖)不是可平面圖.

第6.5節(jié)圖的頂點著色離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025學校安排補考,需要將有同一個學生參加的兩門課安排在不同時間.將各門課程作為圖的頂點,若某個學生需要補考兩門課程,則將這兩門課程對應的頂點用邊相連.我們給這樣的圖中每個頂點賦予某種顏色,使得相鄰頂點的顏色不同,則安排考試需要的時間段的最小值等于對圖中頂點進行著色的最少顏色數(shù).計算機在循環(huán)內計算時把頻繁使用的變量的值存儲于中央處理器的寄存器中而不是內存中,這樣做便于快速訪問數(shù)據(jù)從而提高效率.如果兩個變量在不同時刻使用,則可以分配給它們同一個寄存器.定義一個圖,其頂點就是變量,兩個頂點相鄰當且僅當對應的兩個變量在某時刻同時使用,則變量所需要的寄存器的最少個數(shù)等于給圖中頂點著色使得相鄰頂點的顏色不同所需的最少顏色數(shù).類似的還有裝箱問題:有些貨物裝在同一個箱子里面不安全,給定一些貨物,至少需要多少個箱子來裝?這些問題都和圖的頂點著色有關,下面給出圖的頂點著色的定義.頂點著色的定義和性質

例5.5.1左圖是Peterson圖.因為Peterson圖中含有奇圈,故Peterson圖不是二部圖,因此Peterson圖的色數(shù)至少為3.左圖給出了Peterson圖的3種顏色的頂點著色方案（標相同字母的頂點著相同的顏色）,這就說明Peterson圖的色數(shù)為3.右圖為Gr?tzsch圖,圖中給出了4中顏色的著色方案（標相同字母的頂點著相同的顏色）,不難驗證用3種顏色不可能給Gr?tzsch圖著色,故此圖的色數(shù)為4.頂點著色的定義和性質

貪婪著色：怎么給一個圖進行頂點著色?下面我們介紹一種稱之為貪婪著色的方法.用1,2,3,…等正整數(shù)來表示顏色.

四色問題四色問題的最初形式是:能否用4種顏色給任意平面區(qū)域著色,使得有公共邊的相鄰區(qū)域有不同的顏色(參見左圖).給每個區(qū)域放置一個頂點,兩個區(qū)域有公共邊的話在這兩個相應頂點間添加一條通過公共邊的連線,這樣就得到了一個平面圖(其實是平面區(qū)域的對偶圖).這樣對平面區(qū)域(或地圖)的著色問題就轉變?yōu)榱藢ζ矫鎴D的頂點著色問題(參見右圖).四色問題始于19世紀50年代,經過漫長的發(fā)展出現(xiàn)了很多接近正確的結果。值得一提的是AlfredKempe(1849-1922)于1879年發(fā)表的“證明”.這或許是數(shù)學中最有名的錯誤證明.這名律師的證明在11年后的1890年被他的同胞P.J.Heawood(1861-1955)指出了錯誤.但是Kempe的證明思路卻是100年后K.Appel和W.Haken完成的計算機輔助證明的基礎.最終K.Appel和W.Haken在1976年利用計算機成功給出了證明,但是一些數(shù)學家期待的不使用計算機的常規(guī)證明仍沒有出現(xiàn).定理5.5.3平面圖的著色數(shù)不超過4.定理5.5.4(Heawood,1890)所有可平面圖都是可5著色的.

定理5.5.4(Heawood,1890)所有可平面圖都是可5著色的.

定理5.5.4(Heawood,1890)所有可平面圖都是可5著色的.

定理5.5.4(Heawood,1890)所有可平面圖都是可5著色的.第六章代數(shù)結構離散數(shù)學配套教材：李小南目錄CONTENTS6.16.26.36.46.5代數(shù)系統(tǒng)子群和商群循環(huán)群和對稱群群同態(tài)及應用環(huán)和域6.1代數(shù)系統(tǒng)

6.1.1

代數(shù)運算數(shù)、矩陣、函數(shù)、向量、多項式等交換律、結合律、分配律等定義6.1.1設X是一個集合，則到X的一個映射“”稱為X上的一個代數(shù)運算或二元運算.例6.1.1設，定義，則是上的二元運算.定義6.1.2設X是一個集合，則到X的一個映射“”稱為X上的一個n元運算.例6.1.3()和()都是代數(shù)系統(tǒng).定義6.1.3設X是一個集合，X及其上的若干個代數(shù)運算一起稱為一個代數(shù)系統(tǒng).定義6.1.4集合X到自身的映射稱為X的一個變換，若此映射是單射（滿射或雙射），則稱此變換是單射變換（滿射變換或雙射變換）.每個元素與自身對應的變換顯然是一個雙射變換，稱為恒等變換.定義6.1.5有限集X

=

{1,2,…,n}的雙射變換稱為一個置換.上面的常用符號表示為顯然集合X的置換和X的排列是一一對應的，故X共有P(n,n)=n!個置換.例如當n=3時，X={1,2,3}共有6個置換，分別為分別用T(X)和S(X)表示X上的所有變換和置換構成的集合，定義它們上的運算為映射的合成，即，表示兩個映射的合成，稱為變換的乘法.我們通常省去運算符，僅記為.進而，我們可以稱代數(shù)系統(tǒng)T(X)和代數(shù)系統(tǒng)S(X).兩個例子如下：映射的概念使兩個集合聯(lián)系了起來，對于代數(shù)系統(tǒng)來說，我們希望映射能夠“保持運算”.定義6.1.6設和是兩個代數(shù)系統(tǒng)，f是X到Y的一個映射.如果，有，則稱f是兩個代數(shù)系統(tǒng)之間的同態(tài)映射.同態(tài)的雙射稱為同構映射.如果兩個代數(shù)系統(tǒng)之間存在同構映射，則稱兩個代數(shù)系統(tǒng)是同構的.定義6.1.7設X是非空集合，和是X上的兩個二元運算，如果(1)交換律，.(2)結合律，(3)吸收律,成立，則稱是一個格.并運算(最小上界)交運算(最大下界)定義6.1.8，若格滿足分配律：則稱是分配格.若格中存在，使得則稱是有界格.對于有界格，若X上的一元運算′滿足則稱是有補格，稱為x的補.6.1.2

格和群例6.1.4設X={a,b,c,d},X上的兩個二元運算和的定義分別如下：可以驗證，是一個格.定義偏序關系為：于是有，因此格的Hasse圖如下圖所示.考慮X上的一元運算，如下表所示：可驗證此一元運算是X上的補運算(0=a,1=d).另外，容易驗證是分配格.定義6.1.9如果X上的兩個二元運算和和一元運算′滿足定義6.1.7和定義6.1.8中的所有條件，則稱代數(shù)系統(tǒng)′為布爾代數(shù)(或布爾格).定義6.1.10設f是布爾代數(shù)′和′之間的一個雙射，如果f保持并、交和補運算，即則稱f是布爾代數(shù)′和′之間的一個同構映射，稱這兩個布爾代數(shù)是同構的.例6.1.6設Y={1,2},考慮冪集格(參考例1.4.5)，顯然例6.1.4中的布爾代數(shù)′和布爾格是同構的(參考書第171頁圖6.1.1).注意若按照代數(shù)系統(tǒng)的表示方法，應該記為

，其中分別表示集合的并、交、補運算.定義6.1.11設是一個代數(shù)系統(tǒng)，若二元運算滿足(1)結合律：(2)單位元：存在，使得(3)逆元：存在，使得對于群X，若|X|=n(n為正整數(shù))，則稱X為有限群，且稱n為群X的階；否則稱其為無限群.例6.1.7代數(shù)系統(tǒng)結合律單位元逆元交換律是否構成群√0?x√交換群√11/x√交換群√1

√不是群√

√不是群則稱是一個群.定義中的e稱為群的單位元，稱為x的逆元.若還滿足(4)交換律：則稱是一個交換群或Abel群.幺半群半群例6.1.10

(一般線性群)

和分別是全體n×n實可逆矩陣和全體n×n實矩陣構成的集合.代數(shù)系統(tǒng)結合律單位元逆元交換律是否構成群√零矩陣√√交換群√單位矩陣

幺半群√零矩陣√√交換群√單位矩陣√

一般線性群注意這里的可換為復數(shù)域或有理數(shù)域.例6.1.11

(n次單位根群)所謂n次單位根是指方程的n個復數(shù)解，所有n次單位根及復數(shù)的乘法運算構成一個交換群，稱為n次單位根群.例6.1.12

(n元對稱群)考慮集合X(|X|=n)的所有置換構成的代數(shù)系統(tǒng).設是X的一個置換，則的逆映射和復合就是恒等變換.因為映射的復合滿足結合律，所以集合X上的所有置換構成一個n元對稱群，記為.n元對稱群的子群稱為置換群，我們以為例.X={1,2,3}共有6個置換，分別為以為例，它把2變?yōu)?，把3變?yōu)?，稱其為一個2-輪換.由于1在作用下未變，因此可以用(23)表示這個置換.類似地，用(12)表示，(123)表示，(132)表示，(13)表示，而恒等置換就簡單表示為(1).當然這樣的表述法不唯一，例如.THANKS感謝觀看第6.2節(jié)子群和商群離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025定義6.2.1設是一個群，Y是X的一個子集.如果也是Y上的代數(shù)運算且滿足群的定義，則稱是的子群，記為.任何一個群X至少有兩個子群：一個是X本身，另一個是單位元構成的子群{e}.這兩個群稱為平凡子群，其余子群稱為非平凡子群.定理6.2.1設Y是X的一個子群，則子群Y的單位元就是群X的單位元，Y中元素a在Y中的逆元就是a在X中的逆元.例6.2.1整數(shù)及普通加法構成一個交換群，稱為整數(shù)加群.設是全體偶數(shù)構成的集合，則是整數(shù)加群的子群.正整數(shù)集合不是整數(shù)加群的子群，因為沒有單位元0，且元素沒有逆元.6.2.1

子群證明

設e′是子群Y的單位元，e是群X的單位元，則e′e′=e′=e′e，

于是由消去律可得e′=e.

同樣，設a′是a在Y中的逆元，是a在X中的逆元，則

由消去律可得a′=.定理6.2.2群X的一非空子集Y構成子群的充要條件是：(1)(2)證明

必要性.設Y是X的子群，則X的代數(shù)運算也是Y的代數(shù)運算，因此當

時有，另外，由定理6.2.1可知，當時有.

充分性.設Y滿足(1)與(2)兩個條件，則(1)說明X的代數(shù)運算也是Y的

代數(shù)運算，結合律在X中成立自然在Y中也成立，又根據(jù)(2)，當

時，結合(1)可得，即Y中有單位元e，且每個元素

都有逆元，因此Y是X的一個子群.定義6.2.2設Y是X的一個子群，，則稱集合為群X關于子群Y的一個左陪集；稱集合為群X關于子群Y的一個右陪集.例6.2.2如例6.2.1所示，是整數(shù)加群的子群，有上例中，，因為整數(shù)加群是交換群.一般情況下，左右陪集未必相等.例6.2.3考慮3元對稱群，Y={(1),(12)}是的一個子群.因為(13)(12)=(123)，而(12)(13)=(132)，所以不是交換群.又有所以.定理6.2.3設Y是X的一個子群，則是X的一個劃分.證明

由于，有，故只需證明若，則.

設，下證cY=aY.

設c=ay()，則cY

=

ayY

=

aY

(由于Y是子群，，有，故

易得ayY=a(yY)

=aY).同理可證cY=bY.因此aY=bY.例6.2.4Y={(1),(12)}是的一個子群，且有故共有3個不同的左陪集構成了的一個劃分.定義6.2.3群X關于子群Y的不同的左陪集的個數(shù)稱為Y在X里的指數(shù)，記為(X:Y).根據(jù)定義可知，當然指數(shù)也可能無限.定理6.2.4

(拉格朗日定理)設Y是X的一個子群，則證明

令(X:Y)=s，則(?)是X關于Y的左陪集構

成的X的一個劃分.易知是左陪集到的一個雙射，從而.于是有因此由式(?)可知，即.定義6.2.4設x

是群X

中的一個元素，則滿足的最小正整數(shù)n稱為x的階.如果這樣的最小正整數(shù)不存在，則稱x

的階為無限.例如，整數(shù)加群中所有非零元素的階都為無限，中(12)的階為2，(123)的階為3.推論6.2.1有限群中每個元素的階都整除群的階.注意這里，即n個x相乘.這里說“相乘”是因為群里的代數(shù)運算我們一般稱為“乘法”，當然對于不同的群，具體運算規(guī)則是不同的.同時規(guī)定證明

設x是有限群X中的一個n階元素，則是X的一個n階子群.由拉格朗日定理可知.定義6.2.5設Y是X的一個子群，如果，都有xY=Yx，則稱Y是X的正規(guī)子群，記為由于交換群的左、右陪集都相等，因此交換群的子群都是正規(guī)子群.例6.2.5由例6.2.3可知，{(1),(12)}是的一個子群，但不是正規(guī)子群.類似地，{(1),(13)}，{(1),(23)}也都不是的正規(guī)子群，而{(1),(123),(132)}是的正規(guī)子群.定義6.2.6設Y是X的一個正規(guī)子群，對任意的兩個陪集xY和zY，定義(xY)(zY)=(xz)Y6.2.2

商群上述定義的陪集的運算滿足結合律，單位元為eY=Y，xY的逆元為

，因此全體陪集及上面定義的運算構成了一個群，記為X/Y，稱為X關于正規(guī)子群Y的商群.例6.2.6由例6.2.5可知，{(1),(123),(132)}是的正規(guī)子群，設Y={(1),(123),(132)}，則關于Y的商群，Y為單位元.THANKS感謝觀看第6.3節(jié)循環(huán)群和對稱群離散數(shù)學講授：李小南配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，20256.3.1

循環(huán)群設Y是群X的一個非空子集，則Y未必是X的子群，但是包含Y的所有子群的交仍是X的子群，稱為由Y生成的子群，記為.顯然是X中包含Y的最小子群，Y也稱為的生成系.

由一個元素x生成的群X稱為循環(huán)群，記為，x也稱為的生成元.若群中運算用乘法表示，則即中的任意元素可以寫為(k為整數(shù));若群中運算用加法表示，則即中的任意元素可以寫為kx(k為整數(shù)).例6.3.1整數(shù)加群是無限循環(huán)群，1為其生成元.即也就是說整數(shù)加群中任何一個元素都可以通過1和加法生成.例6.3.2設n為正整數(shù)，整數(shù)加群的加法子群也是一個循環(huán)群.因為中的任何元素kn都可以通過n和加法生成，即循環(huán)群的生成元為n.也是一個無限循環(huán)群.方程的n個復數(shù)解，具體為例6.3.3n次單位根群是一個循環(huán)群.回憶例6.1.11中的n次單位根是指由復數(shù)乘法可得，即任意n次單位根都可以由

的冪運算生成.因此是生成元，n次單位根群是n階循環(huán)群.例6.3.4素數(shù)階群是循環(huán)群.設x是素數(shù)階群X(|X|=p)中的元素，由拉格朗日定理的推論可知，x的階為1或p，故是X中的不同元素.因此為循環(huán)群.證明

設Y是循環(huán)群的任一子群.當Y={e}時，顯然Y是循環(huán)群.定理6.3.1循環(huán)群的子群仍是循環(huán)群.下設Y≠{e}.由于當時必有，故可設為Y中a的最小正冪，于是有.另一方面，任取，令因為是Y中a的最小正冪，所以r=0.從而由式(?)可知由于，故有(?)于是又有因此定理6.3.2(1)無限循環(huán)群有無限多個子群.(2)設是n階循環(huán)群,則對n的任意正因子k(即且k|n)，X只有一個k階子群，這個子群就是.證明

(1)設，則易知是X的全部互不相同的子群，且除e外都是無限循環(huán)群，從而彼此同構.(2)設，k|n且n=kq(Ⅰ)，則，因此是X的一個k階子群.設Y也是X的一個k階子群，根據(jù)定理6.3.1可設，則.又由習題可知的階是，故，式中，(m,n)為m與n的最大公因數(shù).由式(Ⅰ)與(Ⅱ)得q=(m,n)且q|m，從而(Ⅱ)由于與的階相同，故即的k階子群是唯一的.由于，所以{}對乘法是封閉的，即變換乘法（復合映射）是{}的代數(shù)運算，乘法運算的結合律成立，單位元為，兩個元素的逆元就是自己，因此{}是X的變換群.但由于和

都不是雙射變換，故此變換群不是置換群.6.3.2

對稱群集合X的一些變換關于變換的乘法構成的群稱為變換群；X的全體雙射變換（即置換）構成的群稱為對稱群；若|X|=n，則稱全體雙射變換（即置換）構成的群為n元對稱群，記為.定義6.3.1n元對稱群的子群稱為置換群.由定義可知，是置換群，而置換群是變換群.下面給出的例子是變換群而不是置換群.例6.3.5設X={1,2,3,4}，考慮兩個變換4元對稱群中有4!=24個元素，每個輪換都可以表示為對換的乘積，但表示法未必唯一.如(123)=(13)(12)=(13)(32)(32)(12)(1234)=(34)(13)(23)=(23)(13)(23)(13)(14)前面已經指出，中的元素可分別記為(12)和(123).(12)是把1變成2，把2變成1；(123)是把1變成2，把2變成3，把3變成1，這樣的變換稱為輪換.我們可以用(

)表示一個輪換，m稱為輪換的長.長為1的輪換就是恒等變換，長為2的輪換稱為對換；沒有公共元素的若干輪換稱為不相交輪換.定理6.3.3每個置換（非輪換）都可以表示為不相交輪換的乘積；每個輪換都可以表示為對換的乘積.注意由上述定理可知，每個置換都可以表示為對換的乘積.例6.3.6雖然同一置換表示為對換的乘積時有不同的方法，但是各種方法中對換個數(shù)的奇偶性卻相同.我們有下面的定理.定理6.3.4每個置換表示為對換的乘積時，對換個數(shù)的奇偶性不變.這樣我們就可以把置換分為奇置換和偶置換.(123)是偶置換，(1234)是奇置換.有n!個元素，由于奇置換和偶置換的個數(shù)一樣多，故奇置換和偶置換各有n!/2個.的所有偶置換關于置換的乘法構成一個群，稱為交錯群，記為.和分別為例6.3.7為的正規(guī)子群.設，下面說明.若是偶置換，例6.3.8等式顯然成立.若為奇置換，則有.由于恒等置換也是偶置換，而是奇置換，所以是奇置換.因此對任意，是偶置換，即，故，這就說明了.類似可說明.因此，.沒有非平凡正規(guī)子群的群稱為單群，即單群的正規(guī)子群只有子群{e}和其自身.由拉格朗日定理可知，素數(shù)階群都是單群.我們知道素數(shù)階群是循環(huán)群，從而是交換群.對于有限非交換群，下面的結論指出交錯群是單群.定理6.3.5(n>5)是單群.這里需要指出的是，伽羅瓦利用上述結論證明了五次以上多項式沒有求根公式.THANKS感謝觀看第6.4節(jié)群同態(tài)及應用離散數(shù)學配套教材：李小南，易黃建，喬勝寧，離散數(shù)學，電子工業(yè)出版社，2025講授：李小南6.4.1

群同態(tài)基本定理本節(jié)我們假設X和是兩個群，其單位元分別為e和.定義6.4.1設X和是兩個群，f

是X到的映射.如果f

保持群運算，即則稱f是X到的群同態(tài)（簡稱為同態(tài)）.如果同態(tài)f是滿射，則稱f為滿同態(tài)；如果同態(tài)f是單射，則稱f為單同態(tài)；如果同態(tài)f是雙射，則稱f為同構，并稱X和同構，記為.

，有f(ab)=

f(a)f(b)例6.4.1整數(shù)加群到自身的映射f:

n→2n

是同態(tài)映射，因為顯然這是一個單同態(tài)，但不是滿同態(tài).例6.4.2設Y是群X的正規(guī)子群，定義X和商群X/Y之間的映射由陪集的運算可得因此這是一個同態(tài)，且是一個滿同態(tài).群和它的商群同態(tài)同態(tài)映射有一些好的性質，如保持單位元、逆元等.定理6.4.1設f是群X到的群同態(tài)且，則(1)f(e)=.(2)f()=.(3)f()=，n為正整數(shù).設f

是群X到的群同態(tài)，則稱為同態(tài)f

的核；稱為同態(tài)f

的像.定理6.4.2imf

是的子群，kerf

是X的正規(guī)子群.證明

由于f(e)=，故imf

非空.設，由定義可知存在使得f(a)=，由于，故就是的逆.imf

是群的子集，故其元素的乘法滿足結合律.從而imf

是的子群.顯然kerf

是X的子群.下證ker

f

是正規(guī)子群.，只需說明根據(jù)對稱性，只需說明.，下證由于，故.設，因此.kerf

是X的正規(guī)子群，因此就有了商群X/ker

f.定理6.4.3(群同態(tài)基本定理)設f

是X到的群同態(tài)，則注意定理6.4.3中若是滿同態(tài)，則.群同態(tài)基本定理說明任意的同態(tài)的像就是商群，這個商群是由同態(tài)的核產生的.群同態(tài)基本定理的圖示如下.因此是n階循環(huán)群.設

，其中6.4.2

任意群和循環(huán)群的同構刻畫定理6.4.4任意的抽象群都同構于一個變換群；任意n階群都和的子群同構.定理6.4.5設是循環(huán)群，(1)若a的階為正整數(shù)n，則X與n次單位根群同構；(2)若a的階為無限，則X與整數(shù)加群同構.證明(1)由于a的階為正整數(shù)n，故為不同的元素.對于任意整數(shù)m，可寫為m=nq+r

，于是這顯然是一個同構映射，證畢.證明(續(xù))

(2)由于a的階為無限，令若，則.但a的階為