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

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

26個(gè)英文字母是一個(gè)集合，我國(guó)56個(gè)民族也是一個(gè)集合

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

確定性：集合中的元素是確定的，即一個(gè)元素要么屬于一個(gè)集合，要么不屬于這個(gè)集合互異性：集合中的元素都是不同的無(wú)序性：集合中的元素是沒(méi)有順序之分性質(zhì)：確定性、互異性和無(wú)序性

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

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

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

02關(guān)系的表示與復(fù)合關(guān)系的表示與復(fù)合

03關(guān)系閉包關(guān)系閉包

同時(shí)滿足上述三個(gè)性質(zhì)的關(guān)系稱(chēng)為等價(jià)關(guān)系。

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

等價(jià)關(guān)系與等價(jià)類(lèi)劃分粗糙集01等價(jià)關(guān)系與等價(jià)類(lèi)等價(jià)關(guān)系與等價(jià)類(lèi)定義1.3.1滿足自反性、對(duì)稱(chēng)性和傳遞性的關(guān)系稱(chēng)為等價(jià)關(guān)系。

02劃分劃分

由定理1.3.2可知，雖然劃分和等價(jià)關(guān)系的定義不同,但其實(shí)這兩個(gè)概念是描述同一情形的兩種不同方式。

粗糙集粗糙集

建立在等價(jià)關(guān)系基礎(chǔ)上的粗糙集理論于1982年由波蘭學(xué)者Pawlak提出,在機(jī)器學(xué)習(xí)、數(shù)據(jù)分析、決策科學(xué)等領(lǐng)域有著廣泛應(yīng)用。

信息表中有些信息是冗雜的，例如表1.3.1中的尺寸和位置這兩個(gè)屬性，對(duì)對(duì)象的分類(lèi)能力來(lái)說(shuō)是完全一樣的。因此對(duì)信息表進(jìn)一步處理之前，我們常常要簡(jiǎn)化信息表，即要對(duì)信息表進(jìn)行屬性約簡(jiǎn)，類(lèi)似的操作在機(jī)器學(xué)習(xí)中常常稱(chēng)為特征選擇。

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

最大元最小元

極小元極大元

02布爾格布爾格

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

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

(2)序?qū)Ρ硎痉?/p>

(3)向量表示法

(4)Zadeh表示法

03模糊集的運(yùn)算模糊集的運(yùn)算

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

兩個(gè)原理和排列加法原理

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

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

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

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

組合和二項(xiàng)式定理

Sperner定理

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

例2.2.5在6個(gè)人中,或者有3個(gè)人兩兩相互認(rèn)識(shí),或者有3個(gè)人兩兩相互不認(rèn)識(shí).

容斥原理

例2.2.6

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

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

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

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

性質(zhì)2.3.2

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

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

下面分情況討論具體計(jì)算問(wèn)題.

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

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

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

Cn012345678N112514421324291430

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

3.1.2聯(lián)結(jié)詞

通常用真值表來(lái)表示合取、析取這樣的復(fù)合命題的真值.真值表反映了命題所有可能組合對(duì)應(yīng)的復(fù)合命題的真值情況.合取和析取的真值表如下所示。0000010110011111

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

001110110010010111113.1.3條件命題

01011111011010011001011010101111

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

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

3.2.2重言式與矛盾式

00111011111000111011

0000110010110101110111111001111011111101111111113.2.3邏輯等價(jià)

0000000100010000111110011101111101111111

1110000101001001101000001111

11011100000111100111

（蘊(yùn)涵等價(jià)式）（結(jié)合律）（德·摩根律）（蘊(yùn)涵等價(jià)式）

（蘊(yùn)涵等價(jià)式）（德·摩根律）（交換律，結(jié)合律）（矛盾律）（零律）（蘊(yùn)涵等價(jià)式）（交換律）

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

3.3.2主范式

極小項(xiàng)二進(jìn)制數(shù)十進(jìn)制數(shù)二進(jìn)制表示十進(jìn)制表示000012103113

011000000100110010100001

00000011010001111001101111001111

000010001010010111011111100100101111110100111111

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

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

附加簡(jiǎn)化假言推理拒取式析取三段論假言三段論等價(jià)三段論構(gòu)造性二難推理破壞性二難推理

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

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

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

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

量化命題什么時(shí)候?yàn)檎媸裁磿r(shí)候?yàn)榧?/p>

3.5.2量化命題的邏輯等價(jià)式

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

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

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

圖4.1.1一個(gè)有限圖

圖4.1.1一個(gè)有限圖

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

4.1.2路徑與連通

圖4.1.2一個(gè)不連通圖

圖4.1.2一個(gè)不連通圖

子圖生成子圖導(dǎo)出子圖

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

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

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

4.2.2Cayley公式

圖4

2、3、4個(gè)頂點(diǎn)構(gòu)成樹(shù)的圖示

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

樹(shù)及其Prüfer編碼

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

