圖論與抽象代數(shù)復(fù)習

本文格式為Word版，下載可任意編輯——圖論與抽象代數(shù)復(fù)習2023-2023二學期圖論與抽象代數(shù)復(fù)習

第一部分

1.第三篇總復(fù)習題1，2，3題2.第四篇總復(fù)習題1，4，6題3.習題99.1題

4.*運算如下表所示，哪個能使({a,b},*)成為單元半群？（）

5.Q是有理集，（Q，*）（其中*為普通乘法）不能構(gòu)成（）。A．群B．單元半群C．半群D．交換半群6.設(shè)Z是整數(shù)集，＋，·分別是普通加法和乘法，則（Z，＋，·）是（）。A．域B．整環(huán)和域C．整環(huán)D．含零因子環(huán)7.在代數(shù)系統(tǒng)中，整環(huán)和域的關(guān)系為（）。A．整環(huán)一定是域B．域不一定是整環(huán)C．域一定是整環(huán)D．域一定不是整環(huán)8.設(shè)D=為有向圖，V={a,b,c,d,e,f}，E={(a,b),(b,c),(a,d),(d,e),(f,e)}是（A．強連通圖B．單向連通圖C．弱連通圖D．不連通圖9.在有n個結(jié)點的連通圖中，其邊數(shù)（）。A．最多有n?1條B．至少有n?1條C．最多有n條D．至少有n條

10設(shè)G=(n,m)為無向簡單圖，可構(gòu)成鄰接矩陣的數(shù)目為（）。A．n!B．m!C．D．11.歐拉回路是（）。

A．通路B．簡單回路C．既是基本回路也是簡單回路D．既非基本回路也非簡單回路12.哈密爾頓回路是（）。

A．通路B．簡單回路C．既是基本回路也是簡單回路D．既非基本回路也非簡單回路13.下面哪一種圖不一定是樹?（）

A．無回路的連通圖B．有n個結(jié)點n?1條邊的連通圖C．每對結(jié)點間都有通路的圖D．連通但刪去一條邊則不連通的圖下述偏序集（見下圖）中能構(gòu)成格的是（）

下述偏序集中哪一個不構(gòu)成格？（）

。）

其次部分

1第三篇總復(fù)習題11，12，13題2.第四篇總復(fù)習題16，21題3.定理6.14，定理7.10推論2

4.Z是整數(shù)集，群(Z,+)是一個循環(huán)群，其生成元是______和________.

5.G是n個節(jié)點，m條邊的無向圖，v是次數(shù)為k的結(jié)點，則G-v(G中去掉節(jié)點的圖)中有_______個結(jié)點，________條邊。6.設(shè)（G，*）是一個半群，若存在單位元且每個元素都有右逆元，則（G，*）是_____________.7.由一個孤立結(jié)點構(gòu)成的圖稱為________;簡單圖不包含___________第三部分

1.設(shè)代數(shù)系統(tǒng)（A,*），其中A={a,b,c,d}，*乘法表定義如下：問*是否是可交換的；A是否有單位元；假使有單位元，指出哪些元素是可逆的，并給出它們的逆元。

2.第三篇總復(fù)習題20題

3.找出的所有子群。

3

4.有向圖D如下圖所示：

(S,?)

求：(1)D的鄰接矩陣A

(2)D中v1到v4長度為4的通路數(shù)為多少？

(3)D中長度為4的通路總數(shù)為多少？其中有幾條回路？(4)D中v1到自身長度為3的回路數(shù)為多少？

(5)D中長度小于等于4的通路有多少條？其中有多少條是回路？(6)D是哪類連通圖？

5.下圖給出的賦權(quán)圖表示七個城市a，b，c，d，e，f，g及架起城市間直接通信線路的預(yù)計造價，試給出一個設(shè)計方案使得各城市間能夠通信且總造價最小，要求計算出最小總造價。

第四部分

1.證明：定理6.182.證明：定理8.13.證明：定理9.1

4.第三篇總復(fù)習題27題

5.證明：循環(huán)群一定是可換群。

第三篇代數(shù)系統(tǒng)

