離散數(shù)學(xué)知識點2118

...說明：定義：紅色表示。定理性質(zhì)：橙色表示。公式：藍色表示。算法:綠色表示頁碼：灰色表示數(shù)理邏輯：1.命題公式：命題，聯(lián)結(jié)詞(，，，，)，合式公式，子公式2.公式的真值：賦值，求值函數(shù)，真值表，等值式，重言式，矛盾式3.范式：析取范式，極小項，主析取范式，合取范式，極大項，主合取范式4.聯(lián)結(jié)詞的完備集：真值函數(shù)，異或，條件否認，與非，或非，聯(lián)結(jié)詞完備集5.推理理論：重言蘊含式，有效結(jié)論，P規(guī)那么，T規(guī)那么，CP規(guī)那么，推理6.謂詞與量詞:謂詞，個體詞，論域，全稱量詞，存在量詞7.項與公式:項，原子公式，合式公式，自由變元，約束變元，轄域，換名，代入8.公式語義:解釋，賦值，有效的，可滿足的，不可滿足的9.前束范式:前束范式10.推理理論:邏輯蘊含式，有效結(jié)論，-規(guī)那么〔US〕，+規(guī)那么〔UG〕，-規(guī)那么(ES)，+規(guī)那么(EG),推理集合論：1.集合:集合,外延性原理,,,,空集,全集,冪集,文氏圖,交,并,差,補,對稱差2.關(guān)系:序偶,笛卡爾積,關(guān)系,domR,ranR,關(guān)系圖,空關(guān)系,全域關(guān)系,恒等關(guān)系3.關(guān)系性質(zhì)與閉包:自反的,反自反的,對稱的,反對稱的,傳遞的,自反閉包r(R),對稱閉z....-包s(R),傳遞閉包t(R)4.等價關(guān)系:等價關(guān)系,等價類,商集,劃分5.偏序關(guān)系:偏序,哈斯圖,全序(線序),極大元/極小元,最大元/最小元,上界/下界6.函數(shù):函數(shù),常函數(shù),恒等函數(shù),滿射,入射,雙射，反函數(shù),復(fù)合函數(shù)7.集合基數(shù):基數(shù),等勢,有限集/無限集,可數(shù)集,不可數(shù)集代數(shù)構(gòu)造：1.運算及其性質(zhì)：運算，封閉的,可交換的,可結(jié)合的,可分配的,吸收律,冪等的，幺元,零元,逆元2.代數(shù)系統(tǒng)：代數(shù)系統(tǒng)，子代數(shù)，積代數(shù)，同態(tài)，同構(gòu)。3.群與子群：半群,子半群,元素的冪，獨異點，群，群的階數(shù)，子群,平凡子群，陪集，拉格朗日〔Lagrange〕定理4.阿貝爾群和循環(huán)群：阿貝爾群(交換群)，循環(huán)群,生成元5.環(huán)與域：環(huán)，交換環(huán)，含幺環(huán)，整環(huán)，域6.格與布爾代數(shù)：格，對偶原理，子格，分配格，有界格，有補格，布爾代數(shù)，有限布爾代數(shù)的表示定理圖論：1.圖的根本概念：無向圖、有向圖、關(guān)聯(lián)與相鄰、簡單圖、完全圖、正那圖么、子圖、補圖，握手定理，圖的同構(gòu)2.圖的連通性:通路，回路，簡單通路，簡單回路〔跡〕初級通路〔路徑〕，初級回路〔圈〕，點連通，連通圖，點割集，割點，邊割集，割邊，點連通度，邊連通度，弱連通圖，單向連通圖，強連通圖，二部圖〔二分圖〕3.圖的矩陣表示：關(guān)聯(lián)矩陣，鄰接矩陣，可達矩陣-.word.zl-

..-4.歐拉圖與哈密頓圖：歐拉通路、歐拉回路、歐拉圖、半歐拉圖，哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖5.無向樹與根樹：無向樹，生成樹，最小生成樹，Kruskal，根樹，m叉樹，最優(yōu)二叉樹，Huffman算法6.平面圖:平面圖，面，歐拉公式，Kuratoski定理數(shù)理邏輯：命題：具有確定真值的陳述句。否認詞符號：設(shè)p是一個命題，p稱為p的否認式。p是真的當且僅當p是假的。p是真的當且僅當p是假的。【定義1.1】合取詞符號：設(shè)p，q是兩個命題，命題“p并且q〞稱為p，q的合取，記以pq，讀作p且q。pq是真的當且僅當p和q都是真的。【定義1.2】析取詞符號：設(shè)p，q是兩個命題，命題“p或者q〞稱為p，q的析取，記以pq，讀作p或q。pq是真的當且僅當p，q中至少有一個是真的?！径x1.3】蘊含詞符號：設(shè)p，q是兩個命題，命題“如果p，那么q〞稱為p蘊含q，記以pq。pq是假的當且僅當p是真的而q是假的?！径x1.4】等價詞符號：設(shè)p，q是兩個命題，命題“p當且僅當q〞稱為p等價q，記以pq。pq是真的當且僅當p，q或者都是真的，或者都是假的?！径x1.5】合式公式:(1)命題常元和變元符號是合式公式；(2)假設(shè)A是合式公式，那么(A)是合式公式，稱為A的否認式；(3)假設(shè)A，B是合式公式，那么(AB)，(AB)，(AB)，(AB)是合式公式；(4)所有合式公式都是有限次使用(1)，(2)，(3)、(4)得到的符號串。子公式:如果Ｘ是合式公式A的一局部，且Ｘ本身也是一個合式公式，那么稱Ｘ為公式A的子公式。【定義1.6】賦值〔指派，解釋〕：設(shè)是命題變元集合，那么稱函數(shù)v：{1，0}是一個真值賦值?！径x1.8】真值表：公式A在其所有可能的賦值下所取真值的表，稱為A的真值表。【定義1.9】重言式〔永真式〕:任意賦值v，vA矛盾式〔永假式〕:任意賦值v，有vA【定義1.10】等值式：假設(shè)等價式AB是重言式，那么稱A與B等值，記作AB。【定義2.1】根本等值式雙重否認律AA冪等律AAA,AAA交換律ABBA,ABBA結(jié)合律(AB)CA(BC),(AB)CA(BC)分配律A(BC)(AB)(AC),A(BC)(AB)(AC)-.word.zl-..-德摩根律(AB)AB,(AB)AB吸收律A(AB)A,A(AB)AA,AAA,AA零律同一律排中律矛盾律AAAA蘊涵等值式ABAB等價等值式AB(AB)(BA)假言易位ABBA等價否認等值式ABAB(AB)(AB)A歸謬論置換規(guī)那么：設(shè)Ｘ是公式A的子公式,ＸY。將A中的Ｘ〔可以是全部或局部X〕用Y來置換，所得到的公式B，那么AB。文字:設(shè)A〔命題變元集〕,那么A和A都稱為命題符號A的文字，其中前者稱為正文字，后者稱為負文字?！径x2.2】析取范式：形如A(n1)的公式稱為析取范式，其中A(i=1,…,n)是由文字組成的合A…A12ni取范式。合取范式：形為A(n1)的公式稱為合取范式，其中A,…,A都是由文字組成的A…A12n1n析取式?！径x2.3】極小項：文字的合取式稱為極小項，其中公式中每個命題符號的文字都在該合取式中出現(xiàn)一次。極大項：文字的析取式稱為極大項，其中公式中每個命題符號的文字都在該合取式中出現(xiàn)一次?！径x2.4】主析取范式：給定的命題公式的主析取范式是一個與之等價的公式，后者由極小項的析取組成。主合取范式：給定的命題公式的主合取范式是一個與之等價的公式，后者由極大項的合取組成。【定義2.5】公式的真值表中真值為F的指派所對應(yīng)的極大項的合取，即為此公式的主合取范式。真值函數(shù)：稱F:{0,1}n{0,1}為n元真值函數(shù).【定義2.6】聯(lián)結(jié)詞的完備集：設(shè)C是聯(lián)結(jié)詞的集合，假設(shè)對于任意一個合式公式均存在一個與之等價的公式，而后者只含有C中的聯(lián)結(jié)詞，那么稱C是聯(lián)結(jié)詞的完備集?！径x2.7】{，，，，}，{，，},{，}，{，}，{，}是聯(lián)結(jié)詞的完備集?！径ɡ?.6】異或PQ：(PQ)c條件否認PQ：(PQ)與非PQ：(PQ)或非PQ：(PQ)【定義2.8】{},{↓}都是聯(lián)結(jié)詞的完備集【定理2.7】重言蘊含式：當且僅當PQ是一個重言式時，稱P重言蘊含Q，記為PQ。有效結(jié)論：設(shè)A、C是兩個命題公式，假設(shè)AC，稱C是A的有效結(jié)論?！径x3.1】推理定律——重言蘊涵式1.A(AB)2.(AB)A附加律化簡律假言推理拒取式3.(AB)AB4.(AB)BA5.(AB)BA析取三段論假言三段論6.(AB)(BC)(AC)-.word.zl-