圖4.2.1學(xué)號(hào)樹(shù)圖4.3.1樹(shù)及其根樹(shù)表示

樹(shù)高為2

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

20×8=160位.

解：按照Huffman算法得到的二叉樹(shù)如圖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編碼樹(shù)4.3.2二叉搜索樹(shù)和決策樹(shù)

圖4.3.3二叉搜索樹(shù)圖4.3.3二叉搜索樹(shù)

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

圖4.3.4決策樹(shù)

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

加權(quán)圖或網(wǎng)絡(luò)(weightedgraph,ornetwork)是各邊都標(biāo)有數(shù)值(稱(chēng)為邊的權(quán)值,我們只考慮非負(fù)實(shí)數(shù)情形)的圖.一個(gè)圖的權(quán)是圖中各邊的權(quán)之和.最小生成樹(shù)問(wèn)題就是給定一個(gè)加權(quán)連通圖,尋找一個(gè)權(quán)值最小的生成樹(shù).圖4.4.1一個(gè)加權(quán)連通圖

圖4.4.1Kruskal算法產(chǎn)生的生成樹(shù)

注：一個(gè)加權(quán)連通圖的最小生成樹(shù)不是唯一的.

Prim算法：從某一頂點(diǎn)出發(fā),將訪問(wèn)過(guò)的頂點(diǎn)和未訪問(wèn)過(guò)的頂點(diǎn)之間的權(quán)值最小的邊添加進(jìn)來(lái),直到所有頂點(diǎn)已被訪問(wèn).圖4.4.1一棵連通圖從中間頂點(diǎn)開(kāi)始.4.4.2最短路徑問(wèn)題

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

4.5.2哈密頓圖

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

圖5一些哈密頓圖

上述定理中的條件不是充分的.例4.5.1圖4.5.4中的圖稱(chēng)為Petersen圖(這兩個(gè)圖是Petersen圖的不同畫(huà)法,它們是同構(gòu)的,頂點(diǎn)的標(biāo)號(hào)給出了同構(gòu)映射).Petersen圖滿足上述條件,下面來(lái)說(shuō)明Petersen圖不是哈密頓圖．圖4.5.4Petersen圖的兩種圖示

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

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

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

一個(gè)圖是二部圖當(dāng)且僅當(dāng)它不含奇圈.

定理5.1.1(k?nig,1936)

一個(gè)圖是二部圖當(dāng)且僅當(dāng)它不含奇圈.證明：充分性.

頂點(diǎn)覆蓋

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

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

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

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

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

輸入:

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

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

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

(c)(d)

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

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

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

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

類(lèi)似可定義男士最差的穩(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算法產(chǎn)生的穩(wěn)定匹配是男士最優(yōu)穩(wěn)定匹配,女士求婚的Gale-Shapley算法產(chǎn)生的穩(wěn)定匹配是女士最優(yōu)穩(wěn)定匹配.注5.2.2:對(duì)于男士的“優(yōu)于”關(guān)系是所有穩(wěn)定匹配集合上的一個(gè)偏序關(guān)系,其實(shí)所有的穩(wěn)定匹配在此偏序關(guān)系下是一個(gè)格.格的最大元是男士最優(yōu)穩(wěn)定匹配,最小元是男士最差穩(wěn)定匹配.對(duì)于女士的“優(yōu)于”關(guān)系也有類(lèi)似的結(jié)果.

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

前面我們通過(guò)刪除頂點(diǎn)來(lái)定義連通度,下面我們通過(guò)刪除邊來(lái)定義連通度.

Menger定理前面我們用任意兩個(gè)頂點(diǎn)間有路徑相連來(lái)定義連通圖,而兩個(gè)頂點(diǎn)間的不同路徑越多,圖的連通程度似乎就越高.下面說(shuō)明通過(guò)這種方式定義連通程度本質(zhì)上和前面刪除頂點(diǎn)的定義方式是等價(jià)的.

推論5.3.2

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

連通度

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

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

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

可平面圖的刻畫(huà)

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

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

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

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

貪婪著色：怎么給一個(gè)圖進(jìn)行頂點(diǎn)著色?下面我們介紹一種稱(chēng)之為貪婪著色的方法.用1,2,3,…等正整數(shù)來(lái)表示顏色.

四色問(wèn)題四色問(wèn)題的最初形式是:能否用4種顏色給任意平面區(qū)域著色,使得有公共邊的相鄰區(qū)域有不同的顏色(參見(jiàn)左圖).給每個(gè)區(qū)域放置一個(gè)頂點(diǎn),兩個(gè)區(qū)域有公共邊的話在這兩個(gè)相應(yīng)頂點(diǎn)間添加一條通過(guò)公共邊的連線,這樣就得到了一個(gè)平面圖(其實(shí)是平面區(qū)域的對(duì)偶圖).這樣對(duì)平面區(qū)域(或地圖)的著色問(wèn)題就轉(zhuǎn)變?yōu)榱藢?duì)平面圖的頂點(diǎn)著色問(wèn)題(參見(jiàn)右圖).四色問(wèn)題始于19世紀(jì)50年代,經(jīng)過(guò)漫長(zhǎng)的發(fā)展出現(xiàn)了很多接近正確的結(jié)果。值得一提的是AlfredKempe(1849-1922)于1879年發(fā)表的“證明”.這或許是數(shù)學(xué)中最有名的錯(cuò)誤證明.這名律師的證明在11年后的1890年被他的同胞P.J.Heawood(1861-1955)指出了錯(cuò)誤.但是Kempe的證明思路卻是100年后K.Appel和W.Haken完成的計(jì)算機(jī)輔助證明的基礎(chǔ).最終K.Appel和W.Haken在1976年利用計(jì)算機(jī)成功給出了證明,但是一些數(shù)學(xué)家期待的不使用計(jì)算機(jī)的常規(guī)證明仍沒(méi)有出現(xiàn).定理5.5.3平面圖的著色數(shù)不超過(guò)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ù)結(jié)構(gòu)離散數(shù)學(xué)配套教材：李小南目錄CONTENTS6.16.26.36.46.5代數(shù)系統(tǒng)子群和商群循環(huán)群和對(duì)稱(chēng)群群同態(tài)及應(yīng)用環(huán)和域6.1代數(shù)系統(tǒng)