代數(shù)系統(tǒng)是建立在集合論基礎(chǔ)上以代數(shù)運算為研究對象的學科。本篇共三章，第五章代數(shù)系統(tǒng)基礎(chǔ)介紹代數(shù)系統(tǒng)的一般原理與性質(zhì)，第六章群論，主要介紹具有代表性的代數(shù)系統(tǒng)－群，最終第七章其它代數(shù)系統(tǒng)，介紹除群外常見的一些代數(shù)系統(tǒng)，如環(huán)、域、格與布爾代數(shù)等，這三章相互協(xié)同構(gòu)成了代數(shù)系統(tǒng)的完整的整體。第五章代數(shù)系統(tǒng)基礎(chǔ)§5.1代數(shù)系統(tǒng)一般概念

1．代數(shù)系統(tǒng)中的基本概念

（1）代數(shù)系統(tǒng)：集合上具有封閉性的運算組成代數(shù)系統(tǒng)（S,）。（2）子代數(shù)：代數(shù)系統(tǒng)（S,），（S?，?）滿足：①S??S

②如a,b?S?，a?b=ab則稱（S?，?）為（S,）的子代數(shù)?！?.2代數(shù)系統(tǒng)常見的一些性質(zhì)（3）代數(shù)系統(tǒng)常見性質(zhì)1）結(jié)合律：（ab）c＝a（bc）2）交換律：ab＝ba

3）分派律：a（b＋c）＝（ab）＋（ac）4）單位元：a1＝a

5）逆元：aa－1＝16）零元：a0＝07）生成元§5.3同構(gòu)與同態(tài)（4）同構(gòu)：（X，）與（Y，?）存在一一對應(yīng)函數(shù)g:X?Y使得如x1,x2?X，則有：g（x1x2）＝g（x1）?g（x2）此時則稱（X,）與（Y，?）同構(gòu)。（5）同態(tài)：（X,）與（Y，?）存在函數(shù)g:X?Y使得如x1,x2?X，則有：g（x1x2）＝g（x1）?g（x2）此時則稱（X，）與（Y，?）同態(tài)?！?.4常用代數(shù)系統(tǒng)

（6）代數(shù)系統(tǒng)的構(gòu)成

交換律?可換群生成元（一個二元運算）子集上的群?循環(huán)群特別群結(jié)合律半群單位元、逆元群??特別群?子群交換律單位元?可換半群?變換群生成元?單元半群?正規(guī)子群、商群

?循環(huán)半群（兩個二元運算：?,)代數(shù)系統(tǒng)?可換群,半群,對?分派群環(huán)交換律可換環(huán)單位元,逆元?域???單位元，無零因子

特別子環(huán)?理想特別環(huán)（兩個二元運算：?,)??商環(huán)?布爾代數(shù)?兩個運算的單位元、逆元

兩個運算有單位元?有界格兩個運算有逆元?有補格兩個運算的結(jié)合律、交換律、吸收律格兩個運算的分派律分派格?整環(huán)

第六章群論

§6.1一些群的定義

（7）半群——代數(shù)系統(tǒng)滿足交換律（8）單元半群——半群存在單位元（9）群——半群存在單位元與逆元（10）可換群——群滿足交換律

（11）變換群——集合A上所有的變換構(gòu)成的集合E（A），對于復(fù)合變換?所構(gòu)成的代數(shù)系統(tǒng)（E（A）,）是一個群，稱變換群。（12）循環(huán)群——群有生成元。

（13）有限群：群（S,）中S為有限集。

（14）子群：群（G，?）上G的子集所構(gòu)成的群。

（15）正規(guī)子群：（H，?）是群（G，?）的子群，如對a?G都有：aH=Ha

則稱（H，?）是（G，?）的正規(guī)子群。

（16）陪集：H是G的子群，Ha＝{ha|h?H},aH={ah|h?H}分別稱H在G中的一個右陪集或左陪集。

（17）商群：H是G的正規(guī)子群，對Ha，Hb?G/H，二元運算（Ha)?(Hb)＝Hab構(gòu)成群，則稱H是G的商群。（18）單元半群性質(zhì)：

?單元半群的子系統(tǒng)若包含單位元也是單元半群。