..-7.(AB)(BC)(AC)8.(AB)(CD)(AC)(BD)(AB)(AB)B等價三段論構(gòu)造性二難構(gòu)造性二難(特殊形式)9.(AB)(CD)(BD)(AC)破壞性二難形式系統(tǒng):一個形式系統(tǒng)I由下面四個局部組成：(1)非空的字母表，記作A(I).(2)A(I)中符號構(gòu)造的合式公式集，記作E(I).(3)E(I)中一些特殊的公式組成的公理集，記作A(I).X(4)推理規(guī)那么集，記作R(I).記I=<A(I),E(I),A(I),R(I)>,其中<A(I),E(I)>是I的形式語言系統(tǒng),<A(I),R(I)>是I的形式XX演算系統(tǒng).自然推理系統(tǒng):無公理,即A(I)=X公理推理系統(tǒng):推出的結(jié)論是系統(tǒng)中的重言式,稱作定理【定義3.2】P規(guī)那么：在推導(dǎo)過程中,可以隨時添加前提。T規(guī)那么：在推導(dǎo)過程中,可以引入公式S，它是由其前題的一個或多個公式借助重言、蘊含而得到的。推理〔證明〕：從前提A,A,,A到結(jié)論B的推理是一個公式序列C,C,,C.其中C(1il)是12k12li某個A,或者可由序列中前面的公式應(yīng)用推理規(guī)那么得到,并且C=B?！径x3.3】jlCP規(guī)那么(演繹定理)：假設(shè){R}|-S，那么|-RS,其中為命題公式的集合。個體詞：用于表示命題中主語局部的符號或符號串。個體常元表示確指個體。個體變元表示不確指個體。個體域:個體變元的取值范圍，常用D表示。量詞：限定個體數(shù)量特性的詞。全稱量詞：對所有的存在量詞：有些謂詞語言：用符號串表示個體、謂詞、量詞和命題個體變元符號：x，y，z，…個體常元符號：a，b，c，…函數(shù)符號：f，g，…謂詞符號：P，Q，R，…命題常元符號：，量詞符號：，連接詞符號：,,,,輔助符號：〕,〔【定義4.1】項:(1)個體常元和變元是項；(2)假設(shè)f是n元函數(shù)符號，t1,…,tn是項，那么f(t1,…,tn)是項；(3)僅僅有限次使用(1)，(2)產(chǎn)生的符號串是項。【定義4.2】原子公式:假設(shè)P是一個元謂詞符號，t1,…,tn是項,那么P(t1,…,tn)是原子公式?！径x4.3】合式公式：(1)原子公式是公式；(2)假設(shè)A是合式公式，那么(A)是合式公式；(3)假設(shè)A，B是公式，那么(AB)，(AB)，AB)，(AB)是公式；(4)假設(shè)A是公式，x是變元，那么xA，xA是公式；(5)僅僅有限次使用１～４得到的符號串才是合式公式?！径x4.4】-.word.zl-

..-設(shè)公式的一個子公式為xA或xA。那么稱：指導(dǎo)變元：x是或的指導(dǎo)變元。轄域：A是相應(yīng)量詞的轄域。約束出現(xiàn)：轄域中x的一切出現(xiàn)，以及(x)中的x稱為x在中的約束出現(xiàn)。自由出現(xiàn)：變元的非約束出現(xiàn)。約束變元：約束出現(xiàn)的變元。自由變元：自由出現(xiàn)的變元?！径x4.5】封閉的：一個公式A是封閉的，假設(shè)其中不含自由變元。【定義4.6】變元換名：〔1〕換名的范圍是量詞的指導(dǎo)變元,及其相應(yīng)轄域中的變元，其余局部不變?！?〕換名時最好選用轄域中未出現(xiàn)的變元名。變元代入：代入對自由變元進展。不能改變約束關(guān)系。解釋：謂詞語言的一個解釋I=(D,)包括：(1)非空集合D，稱之為論域；(2)對應(yīng)于每一個個體常元a，(a)D；(3)對應(yīng)于每一個n元函數(shù)符號f都有一個函數(shù)(f):DnD；(4)對應(yīng)于每一個n元謂詞符號A都有一個n元關(guān)系(A)Dn?！径x4.7】賦值：解釋I中的賦值v為每一個個體變元x指定一個值v(x〕D，即設(shè)V為所個體變元的集合，那么賦值v是函數(shù)v:VD.可滿足的：給定公式A，假設(shè)在某一解釋中至少有一種賦值使A取值為1，那么稱A為可滿足的。否那么稱A是不可滿足的。等值式AB：假設(shè)AB是有效的【定義5.1】幾類等值式〔1〕命題公式的推廣e.g.P(x)Q(x)P(x)Q(x)〔2〕否認深入xP(x)x(P(x))xP(x)x(P(x))〔3〕量詞作用域的擴X與收縮設(shè)B中不含x的自由出現(xiàn)，那么x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)〔4〕量詞分配等值式x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)〔5〕多個量詞的使用xyA(x,y)yxA(x,y)xyA(x,y)yxA(x,y)置換規(guī)那么：設(shè)(A)是含A的公式,那么,假設(shè)AB,那么(A)(B).-.word.zl-