6.1.1

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

=

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

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

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

√不是群√

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

(一般線性群)

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

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

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

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

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

子群證明

設(shè)e′是子群Y的單位元，e是群X的單位元，則e′e′=e′=e′e，

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

同樣，設(shè)a′是a在Y中的逆元，是a在X中的逆元，則

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

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

時(shí)有，另外，由定理6.2.1可知，當(dāng)時(shí)有.

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

代數(shù)運(yùn)算，結(jié)合律在X中成立自然在Y中也成立，又根據(jù)(2)，當(dāng)

時(shí)，結(jié)合(1)可得，即Y中有單位元e，且每個(gè)元素

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

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

設(shè)，下證cY=aY.

設(shè)c=ay()，則cY

=

ayY

=

aY

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

易得ayY=a(yY)

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

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

令(X:Y)=s，則(?)是X關(guān)于Y的左陪集構(gòu)

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

是群X

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

的階為無(wú)限.例如，整數(shù)加群中所有非零元素的階都為無(wú)限，中(12)的階為2，(123)的階為3.推論6.2.1有限群中每個(gè)元素的階都整除群的階.注意這里，即n個(gè)x相乘.這里說(shuō)“相乘”是因?yàn)槿豪锏拇鷶?shù)運(yùn)算我們一般稱(chēng)為“乘法”，當(dāng)然對(duì)于不同的群，具體運(yùn)算規(guī)則是不同的.同時(shí)規(guī)定證明

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

商群上述定義的陪集的運(yùn)算滿足結(jié)合律，單位元為eY=Y，xY的逆元為

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

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

由一個(gè)元素x生成的群X稱(chēng)為循環(huán)群，記為，x也稱(chēng)為的生成元.若群中運(yùn)算用乘法表示，則即中的任意元素可以寫(xiě)為(k為整數(shù));若群中運(yùn)算用加法表示，則即中的任意元素可以寫(xiě)為kx(k為整數(shù)).例6.3.1整數(shù)加群是無(wú)限循環(huán)群，1為其生成元.即也就是說(shuō)整數(shù)加群中任何一個(gè)元素都可以通過(guò)1和加法生成.例6.3.2設(shè)n為正整數(shù)，整數(shù)加群的加法子群也是一個(gè)循環(huán)群.因?yàn)橹械娜魏卧豮n都可以通過(guò)n和加法生成，即循環(huán)群的生成元為n.也是一個(gè)無(wú)限循環(huán)群.方程的n個(gè)復(fù)數(shù)解，具體為例6.3.3n次單位根群是一個(gè)循環(huán)群.回憶例6.1.11中的n次單位根是指由復(fù)數(shù)乘法可得，即任意n次單位根都可以由

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

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

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

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

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

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

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

是X到的映射.如果f

保持群運(yùn)算，即則稱(chēng)f是X到的群同態(tài)（簡(jiǎn)稱(chēng)為同態(tài)）.如果同態(tài)f是滿射，則稱(chēng)f為滿同態(tài)；如果同態(tài)f是單射，則稱(chēng)f為單同態(tài)；如果同態(tài)f是雙射，則稱(chēng)f為同構(gòu)，并稱(chēng)X和同構(gòu)，記為.

，有f(ab)=

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

n→2n

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

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

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

的像.定理6.4.2imf

是的子群，kerf

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

由于f(e)=，故imf

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

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

是的子群.顯然kerf

是X的子群.下證ker

f

是正規(guī)子群.，只需說(shuō)明根據(jù)對(duì)稱(chēng)性，只需說(shuō)明.，下證由于，故.設(shè)，因此.kerf

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

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

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

，其中6.4.2

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

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

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