?可列個元素的單元半群的運算組合表每行（列）均不一致。?循環(huán)單元半群是可換單元半群。

?可換單元半群的所有等冪元素是一個子單元半群?！?.2一些群的理論與半群性質(zhì)：?半群的子代數(shù)也是半群。?循環(huán)半群是可換半群。（19）關(guān)于群的基本理論

?群方程可解性：ax=b（或xa=b）對x存在唯一解；?群的消去律：ab=ac（或ba=ca）必有b=c；?任一群必與變換群同構(gòu)；

?與一個群同構(gòu)或滿同態(tài)的代數(shù)系統(tǒng)必為群；

?一個代數(shù)系統(tǒng)有限群滿足結(jié)合律及消去律則必為群；

?有限群必與置換群同構(gòu)；

?循環(huán)群要么與（I,＋）同構(gòu)，要么與（Zm，＋m）同構(gòu)；

?一個群子集H構(gòu)成群（H,o）的充分必要條件：a,b?H則ab?H,a?H則a－1?H；

?一個群子集H構(gòu)成子群（H,o）的充分必要條件：a,b?H則ab－1?H；?一個有限群的階一定被它的子群的階所等分（拉格朗日定理）；?f是群（G,）與（G?，?）的滿同態(tài)，K是f的核，則必有：（G/k,?）與（G?，?）同構(gòu)；

第七章其它代數(shù)系統(tǒng)

§7.1環(huán)、理想、整環(huán)和域（20）環(huán)：（R，＋,），對＋的可換群，對的半群，對＋的分派律；（21）理想：（D，＋,），環(huán)（R，＋,）的子環(huán)，滿足：a?R,b?D，必有：ab?D,ba?D；

（22）整環(huán)：環(huán)（R，＋,）中，運算有單位元，無零因子；（23）域：環(huán)（P，＋,）中，運算交換律，有單位元，逆元；（24）環(huán)的基本理論環(huán)的基本運算性質(zhì)：?a0=0a=0；

?a（－b）=（－a）b=－（ab）?(－a)(－b)＝ab

?環(huán)中無零因子?環(huán)滿足消去律；

?環(huán)中子系統(tǒng)S是子環(huán)的充要條件是a?s則必有a－1?S。（25）域的基本理論1）域是整環(huán)；

2）有限整環(huán)必是域。

§7.2格與布爾代數(shù)（26）格：（P，＋,）中，兩個運算的結(jié)合律、吸收律、交換律；

（27）布爾代數(shù)：格（B，＋,）中，兩個運算的分派律、單位元、逆元。（28）格的基本理論

1）一個偏序格必是一個代數(shù)格，反之亦然；2）格的運算性質(zhì)。

?a≤a∨b,b≤a∨b（a∨b≥a,a∨b≥b）?a≤c且b≤c?a∨b≤c（a≤c且b≤c?c≥a∨b）?a∧b≤a,a∧b≤b（a≥a∧b,b≥a∧b）?c≤a且c≤b?c≤a∧b（c≤a且c≤b?c≥a∧b≥c）（29）布爾代數(shù)的基本理論

—布爾代數(shù)（B，＋，）滿足：（對＋與）?交換律?結(jié)合律?等冪律?吸收律?分派律?零一律?同一律?互補律?雙補律?德?摩根律

第四篇圖論

圖論用‘結(jié)點’表示事物，而用‘邊’表示事物間聯(lián)系，并用‘結(jié)點’與‘邊’所構(gòu)成的圖用以研究客觀世界。為便于計算，建立了圖的矩陣表示，這樣可以將圖論研究與計算相結(jié)合，從而使圖論研究具有很大的實用性。由于圖的形式好多，在實用中我們一般對若干種常用的圖作研究，它們是樹、平面圖與兩步圖。

在圖論學習中主要要把握如下幾個方面：①圖論中的基本概念。

②圖論中的基礎(chǔ)理論。③圖的矩陣計算。④幾種常用的圖。