-ii邏輯蘊含式AC：當且僅當AC是有效的。幾類邏輯蘊涵式第二組根本等值式生成的推理定理如,xF(x)xF(x),xF(x)xF(x)xF(x)xF(x),第三組其它常用推理定律或x,y個體變項，c個體常項+規(guī)那么(UG)：-規(guī)那么(ES)：x個體變項x個體變項,c個體常項+規(guī)那么(EG)：c個體常項或x,y個體變項，--或先用ES，再用US自然推理系統(tǒng)N：L1.字母表.同一階語言L的字母表2.合式公式.同L的合式公式3.推理規(guī)那么:(1)前提引入規(guī)那么(2)結(jié)論引入規(guī)那么(3)置換規(guī)那么(4)假言推理規(guī)那么(5)附加規(guī)那么(6)化簡規(guī)那么(7)拒取式(8)假言三段論規(guī)那么(9)析取三段論規(guī)那么(10)構(gòu)造性二難推理規(guī)那么(11)合取引入規(guī)那么(12)-規(guī)那么(13)+規(guī)那么(14)-規(guī)那么(15)+規(guī)那么【定義5.3】集合論：ABx(xAxB)【定義6.1】A=BABBA【定義6.2】ABABAB【定義6.3】A?Bx(xAxB)空集：不含有任何元素的集合【定義6.4】空集是任何集合的子集?！径ɡ?.1】冪集P(A)={x|xA}【定義6.5】如果|A|=n，那么|P(A)|=2n全集E：包含了所有元素的集合【定義6.6】并AB={x|xAxB}交AB={x|xAxB}差〔相對補〕AB={x|xAxB}【定義6.7】對稱差A(yù)B=(AB)(BA)【定義6.8】補〔絕對補〕A=EA={x|xA}【定義6.9】廣義并A={x|z(zAxz)}【定義6.10】-..-廣義交A={x|z(zAxz)}【定義6.11】集合恒等式1.只涉及一個運算的算律：交換結(jié)合冪等AB=BAAB=BAAB=BA(AB)C=A(BC)(AB)C=A(BC)(AB)C=A(BC)AA=AAA=A2．涉及兩個不同運算的算律：與與分配A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)吸收A(AB)=AA(AB)=A3．涉及補運算的算律：A(BC)=(AB)(AC)(BC)=BA(BC)=(AB)(AC)(BC)=BCCD.M律雙重否認A=A4．涉及全集和空集的算律：E補元律零律AA=A=A=A=EAA=EAE=EAE=AE=同一律否認序偶〔有序?qū)Α常河蓛蓚€元素x和y，按照一定的順序組成的二元組，記作<x,y>.【定義7.1】笛卡兒積:設(shè)A,B為集合，A與B的笛卡兒積記作AB定義為AB={<x,y>|xAyB}.【定義7.2】笛卡爾積性質(zhì)：A=或B=時,AB=“〞不滿足結(jié)合律A(BC)=(AB)(AC)關(guān)系：〔兩個定義〕(1)序偶的一個集合,確定了一個二元關(guān)系R。R中任一序偶<x,y>,可記作<x,y>R或xRy【定義7.3】(2)笛卡爾積的子集：RAB【定義7.4】空關(guān)系:全域關(guān)系：A×B-.word.zl-..-恒等關(guān)系I={<x,x>|x∈A}【定義7.5】A關(guān)系矩陣：假設(shè)A={x,x,…,x}，B={y,y,…,y}，R是從A到B的關(guān)系，R的關(guān)系矩陣是布12m12n爾矩陣M=[r],其中r=1<x,y>R.ijmnRijij關(guān)系圖：假設(shè)A={x,x,…,x}，R是從A上的關(guān)系，R的關(guān)系圖是G=<A,R>,其中A為結(jié)點12mR集，R為邊集.如果<x,x>屬于關(guān)系R，在圖中就有一條從x到x的有向邊.ijij前域(定義域)dom(R)={x|y.<x,y>R}值域ran(R)={y|x.<x,y>R}域fld(R)=domRranR【定義7.6】逆關(guān)系R1={<y,x>|<x,y>R}【定義7.7】互逆(R)=R11(RS)1=R1S1(RS)1=R1S1(AB)1=BA(R-S)1=R1-S1復(fù)合關(guān)系RS={<x,z>|y(<x,y>R<y,z>S)}【定義7.8】(RS)P=R(SP)Rm=RR…R設(shè)RXY,SYZ,那么(RS)1=S1R1【定理7.2】R在A上的限制R?A={<x,y>|xRy∧x∈A}A在R下的像R[A]=ran(R?A)【定義7.9】自反的：假設(shè)x∈A，都有<x,x>R,那么稱R是自反的反自反的：假設(shè)x∈A，都有<x,x>R,那么稱R是反自反的.【定義7.11】對稱的：對任意x,yA,滿足,假設(shè)<x,y>R,那么<y,x>R反對稱的：對任意x,yA,滿足，假設(shè)<x,y>R且<y,x>R,那么x=y【定義7.12】傳遞的：對任意的x,y,zA,滿足:假設(shè)<x,y>R且<y,z>R,那么<x,z>R,那么稱R是傳遞的【定義7.13】自反閉包〔對稱、傳遞〕：設(shè)R是A上的二元關(guān)系,如果有另一個關(guān)系R'滿足:①R'是自反〔對稱、傳遞〕的;②R'R;③對于任何自反的關(guān)系R〞,假設(shè)R"R,那么有R"R'.那么稱關(guān)系R'為R的自反閉包.記為r(R)〔對稱閉包s(R)和傳遞閉包t(R)〕?！径x7.14】設(shè)R為A上的關(guān)系,那么有(1)r(R)=R∪IA(2)s(R)=R∪R1(3)t(R)=R∪R∪R∪…∪R〕∪…〔假設(shè)|A|=n，那么t(R)=R∪R232n等價關(guān)系：設(shè)R為集合A上的一個二元關(guān)系。假設(shè)R是自反的,對稱的,傳遞的,那么稱R為A上的等價關(guān)系【定義7.15】等價類：設(shè)R為集合A上的等價關(guān)系,對aA,定義:[a]={x|xA且<a,x>R}稱之為元素aR關(guān)于R的等價類?！径x7.16】給定A上的等價關(guān)系R,對于a,bA有<a,b>當且僅當[a]R=[b]R【定理17.4】-.word.zl-

..-商集：設(shè)R是A上的等價關(guān)系，定義A/R={[a]|aA}稱之為A關(guān)于R的商集.【定義7.17】R劃分：設(shè)A為非空集合,假設(shè)A的子集族π(πP(A))滿足:(1)π(2)xy(x,yπ∧x≠yx∩y=)(3)∪π=A那么稱π是A的一個劃分,稱π中的元素為A的劃分塊.【定義7.18】給定集合A上的等價關(guān)系R,那么商集A/R是A的一個劃分.集合A的一個劃分π誘導(dǎo)出A上的一個等價關(guān)系R.R定義為R={<x,y>|x,yA且x,y在π的同一分塊中}設(shè)R和R為非空集合A上的一個等價關(guān)系,那么R=R當且僅當A/R=A/R.121212偏序：設(shè)A是一個集合.如果A上的二元關(guān)系R是自反的,反對稱的和傳遞的,那么稱R是A上的一個偏序關(guān)系.記R為“〞,且稱序偶<A,>為偏序集。【定義7.19】【定義7.22】全序〔線序〕：設(shè)<A,>為偏序集,假設(shè)對任意的x,yA滿足:xy或yx那么稱為全序關(guān)系.<A,>為全序集.【定義7.21】覆蓋：設(shè)<A,>為偏序集,假設(shè)x,yA,xy,xy且沒有其它元素z滿足xz,zy,那么稱y覆蓋x.記covA={<x,y>|x,yA且y覆蓋x}【定義7.23】哈斯圖：作圖規(guī)那么①用小元圈代表元素;②假設(shè)xy且xy,那么將代表y的小元圈畫在代表x的小元圈之上;③假設(shè)<x,y>covA,那么在x,y之間用直線連接。你極小元/極大元：設(shè)<A,>為偏序集,BA(1)對bB，假設(shè)B中不存在x滿足:bx且xb那么稱b為B的極小元.(2)對bB，假設(shè)B中不存在x滿足:bx且bx那么稱b為B的極大元.最小元/最大元：設(shè)<A,>為偏序集,BA,假設(shè)有某個bB(1)對于B中每一個元素x都有bx，那么稱b為B的最小元.(2)對于B中每一個元素x都有xb，那么稱b為B的最大元.【定義7.24】下界/上界：設(shè)<A,>為偏序集,BA(1)假設(shè)有aA,且對xB滿足ax，那么稱a為B的下界。進一步:設(shè)a為B的下界,假設(shè)B的所有下界y均有ya,那么稱a為B的下確界，記為glbB。(2)假設(shè)有aA,且對xB滿足xa，那么稱a為B的上界。進一步:設(shè)a為B的上界,假設(shè)B的所有上界y均有ay,那么稱a為B的上確界，記為lubB。【定義7.25】函數(shù)：設(shè)X,Y為兩個集合,fXY,假設(shè)對xX,!(唯一的)yY,滿足:<x,y>f,那么稱f為函數(shù).記為:f:XY定義域:domf=X值域:ranf(有時記為f(X))={f(x)|xX}【定義8.1】函數(shù)相等：設(shè)f和g都是從A到B的函數(shù),假設(shè)對任意xA,有f(x)=g(x),那么稱f和g相等.記為f=g【定義8.2】函數(shù)的個數(shù)：設(shè)f:AB,|A|=m,|B|=n.記B={f|f:AB},那么|B|=nAAm滿射(到上映射)：設(shè)f:XY,假設(shè)ranf=Y,那么稱f為滿射的.入射〔單射〕(一對一映射)：設(shè)f:XY,對x,x,那么f(x)f(x),稱f為X,滿足:假設(shè)xx121212入射的.-.word.zl-

..-雙射(一一對應(yīng)映射)：設(shè)f:XY,假設(shè)f既是滿射的,又是入射的.那么稱f是雙射的.【定義8.6】常函數(shù):設(shè)f:A→B,如果存在c∈B使得對所有的x∈A都有f(x)=c,那么稱f:A→B是常函數(shù).恒等函數(shù):稱A上的恒等關(guān)系I為A上的恒等函數(shù),對所有的x∈A都有I(x)=x.AA單調(diào)遞增:設(shè)<A,?>,<B,?>為偏序集，f:A→B，如果對任意的x,x∈A,xx,就有f(x)?f(x),?112212那么稱f為單調(diào)遞增的；嚴格單調(diào)遞增:如果對任意的x,x∈A,xx,就有f(x)?f(x),那么稱f為嚴格單調(diào)遞增的.?112212類似的也可以定義單調(diào)遞減和嚴格單調(diào)遞減的函數(shù)特征函數(shù)：設(shè)A為集合,對于任意的A'A,A'的特征函數(shù)':A→{0,1}定義為'(a)=1,a∈AAA';'(a)=0,a∈AA'A自然映射：設(shè)R是A上的等價關(guān)系,令g:A→A/R；g(a)=[a],a∈A稱g是從A到商集A/R的自然映射【定義8.7】復(fù)合函數(shù)：設(shè)f:XY,g:YZ,定義:fg={<x,z>|xX且zZ且可找到y(tǒng)Y使y=f(x),z=g(y)}稱fg為f與g的復(fù)合函數(shù).設(shè)f:A→B,g:B→C(1)如果f:A→B,g:B→C是滿射的,那么fg:A→C也是滿射的(2)如果f:A→B,g:B→C是單射的,那么fg:A→C也是單射的(3)如果f:A→B,g:B→C是雙射的,那么fg:A→C也是雙射的【定理8.2】反函數(shù)〔逆函數(shù)〕：設(shè)f:XY是一個雙射函數(shù)，那么f是YX的雙射函數(shù).稱f-1-1為f的反函數(shù).-1-1互逆(f)=f設(shè)f:A→B是雙射的,那么f1f=I,ff1=I【定理8.5】BA基數(shù)：用來衡量集合大小的一個概念.對于有限集合集來說,集合的基數(shù)就是其中所含元素的個數(shù).等勢的：設(shè)A,B是集合,如果存在著從A到B的雙射函數(shù),就稱A和B是等勢的,記作A≈B.如果A不與B等勢,那么記作A?B.注：通常將A的基數(shù)記為|A|.【定義8.8】N≈Z≈Q≈N×N任何實數(shù)區(qū)間都與實數(shù)集合R等勢{0,1}≈RN康托定理(1)N?R；(2)對任意集合A都有A?P(A).【定義8.7】有限集(有窮集)/無限集(無窮集)：設(shè)A為一個集合.假設(shè)存在某個自然數(shù)n,使得A與集合{0,1,…,n-1}等勢,那么稱A是有限的.假設(shè)集合A不是有限的,那么稱A是無限的.【定義8.11】：實數(shù)集R的基數(shù)記作,即cardR=【定義8.12】可數(shù)集(可列集)：設(shè)A為集合，假設(shè)cardA≤，那么稱A為可數(shù)集或可列集。【定義8.14】0與自然數(shù)集N等勢的任意集合稱為可數(shù)的.其基數(shù)為0(1)A為可數(shù)的當且僅當可排列成A={a,a,…,a,…}的形式.12n(2)任一無限集必含有可數(shù)子集.(3)可數(shù)集的任何無限子集是可數(shù)的.(4)可數(shù)個兩兩不相交的可數(shù)集合的并集,仍是一個可數(shù)集.-.word.zl-