在本篇中共有兩部分組成，它們是圖論原理與常用圖，其中圖論原理部分介紹圖的基本概念、理論與計算而常用圖部分則介紹樹、平面圖與兩步圖等三種常用圖，這兩部分的有機結(jié)合構(gòu)成了圖論的完整的整體。

第八章圖論原理§8.1圖的基本概念§8.1.1圖

§8.1.2圖的基本概念（1）圖的概念

圖由結(jié)點集V＝{v1，v2，…，vn}與邊集E＝{l1，l2，…，lm}所組成，可記為：

G＝（2）有向圖與無向圖

①邊為有向的圖稱為有向圖②邊為無向的圖稱為無向圖

（3）幾種特別的圖

①零圖：無邊的圖。

②平凡圖：僅有一個結(jié)點所組成的圖。③完全圖：各結(jié)點間均有邊相聯(lián)的圖。

④補圖：G＝，G?＝如有＝為完全圖且E∩E?＝?，則稱G為G的補圖。

⑤簡單圖與多重圖：包括多重邊的圖稱為多重圖，否則稱為簡單圖。⑥有權(quán)圖：邊帶權(quán)的圖。

§8.1.3圖的同構(gòu)

⑦同構(gòu)圖：G＝，G?＝，V與V?以及相應(yīng)邊的結(jié)點對中有一一對應(yīng)關(guān)系。

§8.1.4圖中結(jié)點的次數(shù)（4）圖中結(jié)點的次數(shù)?引入次數(shù)deg（v）、引出次數(shù)deg（v）、次數(shù)deg（v）。?定理：deg（vi）=2m§8.2通路、回路與連通性（5）通路與回路

①通路：圖中vi至vj的通路是在邊的序列：（vi，vi1），（vi1，vi2），…（vik－1，vik），其中vik＝vj

②基本通路與簡單通路：圖各邊全不同的通路叫簡單通路，各點全不同的通路叫基本通路。

③環(huán)與回路：邊的始點與終點一致稱環(huán)，通路的起始點與終止點一致稱回路。④簡單回路與基本回路：簡單（基本）通路的起始點與終止點一致稱簡單（基本）回路。

⑤有向圖（n,m）的基本通路長度≤n－1，基本回路長度≤n。

（6）圖的連通性

①圖的可達性：圖的結(jié)點vi到vj間存在通路則稱從vi到vj是可達的。②連通圖：圖的任何兩結(jié)點間均可達。③三種連通圖：

?強連通：有向圖中任何兩結(jié)點間相互可達則稱強連通。

?弱連通：有向圖忽略其邊的方向所構(gòu)成的無向圖為連通則稱弱連通。?單向連通：有向圖兩結(jié)點間至少有一向是可達的則稱單向連通。

§8.3歐拉圖

（7）歐拉圖

?歐拉回路與歐拉通路：通過G中每邊一次的回（通）路稱歐拉回（通）路，

具此回路的圖稱歐拉圖。

③歐拉圖與歐拉通路：歐拉圖?每個結(jié)點次數(shù)為偶數(shù)。

由vi到vj歐拉通路?vi，vj結(jié)點次數(shù)為奇數(shù)，其它結(jié)點次數(shù)為偶數(shù)。

§8.4漢密爾頓圖

（8）漢密爾頓圖

?漢密爾頓回路與漢密爾頓通路：通過G中每個結(jié)點一次的回（通）路稱漢密爾回（通）路，具此回路的圖稱漢密爾頓圖。?漢密爾頓圖與漢密爾頓通路中的定理

漢密爾頓圖的必要條件G＝中V1?V且P（G－V1）≤|V1|，其中P（G－V1）為從G中刪除V1（包括V1中各結(jié)點及其關(guān)聯(lián)邊）后所得到的連通分支數(shù)。漢密爾頓圖的充分條件：G＝無向簡單圖，|V|≥3，G中每結(jié)點對次數(shù)之和≥|V|。

漢密爾頓通路：有向圖D＝，|V|≥2所有有向邊均用無向邊替代后得無向圖含生成子圖Kn。

§8.5圖的矩陣表示法

（9）圖的鄰接矩陣：G＝為（n，m）圖，其鄰接矩陣：A＝（aij）n×n.

1（vi，vj）?E