..-(5)NN是可數(shù)集.(6)有理數(shù)的全體組成的集合是可數(shù)集.(7)全體實數(shù)構(gòu)成的集合R是不可數(shù)的.基數(shù)的常識：①對于有窮集合A,基數(shù)是其元素個數(shù)n，|A|=n;②沒有最大的基數(shù)。將的基數(shù)按從小到大的順序排列就得到：0,1,2,…,n,…,,,…0代數(shù)構(gòu)造運算：對于集合A，f是從An到A的函數(shù)，稱f為集合A上的一個n元運算。【定義9.1】交換律：<A，*>，假設(shè)x，y∈A，有x*y=y*x，稱*在A上是可交換的?！径x9.3】結(jié)合律：<A，*>，假設(shè)x，y，z∈A，有x*〔y*z〕=〔x*y〕*z，稱*在A上是可結(jié)合的?！径x9.4】冪等律：〈A，*〉，假設(shè)x∈A，x*x=x那么稱滿足冪等律。【定義9.5】分配律：設(shè)<A，*，△>，假設(shè)x，y，z∈A有:x*(y△z)=〔x*y〕△〔x*z〕;(y△z)*x=(y*x)△(z*x)稱運算*對△是可分配的?！径x9.6】吸收律：設(shè),是定義在集合A上的兩個可交換二元運算，假設(shè)對x,yA,都有:x(xy)=x；x(xy)=x那么稱運算和滿足吸收律.【定義9.7】單位元〔幺元〕:設(shè)*是A上二元運算，e,e,eAlr左幺元：假設(shè)xA，有e*x=x，稱e為運算*的左幺元；ll右幺元：假設(shè)xA，有x*e=x，稱e為運算*的右幺元；rr假設(shè)e既是左幺元又是右幺元，稱e為運算*的幺元【定義9.8】設(shè)*是A上的二元運算，具有左幺元el，右幺元e，那么e=e=e【定理9.1】rlr零元:設(shè)*是A上二元運算，,,Alr左零元：假設(shè)xA，有*x=，稱為運算*的左零元；lll右零元：假設(shè)xA，有x*=，稱為運算*的右零元；rrr假設(shè)既是左零元又是右零元，稱為運算*的零元。【定義9.9】設(shè)*是A上的二元運算，具有左零元，右零元，那么==【定理9.2】lrlr逆元：設(shè)*是A上的二元運算，e是運算*的幺元，假設(shè)x*y=e那對于運算*，x是y的左逆元，y是x的右逆元存在逆元(×ó???T￡?óò???a￡?μ??a??3??a?é??μ?￡¨×ó?é??μ?￡?óò?é??μ?￡?【定義9.10】對于可結(jié)合運算ο，如果元素x有左逆元ｌ，右逆元r，那么l=r=x消去律：<A，*>，假設(shè)x，y，z∈A，有－１【定理9.4】(1)假設(shè)x*y=x*z且x,那么y=z；(左消去律)(2)假設(shè)y*x=z*x且x,那么y=z；〔右消去律〕那么稱*滿足消去律?！径x9.11】代數(shù)系統(tǒng)：設(shè)A為非空集合，為A上運算的集合,稱<A,>為一個代數(shù)系統(tǒng).【定義9.12】同類型的代數(shù)系統(tǒng)：如果兩個代數(shù)系統(tǒng)中運算的個數(shù)一樣，對應(yīng)運算的元數(shù)一樣，且代數(shù)常數(shù)的個數(shù)也一樣，那么稱它們是同類型的代數(shù)系統(tǒng).【定義9.13】子代數(shù)：設(shè)V=<S,f1,f2,…,fk>是代數(shù)系統(tǒng)，B是S的非空子集，如果B對f1,f2,…,fk都是封閉的，且B和S含有一樣的代數(shù)常數(shù)，那么稱<B,f1,f2,…,fk>是V的子代數(shù)系統(tǒng)，簡稱子代數(shù)【定義9.14】最大的子代數(shù)：就是V本身最小的子代數(shù)：如果令V中所有代數(shù)常數(shù)構(gòu)成的集合是B，且B對V中所有的運算都是封閉的，-.word.zl-

..-那么B就構(gòu)成了V的最小的子代數(shù)平凡的子代數(shù):最大和最小的子代數(shù)稱為V的平凡的子代數(shù)真子代數(shù)：假設(shè)B是S的真子集，那么B構(gòu)成的子代數(shù)稱為V的真子代數(shù).因子代數(shù)：設(shè)V=<A,?>和V=<B,>是同類型的代數(shù)系統(tǒng)，?和為二元運算，在集合AB上如12下定義二元運算?，<a,b>,<a,b>AB，有<a,b>?<a,b>=<a?a,bb>稱V=<AB,?>為112211221212V與V的積代數(shù)，記作VV.這時也稱V和V為V的因子代數(shù).【定義9.15】121212設(shè)V=<A,?>和V=<B,>是同類型的代數(shù)系統(tǒng)，VV=<AB,?>是它們的積代數(shù).1212(1)如果?和運算是可交換〔可結(jié)合、冪等〕的，那幺?運算也是可交換〔可結(jié)合、冪等〕的(2)如果e和e〔和〕分別為?和運算的單位元〔零元〕，那幺<,>〔<,>〕也是?運算ee12121212的單位元〔零元〕(3)如果x和y分別為?和運算的可逆元素，那幺<x,y>也是?運算的可逆元素，其逆元就是<x1,y1>【定理9.5】同態(tài):設(shè)V=<A,°>和V=<B,>是同類型的代數(shù)系統(tǒng)，f:AB，對x,yA有f(x°y)=f(x)f(y),那12么稱f是V到V的同態(tài)映射，簡稱同態(tài)12(1)f如果是單射，那么稱為單同態(tài)。(2)如果是滿射，那么稱為滿同態(tài)，這時稱V是V的同態(tài)像，記作VV2112。(3)如果是雙射，那么稱為同構(gòu)，也稱代數(shù)系統(tǒng)V同構(gòu)于V，記作VV(4)如果V=V，那么稱作自同態(tài)?！径x9.16】1212。12半群：設(shè)V=<S,°>是代數(shù)系統(tǒng)，°為二元運算，如果°運算是可結(jié)合的，那么稱V為半群。獨異點：設(shè)V=<S,°>是半群，假設(shè)e∈S是關(guān)于°運算的單位元，那么稱V是含幺半群，也叫做獨異點。有時也將獨異點V記作V=<S,°,e>.群￡o設(shè)V=<G,°>是獨異點，eG關(guān)于°運算的單位元，假設(shè)aG，a1G，那么稱是群(Group).V通常將群記作G.【定義10.1】群的階數(shù)：設(shè)<G,>是一個群有限群：如果G是有限集，那么稱<G,>為有限群階數(shù)：|G|為該有限群的階數(shù)；無限群：如果G是無限集，那么稱<G,>為無限群。平凡群：階數(shù)為1〔即只含單位元〕的群稱為平凡群【定義10.2】群的性質(zhì)：設(shè)<G,>是一個群。〔1〕非平凡群中不可能有零元.〔2〕對于a,bG,必存在唯一的xG,使得ax=b.〔3〕對于{a,b,c}G假設(shè):ab=ac或ba=ca那么必有b=c(消去律)。〔4〕運算表中的每一行或每一列都是一個置換。〔5〕除幺元e外,不可能有任何別的冪等元。en0元素的冪￡o設(shè)G是群，a∈G，n∈Z，那么a的n次冪anan0an【定1annm1m()0,義10.3】元素的階：設(shè)G是群，a∈G，使得等式ak=e成立的最小正整數(shù)k稱為元素a的階，記作|a|=k，稱a為k階元。假設(shè)不存在這樣的正整數(shù)k，那么稱a為無限階元?！径x10.4】冪運算性質(zhì)：(1)a∈G，(a1)1=a(2)a,b∈G，(ab)1=b1a1(3)a∈G，anam=a，n,m∈Zn+m-.word.zl-

..-(4)a∈G，(an)m=anm，n,m∈Z(5)假設(shè)G為交換群，那么(ab)n=anbn.【定理10.1】元素的階的性質(zhì)：G為群，a∈G且|a|=r.設(shè)k是整數(shù)，那么(1)ak=e當且僅當r|k(r整除k)(2)|a1|=|a|【定理10.3】子群：設(shè)G是群，H是G的非空子集，如果H關(guān)于G中的運算構(gòu)成群，那么稱H是G的子群,記作H≤G。真子群：假設(shè)H是G的子群，且HG，那么稱H是G的真子群，記作H<G.平凡子群：對任何群G都存在子群.G和{e}都是G的子群，稱為G的平凡子群.【定義10.5】子群判定定理ò?￡o設(shè)G為群，H是G的非空子集，那么H是G的子群當且僅當(1)a,b∈H有ab∈H；(2)a∈H有a1∈H。【定理10.4】子群判定定理二：設(shè)G為群，H是G的非空子集.H是G的子群當且僅當a,b∈H有ab1∈H【.定理10.5】子群判定定理三：設(shè)G為群，H是G的非空有窮子集，那么H是G的子群當且僅當a,b∈H有ab∈H.【定理10.6】生成子群：設(shè)G為群，a∈G，令H={ak|k∈Z}，那么H是G的子群，稱為由a生成的子群，記作<a>.陪集￡o設(shè)<H,>是群<G,>的一個子群,aG那么:左陪集￡oaH::={a}H，由a所確定的H在G中的左陪集.右陪集￡oHa::=H{a}陪集是左陪集與右陪集的統(tǒng)稱.【定義10.6】陪集性質(zhì)：設(shè)H是群G的子群，那么①He=H②a∈G有a∈Ha③a,b∈G有：a∈Hbab1∈HHa=Hb④在G上定義二元關(guān)系R：a,b∈G,<a,b>∈Rab1∈H那么R是G上的等價關(guān)系，且[a]R=Ha.⑤|Ha|=|H|【定理10.7】【定理10.8】拉格朗日定理：設(shè)G是有限群，H是G的子群，那么|G|=|H|·[G:H]其中[G:H]是H在G中的不同右陪集(或左陪集)數(shù)，稱為H在G中的指數(shù).【定理10.10】推論：〔1〕設(shè)G是n階群，那么a∈G，|a|是n的因子，且an=e.〔2〕對階為素數(shù)的群G，必存在a∈G使得G=<a>.阿貝爾群〔交換群〕：假設(shè)群G中的運算是可交換的，那么稱G為交換群或阿貝爾群。循環(huán)群：設(shè)G是群，假設(shè)存在a∈G使得G={ak|k∈Z}那么稱G是循環(huán)群，記作G=<a>，稱a為G的生成元.n階循環(huán)群:設(shè)G=<a>是循環(huán)群，假設(shè)a是n階元，那么G={a無限循環(huán)群:假設(shè)a是無限階元，那么G={a=e,a,a,…}【定義10.7】循環(huán)群的生成元:設(shè)G=<a>是循環(huán)群(1)假設(shè)G是無限循環(huán)群，那么G只有兩個生成元，即a和a1.n(2)假設(shè)G是n階循環(huán)群，那么G含有()個生成元.對于任何小于n且與n互質(zhì)的數(shù)∈=e,a,a,…,an1}0120±1±2r{0,1,…,n-1},ar是G的生成元.【定理10.11】循環(huán)群的子群：-.word.zl-

-(1)a∈R，a0=0a=0(2)a,b∈R，(a)b=a(b)=ab(3)a,b,c∈R，a(bc)=abac，(bc)a=baca(4)a,a,...,a,b,b,...,b∈R(n,m≥2)【定理10.14】12n12m設(shè)<R,+,·>是環(huán)交換環(huán)：假設(shè)環(huán)中乘法·適合交換律，那么稱R是交換環(huán)；含幺環(huán)：假設(shè)環(huán)中乘法·存在單位元，那么稱R是含幺環(huán)；無零因子環(huán)：假設(shè)a,b∈R，ab=0a=0∨b=0，那么稱R是無零因子環(huán)。整環(huán)：設(shè)<R,+,?>是一個代數(shù)系統(tǒng),假設(shè)滿足:(1)<R,+>是阿貝爾群；(2)<R,?>是可交換獨異點，且無零因子，即對a,bR,a0,b0那么a?b0；(3)運算?對+是可分配的，那么稱<R,+,?>是整環(huán)域：設(shè)<R,+,?>是一個代數(shù)系統(tǒng),假設(shè)滿足:(1)<R,+>是阿貝爾群；(2)<R-{0},?>是阿貝爾群；(3)運算?對+是可分配的，那么稱<R,+,?>是域。【定義10.12】格：設(shè)<S,?>是偏序集，如果x,yS，{x,y}都有最小上界和最大下界，那么稱S關(guān)于偏序?作成一個格【定義11.1】格的代數(shù)系統(tǒng)定義：設(shè)<S,?,?>是代數(shù)系統(tǒng),?和?是二元運算,如果?和?滿足交換律、結(jié)合律和吸收律,那么<S,?,?>構(gòu)成格【定義11.3】對偶命題：設(shè)f是含有格中元素以及符號=,?,?,∨和∧的命題.令f*是將f中的?替換成?,?替換成?,∨替換成∧,∧替換成∨所得到的命題.稱f*為f的對偶命題【定義11.2】格的對偶原理：設(shè)f是含有格中元素以及符號=,?,?,∨和∧等的命題.假設(shè)f對一切格為真,那么f的對偶命題f*也對一切格為真.格的性質(zhì)：設(shè)<L,?>是格,那么運算∨和∧適合交換律、結(jié)合律、冪等律和吸收律,即(1)a,b∈L有a∨b=b∨a,a∧b=b∧a(2)a,b,c∈L有(a∨b)∨c=a∨(b∨c),(a∧b)∧c=a∧(b∧c)(3)a∈L有a∨a=a,a∧a=a(4)a,b∈L有a∨(a∧b)=a,a∧(a∨b)=a【定理11.1】格的序與運算性質(zhì)：設(shè)L是格,那么a,b∈L有a?ba∧b=aa∨b=b【定理11.3】--格的保序性質(zhì)：設(shè)L是格,a,b,c,d∈L，假設(shè)a?b且c?d,那么a∧c?b∧d,a∨c?b∨d【定理11.4】子格：設(shè)<L,∧,∨>是格,S是L的非空子集,假設(shè)S關(guān)于L中的運算∧和∨仍構(gòu)成格,那么稱S是L的子格【定義11.4】分配格：設(shè)<L,∧,∨>是格,假設(shè)a,b,c∈L,有a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)那么稱L為分配格.【定義11.5】分配格的判別：設(shè)L是格,那么L是分配格當且僅當L不含有與鉆石格或五角格同構(gòu)的子格【定理11.5】全下界：設(shè)L是格,假設(shè)存在a∈L使得x∈L有a?x,那么稱a為L的全下界；全上界：設(shè)L是格,假設(shè)存在b∈L使得x∈L有x?b,那么稱b為L的全上界。【定義11.6】有界格：設(shè)L是格，假設(shè)L存在全下界和全上界,那么稱L為有界格，一般將有界格L記為<L,∧,∨,0,1>.【定義11.7】有界格的性質(zhì)：設(shè)<L,∧,∨,0,1>是有界格,那么a∈L有a∧0=0,a∨0=a,a∧1=a,a∨1=1補元：設(shè)<L,∧,∨,0,1>是有界格,a∈L,假設(shè)存在b∈L使得a∧b=0和a∨b=1成立,那么稱b是a的補元【定義11.8】有界分配格的補元惟一性定理：設(shè)<L,∧,∨,0,1>是有界分配格.假設(shè)L中元素a存在補元,那么存在惟一的補元.【定理11.6】有補格:設(shè)<L,∧,∨,0,1>是有界格,假設(shè)L中所有元素都有補元存在,那么稱L為有補格.【定義11.9】布爾格〔布爾代數(shù)〕：如果一個格是有補分配格,那么稱它為布爾格或布爾代數(shù).布爾代數(shù)標記為<B,∧,∨,,0,1>,為求補運算.【定義11.10】布爾代數(shù)的代數(shù)系統(tǒng)定義：設(shè)<B,?,?>是代數(shù)系統(tǒng),?和?是二元運算.假設(shè)?和?運算滿足：(1)交換律,即a,b∈B有a?b=b?a,a?b=b?a(2)分配律,即a,b,c∈B有a?(b?c)=(a?b)?(a?c),a?(b?c)=(a?b)?(a?c)(3)同一律,即存在0,1∈B,使得a∈B有a?1=a,a?0=a(4)補元律,即a∈B,存在a∈B使得a?a=0,a?a=1那么稱<B,?,?>是一個布爾代數(shù).【定義11.11】布爾代數(shù)的性質(zhì)：設(shè)<B,∧,∨,,0,1>是布爾代數(shù),那么(1)a∈B,(a)=a.(2)a,b∈B,(a∧b)=a∨b,(a∨b)=a∧b〔德摩根律〕【定理11.7】原子：設(shè)L是格,0∈L,a∈L假設(shè)b∈L有0?b?ab=a,那么稱a是L中的原子【定義11.12】有限布爾代數(shù)的表示定理：設(shè)B是有限布爾代數(shù),A是B的全體原子構(gòu)成的集合,那么B同構(gòu)于A的冪集代數(shù)P(A).【定理11.8】推論1：任何有限布爾代數(shù)的基數(shù)為2n,n∈N.推論2：任何等勢的有限布爾代數(shù)都是同構(gòu)的圖論無序積：AB={(x,y)|xAyB}無向圖G=<V,E>,其中(1)V為頂點集，元素稱為頂點；-..-(2)E為VV的多重集，其元素稱為無向邊，簡稱邊。【定義14.1】有向圖D=<V,E>,只需注意E是VV的多重子集【定義14.2】n階圖：頂點個數(shù)為n.零圖：邊的個數(shù)為0.n階零圖記為Nn平凡圖：1階零圖N1空圖：標定圖與非標定圖：依據(jù)頂點和邊是否命名標識。有向圖的基圖：有向邊改為無向邊后的圖。頂點與邊的關(guān)聯(lián)關(guān)系e=(v,v)kij關(guān)聯(lián)：e與v,v關(guān)聯(lián)kij關(guān)聯(lián)次數(shù)：0(不關(guān)聯(lián))，1(vv)，2(v=v)ijij環(huán)：與同一頂點關(guān)聯(lián)次數(shù)為2的邊；孤立點：不與任何邊關(guān)聯(lián)的頂點。頂點相鄰：兩個頂點之間有邊。邊相鄰：兩條邊有公共端點。平行邊：關(guān)聯(lián)的端點一樣的兩條邊〔有向圖中方向一樣〕。vV(G)(G為無向圖)v的鄰域：Nv(){u|uVG()(uv,)EG()uv}v的閉鄰域：NvNvv()(){}IveeEG()e與v關(guān)聯(lián)v的關(guān)聯(lián)集：(){|}vV(D)(D為有向圖)v的后繼元集：(v){u|uV(D)v,uE(D)uv}Dv的先驅(qū)元集：(v){u|uV(D)u,vE(D)uv}Dv的鄰域：N(v)(v)(v)DDDvμ?±?áúóò￡oND(v)N(v){}vD多重圖：含平行邊的圖；簡單圖：即不含平行邊又不含環(huán)的圖。【定義14.3】度〔度數(shù)〕：設(shè)G=<V,E>為無向圖,vV,d(v)——v的度數(shù),簡稱度設(shè)D=<V,E>為有向圖,vV,出度d(v)￡ov×÷?a±?μ?ê?μ?μ?′?êy+入度d(v)￡ov作為邊的終點的次數(shù)(v)+d(v)度〔度數(shù)〕d(v)￡od+最大度(G)=max{d(v)|v∈V(G)}最小度(G)=min{d(v)|v∈V(G)}×?′ó3??è(D)=max{d(v)|v∈V(D)}+×?D?3??è(D)=min{d×?′óè??è(D)=max{d+++(v)|v∈V(D)}-(v)|v∈V(D)}(v)|v∈V(D)}×?D?è??è(D)=min{d--.word.zl-..-×?′ó?è(D)=max{d(v)|v∈V(D)}×?D??è(D)=min{d(v)|v∈V(G)}奇頂點度：度為奇數(shù)的頂點偶度頂點：度為偶數(shù)的頂點【定義14.4】握手定理：設(shè)G=<V,E>為任意無向圖，V={v1,v2,…,vn},|E|=m,那么ndvm()2ii1設(shè)D=<V,E>為任意有向圖，V={v1,v2,…,vn},|E|=m,那么nd(v)2m,且id(v)d(v)m【定理14.1】【定理14.2】iinni1i1i1推論：任何圖(無向或有向)中，奇度頂點的個數(shù)是偶數(shù).度數(shù)列：V={v,v,…,v}為無向圖G的頂點集，稱d(v),d(v),…,d(v)為G的度數(shù)列12n12nV={v,v,…,v}為有向圖D的頂點集12n度數(shù)列：d(v),d(v),…,d(v)12n出度列：d+(v),d(v),…,d(v)++12n入度列：d(v),d(v),…,d(v)12n?éí??ˉμ?￡o非負整數(shù)列d=(d,d,…,d)￡?è?′??úò?V={v,v,…,v}?a?￥μ??ˉμ?n?×?T?òí?G,12n12n使得d(v)=d，那么稱d是可圖化的。特別的，假設(shè)得到的圖是簡單圖，那么稱d是可簡單圖化ii的。n非負整數(shù)列d=(d,d,…,d)是可圖化的當且僅當d為偶數(shù).【定理14.3】i12ni1設(shè)G為任意n階無向簡單圖，那么(G)n-1.【定理14.4】圖的同構(gòu)：設(shè)G=<V,E>,G=<V,E>為兩個無向圖(兩個有向圖)，假設(shè)存在雙射函數(shù)f:VV，11122212對于v,vV,(v,v)E當且僅當(f(v),f(v))E〔<v,v>E當且僅當<f(v),f(v)>E)并且,(v,v)ij1i〔<v,v>〕與(f(v),f(v))〔<f(v),f(v)>〕的重數(shù)一樣，那么稱G與G是同構(gòu)的，記作GG.【定j1ij2ij1ij2ijijijij1212義14.5】n(n1)階無向完全圖￡o每個頂點與其余頂點均相鄰的無向簡單圖，記作K.nnn(1)邊數(shù)m,n12n(n1)階有向完全圖￡o每對頂點之間均有兩條方向相反的有向邊的有向簡單圖.邊數(shù)mnnnn1(1),2(1),n(n1)階競賽圖￡o基圖為K的有向簡單圖.【定義14.6】nnn(1)邊數(shù)m,n12n階k正那么圖：==k的無向簡單圖。【定義14.7】nk邊數(shù)m2G=<V,E>,G=<V,E>子圖：V’V且E’E,那么稱G’為G的子圖，記為GG，稱G為G的母圖;生成子圖：假設(shè)GG且V=V，那么稱G為G的生成子圖；真子圖：假設(shè)VV或EE，稱G為G的真子圖；-.word.zl-..-導(dǎo)出子圖：V〔VV且V〕的導(dǎo)出子圖，記作G[V]；E〔EE且E〕的導(dǎo)出子圖，記作G[E].【定義14.8】補圖：設(shè)G=<V,E>為n階無向簡單圖，以V為頂點集，以所有使G成為完全圖K的添加邊組n成的集合為邊集的圖，稱為G的補圖，記作G.假設(shè)GG,那么稱G是自補圖【定義14.9】Gv￡o從G中將v及關(guān)聯(lián)的邊去掉GV￡o從G中刪除V中所有的頂點Ge￡o將e從G中去掉GE￡o刪除E中所有邊【定義14.10】通路與回路：給定圖G=<V,E>〔無向或有向的〕，G中頂點與邊的交替序列=veve…ev稱0112ll為從v到v的通路，其中v,v是e的端點.；假設(shè)v=v，為回路。中的邊數(shù)稱為通路的長i10lii0l度.簡單通路與簡單回路：所有邊各異。初級通路(路徑)與初級回路(圈)：中所有頂點各異〔=除外〕，所有邊也各異vv0l復(fù)雜通路與復(fù)雜回路：有邊重復(fù)出現(xiàn)【定義14.11】在n階圖G中，假設(shè)從頂點v到v〔vv〕存在通路，那么從v到v存在長度小于或等于n1的ijijij通路.【定理14.5】推論：在n階圖G中，假設(shè)從頂點v到v〔vv〕存在通路，那么從v到v存在長度小于或等ijijij于n1的初級通路〔路徑〕在一個n階圖G中，假設(shè)存在v到自身的回路，那么一定存在v到自身長度小于或等于n的ii回路.【定理14.6】推論：在一個n階圖G中，假設(shè)存在v到自身的簡單回路，那么一定存在長度小于或等于n的i初級回路.頂點的連通性：G=<V,E>為無向圖，假設(shè)v與v之間有通路，那么稱v與v是連通的，記為vvjá?í¨í?￡o假設(shè)u,vV，uv，那么稱G是連通的；【定義14.12】連通分支：V/R={V,V,…,V}，稱G[V],G[V],…,G[V]為連通分支，其個數(shù)稱為連通分支數(shù)，ijiji12k12k記為p(G)【定義14.13】短程線uv：，u與v之間長度最短的通路距離d(u,v)：短程線的長度【定義14.14】d(u,v)0,u?v時d(u,v)=d(u,v)=d(v,u)d(u,v)+d(v,w)d(u,w)G=<V,E>,VV點割集￡op(GV)>p(G)，且對任意VV均有p(GV)=p(G)￡??òV為點割集割點￡o{v}為點割集，那么v為割點【定義14.15】G=<V,E>,EE邊割集￡op(GE)>p(G)且有極小性那么E是邊割集割邊〔橋〕￡o{e}為邊割集e是割邊〔橋〕【定義14.16】G為連通非完全圖點連通度(G)=min{|V|V為點割集}?￡規(guī)定(K)=n1;假設(shè)G非連通，(G)=0nk-連通圖：假設(shè)(G)k，那么稱G為k-連通圖【定義14.17】設(shè)G為連通圖邊連通度(G)=min{|E|E為邊割集}規(guī)定：假設(shè)G非連通，那么(G)=0r邊-連通圖：假設(shè)(G)r，那么稱G是r邊-連通圖【定義14.18】-.word.zl-..-,,之間的關(guān)系：(G)(G)(G)【定理14.7】D=<V,E>為有向圖可達vv：存在從v到v有通路ijij相互可達vv：vv?òvv【定義14.19】ijijjiD=<V,E>為有向圖弱連通(連通)￡o基圖為無向連通圖單向連通￡ov,vV，vv或vvijijji強連通￡ov,vV，vv【定義14.21】ijij有向圖的連通性判別法：(1)D強連通當且僅當D中存在經(jīng)過每個頂點至少一次的回路；【定理14.8】(2)D單向連通當且僅當D中存在經(jīng)過每個頂點至少一次的通路?！径ɡ?4.9】二部圖(二分圖)(偶圖)￡o設(shè)G=<V,E>為一個無向圖，假設(shè)能將V分成V和V(VV=V，1212V=)，使得G中的每條邊的兩個端點都是一個屬于V，另一個屬于V，那么稱G為二部V1212圖(或稱二分圖、偶圖等)，稱V和V為互補頂點子集，常將二部圖G記為<V,V,E>.1212完全二部圖：假設(shè)G是簡單二部圖，V中每個頂點均與V中所有的頂點相鄰，那么稱G為完全12二部圖，記為K，其中r=|V|，s=|V|.【定義14.22】r,s12二部圖的判別法：無向圖G=<V,E>是二部圖當且僅當G中無奇圈?！径ɡ?4.10】關(guān)聯(lián)矩陣M(G)￡o無向圖G=<V,E>，|V|=n，|E|=m，令m為v與e的關(guān)聯(lián)次數(shù)，稱(m)為ijnmijijG的，記為M(G).【定義14.23】nm2(j1,2,...,m)(1)i1(2)mijmd(v)(i1,2,...,n)(3)j1m2mijiiji,j(4)平行邊的列一樣關(guān)聯(lián)矩陣M(D)：有向圖D=<V,E>，令那么稱(m)為D的關(guān)聯(lián)矩陣，記為.ijnmv為e的始點j1,【定義14.24】im0,v與e不關(guān)聯(lián)ijij1,v為e的終點ijnm0(j1,2,...,m)(1)(2)im1ij(m1)d(v),m(m1)d(v),i1,2,...,nj1(3)m0ijij1ijiiji,j(4)平行邊對應(yīng)的列一樣鄰接矩陣：設(shè)D＝(V,E)是有向圖，V={v,….,v}，構(gòu)造矩陣A=[a]如下：i,j(1i,jn)1nijk若從v到v有K條邊aij稱A為圖D的鄰接矩陣。【定義14.25】ij0若從v到v沒有邊ij-.word.zl-

..-na(1)d(v),i1,2,...,ni(1)j1ij(2)na(1)d(v),j1,2,...,nji1ij(3)a(1)mD中長度為1的通路數(shù)iji,j(4)na(1)D中長度為1的回路數(shù)i1ii鄰接矩陣的含義：設(shè)A為有向圖D的鄰接矩陣，V={v,v,…,v}為頂點集，那么A的l次冪12naij到v長度為l的通路數(shù)，其中a()l為v到自身長度為l的回路數(shù)，jiiAl〔l1〕中元素()l為D中vii而nna()l為D中長度為l的通路總數(shù)，naiii1為D中長度為l的回路總數(shù).【定理14.11】()liji1j11,v可達vp0,?否則可達矩陣P(D)：設(shè)D=<V,E>為有向圖.V={v,v,…,v},令j稱i12nij(p)為D的可達矩陣，記作P(D)，簡記為P.【定義14.26】ijnn歐拉通路￡o經(jīng)過圖〔無向圖或有向圖〕中每條邊一次且僅一次行遍所有頂點的通路.歐拉回路￡o經(jīng)過圖中每條邊一次且僅一次行遍所有頂點的回路.歐拉圖￡o具有歐拉回路的圖.半歐拉圖￡o具有歐拉通路而無歐拉回路的圖【定義15.1】平凡圖是歐拉圖.歐拉通路是簡單通路，歐拉回路是簡單回路無向歐拉圖的判別法