離散數(shù)學知識點

離散數(shù)學知識點離散數(shù)學知識點/離散數(shù)學知識點說明： 定義：紅色表示。 定理性質(zhì)：橙色表示。 公式：藍色表示。 算法:綠色表示 頁碼：灰色表示數(shù)理邏輯：命題公式：命題，聯(lián)結詞(，，，，)，合式公式，子公式公式的真值：賦值，求值函數(shù)，真值表，等值式，重言式，矛盾式范式：析取范式，極小項，主析取范式，合取范式，極大項，主合取范式聯(lián)結詞的完備集：真值函數(shù)，異或，條件否定，與非，或非，聯(lián)結詞完備集推理理論：重言蘊含式，有效結論，P規(guī)則，T規(guī)則，規(guī)則，推理謂詞與量詞:謂詞，個體詞，論域，全稱量詞，存在量詞項與公式:項，原子公式，合式公式，自由變元，約束變元，轄域，換名，代入公式語義:解釋，賦值，有效的，可滿足的，不可滿足的前束范式:前束范式推理理論:邏輯蘊含式，有效結論，-規(guī)則（），+規(guī)則（），-規(guī)則()，+規(guī)則(),推理集合論：集合:集合,外延性原理,,,,空集,全集,冪集,文氏圖,交,并,差,補,對稱差關系:序偶,笛卡爾積,關系,,,關系圖,空關系,全域關系,恒等關系關系性質(zhì)與閉包:自反的,反自反的,對稱的,反對稱的,傳遞的,自反閉包r(R),對稱閉包s(R),傳遞閉包t(R)等價關系:等價關系,等價類,商集,劃分偏序關系:偏序,哈斯圖,全序(線序),極大元/極小元,最大元/最小元,上界/下界函數(shù):函數(shù),常函數(shù),恒等函數(shù),滿射,入射,雙射，反函數(shù),復合函數(shù)集合基數(shù):基數(shù),等勢,有限集/無限集,可數(shù)集,不可數(shù)集代數(shù)結構：運算與其性質(zhì)：運算，封閉的,可交換的,可結合的,可分配的,吸收律,冪等的，幺元,零元,逆元代數(shù)系統(tǒng)：代數(shù)系統(tǒng)，子代數(shù)，積代數(shù)，同態(tài)，同構。群與子群：半群,子半群,元素的冪，獨異點，群，群的階數(shù)，子群,平凡子群，陪集，拉格朗日（）定理阿貝爾群和循環(huán)群：阿貝爾群(交換群)，循環(huán)群,生成元環(huán)與域：環(huán)，交換環(huán)，含幺環(huán)，整環(huán)，域格與布爾代數(shù)：格，對偶原理，子格，分配格，有界格，有補格，布爾代數(shù)，有限布爾代數(shù)的表示定理圖論：圖的基本概念：無向圖、有向圖、關聯(lián)與相鄰、簡單圖、完全圖、正則圖、子圖、補圖，握手定理，圖的同構圖的連通性:通路，回路，簡單通路，簡單回路（跡）初級通路（路徑），初級回路（圈），點連通，連通圖，點割集，割點，邊割集，割邊，點連通度，邊連通度，弱連通圖，單向連通圖，強連通圖，二部圖（二分圖）圖的矩陣表示：關聯(lián)矩陣，鄰接矩陣，可達矩陣歐拉圖與哈密頓圖：歐拉通路、歐拉回路、歐拉圖、半歐拉圖，哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖無向樹與根樹：無向樹，生成樹，最小生成樹，，根樹，m叉樹，最優(yōu)二叉樹，算法平面圖:平面圖，面，歐拉公式，定理數(shù)理邏輯：命題：具有確定真值的陳述句。否定詞符號：設p是一個命題，p稱為p的否定式。p是真的當且僅當p是假的。p是真的當且僅當p是假的?！径x1.1】合取詞符號：設p，q是兩個命題，命題“p并且q”稱為p，q的合取，記以pq，讀作p且q。pq是真的當且僅當p和q都是真的?！径x1.2】析取詞符號：設p，q是兩個命題，命題“p或者q”稱為p，q的析取，記以pq，讀作p或q。pq是真的當且僅當p，q中至少有一個是真的?！径x1.3】蘊含詞符號：設p，q是兩個命題，命題“如果p，則q”稱為p蘊含q，記以pq。pq是假的當且僅當p是真的而q是假的?！径x1.4】等價詞符號：設p，q是兩個命題，命題“p當且僅當q”稱為p等價q，記以pq。pq是真的當且僅當p，q或者都是真的，或者都是假的?！径x1.5】合式公式:命題常元和變元符號是合式公式；若A是合式公式，則(A)是合式公式，稱為A的否定式；若A，B是合式公式，則(AB)，(AB)，(AB)，(AB)是合式公式；所有合式公式都是有限次使用(1)，(2)，(3)、(4)得到的符號串。子公式:如果Ｘ是合式公式A的一部分，且Ｘ本身也是一個合式公式，則稱Ｘ為公式A的子公式。【定義1.6】賦值（指派，解釋）：設是命題變元集合，則稱函數(shù)v：{1，0}是一個真值賦值?！径x1.8】真值表：公式A在其所有可能的賦值下所取真值的表，稱為A的真值表?！径x1.9】重言式（永真式）:任意賦值v，vA矛盾式（永假式）:任意賦值v，有vA【定義1.10】等值式：若等價式AB是重言式，則稱A與B等值，記作AB。【定義2.1】基本等值式 雙重否定律 AA冪等律AAA,AAA交換律ABBA,ABBA結合律(AB)CA(BC),(AB)CA(BC)分配律A(BC)(AB)(AC),A(BC)(AB)(AC)德摩根律 (AB)AB ,(AB)AB吸收律A(AB)A,A(AB)A 零律A,A同一律 AA,AA排中律AA矛盾律AA蘊涵等值式ABAB等價等值式AB(AB)(BA)假言易位ABBA等價否定等值式ABAB歸謬論(AB)(AB)A置換規(guī)則：設Ｘ是公式A的子公式,ＸY。將A中的Ｘ（可以是全部或部分X）用Y來置換，所得到的公式B，則AB。文字:設A（命題變元集）,則A和A都稱為命題符號A的文字，其中前者稱為正文字，后者稱為負文字。【定義2.2】析取范式：形如A1A2…(n1)的公式稱為析取范式，其中(1,…)是由文字組成的合取范式。合取范式：形為A1A2…(n1)的公式稱為合取范式，其中A1,…都是由文字組成的析取式?！径x2.3】極小項：文字的合取式稱為極小項，其中公式中每個命題符號的文字都在該合取式中出現(xiàn)一次。極大項：文字的析取式稱為極大項，其中公式中每個命題符號的文字都在該合取式中出現(xiàn)一次?！径x2.4】主析取范式：給定的命題公式的主析取范式是一個與之等價的公式，后者由極小項的析取組成。主合取范式：給定的命題公式的主合取范式是一個與之等價的公式，后者由極大項的合取組成?！径x2.5】公式的真值表中真值為F的指派所對應的極大項的合取，即為此公式的主合取范式。真值函數(shù)：稱F:{0,1}n{0,1}為n元真值函數(shù).【定義2.6】聯(lián)結詞的完備集：設C是聯(lián)結詞的集合，若對于任意一個合式公式均存在一個與之等價的公式，而后者只含有C中的聯(lián)結詞，則稱C是聯(lián)結詞的完備集?！径x2.7】{，，，，}，{，，},{，}，{，}，{，}是聯(lián)結詞的完備集?！径ɡ?.6】c異或PQ： (PQ)c條件否定PQ：(PQ)與非PQ： (PQ)或非PQ： (PQ)【定義2.8】{},{↓}都是聯(lián)結詞的完備集【定理2.7】重言蘊含式：當且僅當PQ是一個重言式時，稱P重言蘊含Q，記為PQ。有效結論：設A、C是兩個命題公式，若AC，稱C是A的有效結論。【定義3.1】推理定律——重言蘊涵式 1.A(AB) 附加律2.(AB)A 化簡律3.(AB)AB 假言推理4.(AB)BA 拒取式5.(AB)BA 析取三段論6.(AB)(BC)(AC) 假言三段論7.(AB)(BC)(AC) 等價三段論8.(AB)(CD)(AC)(BD) 構造性二難 (AB)(AB)B 構造性二難(特殊形式)9.(AB)(CD)(BD)(AC) 破壞性二難形式系統(tǒng):一個形式系統(tǒng)I由下面四個部分組成： (1)非空的字母表，記作A(I). (2)A(I)中符號構造的合式公式集，記作E(I). (3)E(I)中一些特殊的公式組成的公理集，記作(I). (4)推理規(guī)則集，記作R(I).記<A(I)(I)(I)(I)>,其中<A(I)(I)>是I的形式語言系統(tǒng),<(I)(I)>是I的形式演算系統(tǒng).自然推理系統(tǒng):無公理,即(I)=公理推理系統(tǒng):推出的結論是系統(tǒng)中的重言式,稱作定理【定義3.2】P規(guī)則：在推導過程中,可以隨時添加前提。T規(guī)則：在推導過程中,可以引入公式S，它是由其前題的一個或多個公式借助重言、蘊含而得到的。推理（證明）：從前提A1,A2,,到結論B的推理是一個公式序列C1,C2,,.其中(1il)是某個,或者可由序列中前面的公式應用推理規(guī)則得到,并且?！径x3.3】規(guī)則(演繹定理)：若{R}S，則RS,其中為命題公式的集合。個體詞：用于表示命題中主語部分的符號或符號串。個體常元表示確指個體。個體變元表示不確指個體。個體域:個體變元的取值范圍，常用D表示。量詞：限定個體數(shù)量特性的詞。全稱量詞：對所有的存在量詞：有些謂詞語言：用符號串表示個體、謂詞、量詞和命題 個體變元符號：x，y，z，… 個體常元符號：a，b，c，… 函數(shù)符號：f，g，… 謂詞符號：P，Q，R，… 命題常元符號：， 量詞符號：， 連接詞符號：,,,, 輔助符號：）,（ 【定義4.1】項:(1)個體常元和變元是項；(2)若f是n元函數(shù)符號，t1,…,是項，則f(t1,…,)是項；(3)僅僅有限次使用(1)，(2)產(chǎn)生的符號串是項?！径x4.2】原子公式:若P是一個元謂詞符號，t1,…是項,則P(t1,…)是原子公式。【定義4.3】合式公式：(1)原子公式是公式；(2)若A是合式公式，則(A)是合式公式；(3)若A，B是公式，則(AB)，(AB)，AB)，(AB)是公式；(4)若A是公式，x是變元，則，是公式；(5)僅僅有限次使用１～４得到的符號串才是合式公式?！径x4.4】設公式的一個子公式為xA或xA。則稱：指導變元：x是或的指導變元。轄域：A是相應量詞的轄域。約束出現(xiàn)：轄域中x的一切出現(xiàn)，以與(x)中的x稱為x在中的約束出現(xiàn)。自由出現(xiàn)：變元的非約束出現(xiàn)。約束變元：約束出現(xiàn)的變元。自由變元：自由出現(xiàn)的變元?！径x4.5】封閉的：一個公式A是封閉的，若其中不含自由變元。【定義4.6】變元換名：（1）換名的范圍是量詞的指導變元,與其相應轄域中的變元，其余部分不變。（2）換名時最好選用轄域中未出現(xiàn)的變元名。變元代入：代入對自由變元進行。不能改變約束關系。解釋：謂詞語言的一個解釋(D,)包括：(1)非空集合D，稱之為論域；(2)對應于每一個個體常元a，(a)D；(3)對應于每一個n元函數(shù)符號f都有一個函數(shù)(f)D；(4)對應于每一個n元謂詞符號A都有一個n元關系(A)?！径x4.7】賦值：解釋I中的賦值v為每一個個體變元x指定一個值v(x）D，即設V為所個體變元的集合，則賦值v是函數(shù)D.可滿足的：給定公式A，若在某一解釋中至少有一種賦值使A取值為1，則稱A為可滿足的。否則稱A是不可滿足的。等值式AB：若AB是有效的【定義5.1】幾類等值式（1）命題公式的推廣.P(x)Q(x)P(x)Q(x)（2）否定深入xP(x)x(P(x))(x)x(P(x))（3）量詞作用域的擴張與收縮 設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()yxA() xyA()yxA()置換規(guī)則：設(A)是含A的公式,那么,若AB,則(A)(B).換名規(guī)則：設A為一公式，將A中某量詞轄域中個體變項的所有約束出現(xiàn)與相應的指導變元換成該量詞轄域中未曾出現(xiàn)過的個體變項符號，其余部分不變，設所得公式為A，則AA.前束范式：如果謂詞公式A有如下形狀：Q1x1…，其中或者是，或者是，1，…，n，M是不含量詞的公式，Q1x1…稱為首標，M稱為母式?！径x5.2】前束范式存在定理：對于任意謂詞公式，都存在與它邏輯等價的前束范式。【定理5.1】前束范式的算法：步1.對約束出現(xiàn)的變元進行必要的換名，使得約束出現(xiàn)的變元互不相同且不與任何自由變元同名。步2.將所有的否定號深入到量詞后面。 步3.將量詞符號移至公式最外層。邏輯蘊含式AC：當且僅當AC是有效的。幾類邏輯蘊涵式 第一組命題邏輯推理定理的代換實例 如,(x)(y)(x)第二組基本等值式生成的推理定理 如,(x)(x),(x)(x)(x)xF(x),xF(x)(x)第三組其它常用推理定律 (1)(x)(x)x(A(x)B(x)) (2)x(A(x)B(x))(x)(x) (3)x(A(x)B(x))(x)(x) (4)x(A(x)B(x))(x)(x)推理規(guī)則 -規(guī)則()：?xAx∴Ay或? +規(guī)則()：Ax∴?xAx -規(guī)則()：∴?xAx∴Ac x +規(guī)則()：Ay∴?xAx或B Ac∴? 先用，再用自然推理系統(tǒng)NL：1.字母表.同一階語言L的字母表2.合式公式.同L的合式公式3.推理規(guī)則:(1)前提引入規(guī)則 (2)結論引入規(guī)則(3)置換規(guī)則(4)假言推理規(guī)則(5)附加規(guī)則(6)化簡規(guī)則(7)拒取式(8)假言三段論規(guī)則(9)析取三段論規(guī)則(10)構造性二難推理規(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)2n全集E：包含了所有元素的集合【定義6.6】并AB={x|xAxB}交AB={x|xAxB}差（相對補）AB={x|xAxB}【定義6.7】對稱差AB=(AB)(BA)【定義6.8】補（絕對補）A=EA={A}【定義6.9】廣義并A={x|z(zAxz)}【定義6.10】廣義交A={x|z(zAxz)}【定義6.11】集合恒等式1.只涉與一個運算的算律：交換AAAAAA結合(AB)(BC)(AB)(BC)(AB)(BC)冪等AA2．涉與兩個不同運算的算律：與與分配A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)吸收A(AB)A(AB)3．涉與補運算的算律：律A(BC)=(AB)(AC)A(BC)=(AB)(AC)(BC)=BC(BC)=BC雙重否定4．涉與全集和空集的算律：E補元律AA零律A=A同一律AA否定序偶（有序?qū)Γ河蓛蓚€元素x和y，按照一定的順序組成的二元組，記作<>.【定義7.1】笛卡兒積:設為集合，A與B的笛卡兒積記作AB定義為AB={<>|xAyB}.【定義7.2】笛卡爾積性質(zhì)：或時,A“”不滿足結合律A(BC)=(AB)(AC)關系：（兩個定義）(1)序偶的一個集合,確定了一個二元關系R。R中任一序偶<>,可記作<x,y>R或【定義7.3】(2)笛卡爾積的子集：RAB【定義7.4】空關系:全域關系：A×B恒等關系={<>|x∈A} 【定義7.5】關系矩陣：若{x1,x2,…,}，{y1,y2,…,}，R是從A到B的關系，R的關系矩陣是布爾矩陣=[]mn,其中=1<,>R.關系圖：若{x1,x2,…,}，R是從A上的關系，R的關系圖是<A,R>,其中A為結點集，R為邊集.如果<>屬于關系R，在圖中就有一條從到的有向邊.前域(定義域)(R)={y.<>R} 值域(R)={x.<>R}域(R)= 【定義7.6】逆關系R1={<y,x>|<x,y>R} 【定義7.7】互逆(R1)1=R(RS)1=R1S1(RS)1=R1S1(AB)1=BA(R-S)1=R1-S1復合關系RS={<x,z>|y(<x,y>R<y,z>S)}【定義7.8】(RS)(SP)=RR…R設RXYZ,則(RS)1=S1R1【定理7.2】R在A上的限制R?A={<>|∧x∈A} A在R下的像R[A](R?A) 【定義7.9】自反的：若x∈A，都有<>R,則稱R是自反的反自反的：若x∈A，都有<>R,則稱R是反自反的.【定義7.11】對稱的：對任意A,滿足,若<>R,則<>R反對稱的：對任意A,滿足，若<>R且<>R,則【定義7.12】傳遞的：對任意的A,滿足:若<>R且<>R,則<>R,則稱R是傳遞的【定義7.13】自反閉包（對稱、傳遞）：設R是A上的二元關系,如果有另一個關系R'滿足:R'是自反（對稱、傳遞）的;R'R;對于任何自反的關系R”,若R"R,則有R"R'.則稱關系R'為R的自反閉包.記為r(R)（

對稱閉包s(R)和傳遞閉包t(R)）?！径x7.14】設R為A上的關系,則有(1)r(R)∪(2)s(R)∪R1(3)t(R)∪R2∪R3∪…（若，則t(R)∪R2∪…∪）等價關系：設R為集合A上的一個二元關系。若R是自反的,對稱的,傳遞的,則稱R為A上的等價關系【定義7.15】等價類：設R為集合A上的等價關系,對aA,定義:[a]R={A且<>R}稱之為元素a關于R的等價類?！径x7.16】給定A上的等價關系R,對于A有<>當且僅當[a][b]R【定理17.4】商集：設R是A上的等價關系，定義{[a]A}稱之為A關于R的商集.【定義7.17】劃分：設A為非空集合,若A的子集族π(πP(A))滿足: (1)π (2)xy(π∧x≠yx∩) (3)∪π=A則稱π是A的一個劃分,稱π中的元素為A的劃分塊.【定義7.18】給定集合A上的等價關系R,則商集是A的一個劃分.集合A的一個劃分π誘導出A上的一個等價關系R.R定義為{<>|A且在π的同一分塊中}設R1和R2為非空集合A上的一個等價關系,則R1=R2當且僅當1=2.偏序：設A是一個集合.如果A上的二元關系R是自反的,反對稱的和傳遞的,則稱R是A上的一個偏序關系.記R為“”,且稱序偶<A,>為偏序集?！径x7.19】【定義7.22】全序（線序）：設<A,>為偏序集,若對任意的A滿足:xy或yx則稱為全序關系.<A,>為全序集.【定義7.21】覆蓋：設<A,>為偏序集,若A,xy且沒有其它元素z滿足xy,則稱y覆蓋x.記{<>A且y覆蓋x}【定義7.23】哈斯圖：作圖規(guī)則用小元圈代表元素;若xy且xy,則將代表y的小元圈畫在代表x的小元圈之上;若<>,則在之間用直線連接。你極小元/極大元：設<A,>為偏序集,BA(1)對bB，若B中不存在x滿足:bx且xb則稱b為B的極小元.(2)對bB，若B中不存在x滿足:bx且bx則稱b為B的極大元.最小元/最大元：設<A,>為偏序集A,若有某個bB(1)對于B中每一個元素x都有bx，則稱b為B的最小元.(2)對于B中每一個元素x都有xb，則稱b為B的最大元.【定義7.24】下界/上界：設<A,>為偏序集,BA (1)若有aA,且對xB滿足ax，則稱a為B的下界。進一步:設a為B的下界,若B的所有下界y均有ya,則稱a為B的下確界，記為B。 (2)若有aA,且對xB滿足xa，則稱a為B的上界。進一步:設a為B的上界,若B的所有上界y均有ay,則稱a為B的上確界，記為B?！径x7.25】函數(shù)：設為兩個集合XY,若對xX,!(唯一的)yY,滿足:<>f,則稱f為函數(shù).記為Y定義域:值域:(有時記為f(X))={f(x)X}【定義8.1】函數(shù)相等：設f和g都是從A到B的函數(shù),若對任意xA,有f(x)(x),則稱f和g相等.記為【定義8.2】函數(shù)的個數(shù)：設,.記{:AB},則|滿射(到上映射)：設f:XY,若=Y,則稱f為滿射的.入射（單射）(一對一映射)：設f:XY,對x1,x2X,滿足:若x1x2,則f(x1)f(x2),稱f為入射的.雙射(一一對應映射)：設Y,若f既是滿射的,又是入射的.則稱f是雙射的.【定義8.6】常函數(shù):設→B,如果存在c∈B使得對所有的x∈A都有f(x),則稱→B是常函數(shù).恒等函數(shù):稱A上的恒等關系為A上的恒等函數(shù),對所有的x∈A都有(x).單調(diào)遞增:設<A,?>,<B,?>為偏序集，→B，如果對任意的x1,x2∈A,x1?x2,就有f(x1)?f(x2),則稱f為單調(diào)遞增的；嚴格單調(diào)遞增:如果對任意的x1,x2∈A,x1?x2,就有f(x1)?f(x2),則稱f為嚴格單調(diào)遞增的.類似的也可以定義單調(diào)遞減和嚴格單調(diào)遞減的函數(shù) 特征函數(shù)：設A為集合,對于任意的A'A,A'的特征函數(shù)A'→{0,1}定義為A'(a)=1,a∈A';A'(a)=0,a∈AA'自然映射：設R是A上的等價關系,令→；g(a)=[a],a∈A稱g是從A到商集的自然映射 【定義8.7】復合函數(shù)：設Z,定義:fg={<>X且zZ且可找到y(tǒng)Y使(x)(y)}稱fg為f與g的復合函數(shù).設→B,→C

(1)如果→B,→C是滿射的,則f→C也是滿射的(2)如果→B,→C是單射的,則f→C也是單射的

(3)如果→B,→C是雙射的,則f→C也是雙射的

【定理8.2】反函數(shù)（逆函數(shù)）：設Y是一個雙射函數(shù)，那么f-1是YX的雙射函數(shù).稱f-1為f的反函數(shù).互逆(f-1)-1設→B是雙射的,則f1f=,ff1=【定理8.5】基數(shù)：用來衡量集合大小的一個概念.對于有限集合集來說,集合的基數(shù)就是其中所含元素的個數(shù).等勢的：設A,B是集合,如果存在著從A到B的雙射函數(shù),就稱A和B是等勢的,記作A≈B.如果A不與B等勢,則記作A?B. 注：通常將A的基數(shù)記為.【定義8.8】N≈Z≈Q≈N×N任何實數(shù)區(qū)間都與實數(shù)集合R等勢{0,1}N≈R康托定理N?R；對任意集合A都有A?P(A).【定義8.7】有限集(有窮集)/無限集(無窮集)：設A為一個集合.若存在某個自然數(shù)n,使得A與集合{0,1,…1}等勢,則稱A是有限的.若集合A不是有限的,則稱A是無限的.【定義8.11】：實數(shù)集R的基數(shù)記作,即=【定義8.12】可數(shù)集(可列集)：設A為集合，若≤0，則稱A為可數(shù)集或可列集?！径x8.14】與自然數(shù)集N等勢的任意集合稱為可數(shù)的.其基數(shù)為0結論： (1)A為可數(shù)的當且僅當可排列成{a12,…,…}的形式.(2)任一無限集必含有可數(shù)子集.(3)可數(shù)集的任何無限子集是可數(shù)的.(4)可數(shù)個兩兩不相交的可數(shù)集合的并集,仍是一個可數(shù)集.(5)NN是可數(shù)集.(6)有理數(shù)的全體組成的集合是可數(shù)集.(7)全體實數(shù)構成的集合R是不可數(shù)的.基數(shù)的常識：對于有窮集合A,基數(shù)是其元素個數(shù)n，=n;沒有最大的基數(shù)。將已知的基數(shù)按從小到大的順序排列就得到：0,1,2,…,n,…,0,,…代數(shù)結構運算：對于集合A，f是從到A的函數(shù)，稱f為集合A上的一個n元運算?！径x9.1】交換律：已知<A，*>，若x，y∈A，有x**x，稱*在A上是可交換的?！径x9.3】結合律：已知<A，*>，若x，y，z∈A，有x*（y*z）=（x*y）*z，稱*在A上是可結合的?！径x9.4】冪等律：已知〈A，*〉，若x∈A，x*則稱滿足冪等律?！径x9.5】分配律：設<A，*，△>，若x，y，z∈A有:x*(y△z)=（x*y）△（x*z）;(y△z)*(y*x)△(z*x)稱運算*對△是可分配的?！径x9.6】吸收律：設,是定義在集合A上的兩個可交換二元運算，若對A,都有(xy)=x；x(xy)=x則稱運算和滿足吸收律.【定義9.7】單位元（幺元）:設*是A上二元運算，,A 左幺元：若xA，有*，稱為運算*的左幺元； 右幺元：若xA，有x*，稱為運算*的右幺元；若e既是左幺元又是右幺元，稱e為運算*的幺元【定義9.8】設*是A上的二元運算，具有左幺元，右幺元，則【定理9.1】零元:設*是A上二元運算，l,r,A 左零元：若xA，有l(wèi)*l，稱l為運算*的左零元； 右零元： 若xA，有x*r，稱r為運算*的右零元；若既是左零元又是右零元，稱為運算*的零元。【定義9.9】設*是A上的二元運算，具有左零元l，右零元r，則【定理9.2】逆元：設*是A上的二元運算，e是運算*的幺元，若x*那對于運算*，x是y的左逆元，y是x的右逆元存在逆元(左逆無，右逆元）的元素稱為可逆的（左可逆的，右可逆的）【定義9.10】對于可結合運算ο，如果元素x有左逆元ｌ，右逆元r，則－１【定理9.4】消去律：已知<A，*>，若x，y，z∈A，有(1)若x*y=x*z且x,則；(左消去律)(2)若y*x=z*x且x,則；（右消去律）那么稱*滿足消去律?！径x9.11】代數(shù)系統(tǒng)：設A為非空集合，為A上運算的集合,稱<A,>為一個代數(shù)系統(tǒng).【定義9.12】同類型的代數(shù)系統(tǒng)：如果兩個代數(shù)系統(tǒng)中運算的個數(shù)相同，對應運算的元數(shù)相同，且代數(shù)常數(shù)的個數(shù)也相同，則稱它們是同類型的代數(shù)系統(tǒng).【定義9.13】子代數(shù)：設<S,f1,f2,…,>是代數(shù)系統(tǒng)，B是S的非空子集，如果B對f1,f2,…,都是封閉的，且B和S含有相同的代數(shù)常數(shù)，則稱<B,f1,f2,…,>是V的子代數(shù)系統(tǒng)，簡稱子代數(shù)【定義9.14】最大的子代數(shù)：就是V本身最小的子代數(shù)：如果令V中所有代數(shù)常數(shù)構成的集合是B，且B對V中所有的運算都是封閉的，則B就構成了V的最小的子代數(shù)平凡的子代數(shù):最大和最小的子代數(shù)稱為V的平凡的子代數(shù)真子代數(shù)：若B是S的真子集，則B構成的子代數(shù)稱為V的真子代數(shù).因子代數(shù)：設V1=<A,?>和V2=<B,>是同類型的代數(shù)系統(tǒng)，?和為二元運算，在集合AB上如下定義二元運算?，<a11>,<a22>AB，有<a11>?<a22>=<a1?a2,b1b2>稱<AB,?>為V1與V2的積代數(shù)，記作V1V2.這時也稱V1和V2為V的因子代數(shù).【定義9.15】設V1=<A,?>和V2=<B,>是同類型的代數(shù)系統(tǒng)，V1V2=<AB,?>是它們的積代數(shù).(1)如果?和運算是可交換（可結合、冪等）的，那幺?運算也是可交換（可結合、冪等）的(2)如果e1和e2（1和2）分別為?和運算的單位元（零元），那幺<e12>（<1,2>）也是?運算的單位元（零元）(3)如果x和y分別為?和運算的可逆元素，那幺<>也是?運算的可逆元素，其逆元就是<x11>【定理9.5】同態(tài):設V1=<A,°>和V2=<B,>是同類型的代數(shù)系統(tǒng)，B，對x,yA有f(x°y)=f(x)f(y),則稱f是V1到V2的同態(tài)映射，簡稱同態(tài)(1)f如果是單射，則稱為單同態(tài)。(2)如果是滿射，則稱為滿同態(tài)，這時稱V2是V1的同態(tài)像，記作V1V2。(3)如果是雙射，則稱為同構，也稱代數(shù)系統(tǒng)V1同構于V2，記作V1V2。(4)如果V12，則稱作自同態(tài)?！径x9.16】半群：設<S,°>是代數(shù)系統(tǒng)，°為二元運算，如果°運算是可結合的，則稱V為半群。獨異點：設<S,°>是半群，若e∈S是關于°運算的單位元，則稱V是含幺半群，也叫做獨異點。有時也將獨異點V記作<S,°>.群：設<G,°>是獨異點，eG關于°運算的單位元，若aG，a1G，則稱V是群().通常將群記作G.【定義10.1】群的階數(shù)：設<G,>是一個群 有限群：如果G是有限集，那么稱<G,>為有限群 階數(shù)：為該有限群的階數(shù)； 無限群：如果G是無限集，則稱<G,>為無限群。平凡群：階數(shù)為1（即只含單位元）的群稱為平凡群【定義10.2】群的性質(zhì)：設<G,>是一個群。（1）非平凡群中不可能有零元.（2）對于G,必存在唯一的xG,使得ax.（3）對于{}G若:ab=ac或ba=ca則必有(消去律)。（4）運算表中的每一行或每一列都是一個置換。（5）除幺元e外,不可能有任何別的冪等元。元素的冪：設G是群，a∈G，n∈Z，則a的n次冪【定義10.3】元素的階：設G是群，a∈G，使得等式成立的最小正整數(shù)k稱為元素a的階，記作，稱a為k階元。若不存在這樣的正整數(shù)k，則稱a為無限階元?！径x10.4】冪運算性質(zhì)： (1)a∈G，(a1)1 (2)∈G，()11a1 (3)a∈G，=，n,m∈Z (4)a∈G，()m=，n,m∈Z (5)若G為交換群，則()n=.【定理10.1】元素的階的性質(zhì)：G為群，a∈G且=r.設k是整數(shù)，則(1)=e當且僅當r|k(r整除k)(2)1|=【定理10.3】子群：設G是群，H是G的非空子集，如果H關于G中的運算構成群，則稱H是G的子群,記作H≤G。真子群：若H是G的子群，且HG，則稱H是G的真子群，記作H<G.平凡子群：對任何群G都存在子群.G和{e}都是G的子群，稱為G的平凡子群.【定義10.5】子群判定定理一：設G為群，H是G的非空子集，則H是G的子群當且僅當(1)∈H有∈H；(2)a∈H有a1∈H。【定理10.4】子群判定定理二：設G為群，H是G的非空子集.H是G的子群當且僅當∈H有1∈H.

【定理10.5】子群判定定理三：設G為群，H是G的非空有窮子集，則H是G的子群當且僅當∈H有∈H.【定理10.6】生成子群：設G為群，a∈G，令{k∈Z}，則H是G的子群，稱為由a生成的子群，記作<a>.陪集：設<H,>是群<G,>的一個子群G則: 左陪集：{a}H，由a所確定的H在G中的左陪集. 右陪集：{a}陪集是左陪集與右陪集的統(tǒng)稱.

【定義10.6】陪集性質(zhì)：設H是群G的子群，則=Ha∈G有a∈∈G有：a∈1∈H在G上定義二元關系R：∈G,<>∈R1∈H則R是G上的等價關系，且[a]R=. 【定理10.7】【定理10.8】拉格朗日定理：設G是有限群，H是G的子群，則=·[]其中[]是H在G中的不同右陪集(或左陪集)數(shù)，稱為H在G中的指數(shù).【定理10.10】推論：（1）設G是n階群，則a∈G，是n的因子，且=e.（2）對階為素數(shù)的群G，必存在a∈G使得G=<a>.阿貝爾群（交換群）：若群G中的運算是可交換的，則稱G為交換群或阿貝爾群。循環(huán)群：設G是群，若存在a∈G使得{k∈Z}則稱G是循環(huán)群，記作<a>，稱a為G的生成元.

n階循環(huán)群:設<a>是循環(huán)群，若a是n階元，則G={a0,a1,a2,…,1}無限循環(huán)群:若a是無限階元，則G={a0,a±1,a±2,…}【定義10.7】循環(huán)群的生成元:設<a>是循環(huán)群(1)若G是無限循環(huán)群，則G只有兩個生成元，即a和a1.

(2)若G是n階循環(huán)群，則G含有(n)個生成元.對于任何小于n且與n互質(zhì)的數(shù)r∈{0,1,…1},是G的生成元.【定理10.11】循環(huán)群的子群：(1)設<a>是循環(huán)群，則G的子群仍是循環(huán)群；(2)若<a>是無限循環(huán)群，則G的子群除{e}以外都是無限循環(huán)群；(3)若<a>是n階循環(huán)群，則對n的每個正因子d，G恰好含有一個d階子群。【定理10.12】環(huán)：設<,·>是代數(shù)系統(tǒng)，+和·是二元運算.如果滿足以下條件:(1)<>構成交換群；(2)<R,·>構成半群；(3)·運算關于+運算適合分配律，則稱<,·>是一個環(huán).【定義10.11】環(huán)的運算性質(zhì)：設<,·>是環(huán)，則(1)a∈R，a0=0a=0(2)∈R，(a)b=a(b)=(3)∈R，a(bc)=，(bc)a=(4)a1212∈R(≥2)i=1nai設<,·>是環(huán) 交換環(huán)：若環(huán)中乘法·適合交換律，則稱R是交換環(huán)；含幺環(huán)：若環(huán)中乘法·存在單位元，則稱R是含幺環(huán)；無零因子環(huán)：若∈R，00∨0，則稱R是無零因子環(huán)。整環(huán)：設<,>是一個代數(shù)系統(tǒng),若滿足:(1)<>是阿貝爾群；(2)<R,>是可交換獨異點，且無零因子，即對R,a00則ab0；(3)運算對+是可分配的，則稱<,>是整環(huán)域：設<,>是一個代數(shù)系統(tǒng),若滿足:(1)<>是阿貝爾群；(2)<{0},>是阿貝爾群；(3)運算對+是可分配的，則稱<,>是域?！径x10.12】格：設<S,?>是偏序集，如果S，{}都有最小上界和最大下界，則稱S關于偏序?作成一個格【定義11.1】格的代數(shù)系統(tǒng)定義：設<S,?,?>是代數(shù)系統(tǒng),?和?是二元運算,如果?和?滿足交換律、結合律和吸收律,則<S,?,?>構成格【定義11.3】對偶命題：設f是含有格中元素以與符號=,?,?,∨和∧的命題.令f*是將f中的?替換成?,?替換成?,∨替換成∧,∧替換成∨所得到的命題.稱f*為f的對偶命題【定義11.2】格的對偶原理：設f是含有格中元素以與符號=,?,?,∨和∧等的命題.若f對一切格為真,則f的對偶命題f*也對一切格為真.格的性質(zhì)：設<L,?>是格,則運算∨和∧適合交換律、結合律、冪等律和吸收律,即(1)∈L有a∨b=b∨a,a∧b=b∧a(2)∈L有(a∨b)∨c=a∨(b∨c),(a∧b)∧c=a∧(b∧c)(3)a∈L有a∨a=a,a∧a=a(4)∈L有a∨(a∧b)=a,a∧(a∨b)=a【定理11.1】格的序與運算性質(zhì)：設L是格,則∈L有a?ba∧b=aa∨b=b【定理11.3】格的保序性質(zhì)：設L是格,∈L，若a?b且c?d,則a∧c?b∧d,a∨c?b∨d【定理11.4】子格：設<L,∧,∨>是格,S是L的非空子集,若S關于L中的運算∧和∨仍構成格,則稱S是L的子格【定義11.4】分配格：設<L,∧,∨>是格,若∈L,有a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)則稱L為分配格.【定義11.5】分配格的判別：設L是格,則L是分配格當且僅當L不含有與鉆石格或五角格同構的子格【定理11.5】全下界：設L是格,若存在a∈L使得x∈L有a?x,則稱a為L的全下界；全上界：設L是格,若存在b∈L使得x∈L有x?b,則稱b為L的全上界

?！径x11.6】有界格：設L是格，若L存在全下界和全上界,則稱L為有界格，一般將有界格L記為<L,∧,∨,0,1>.【定義11.7】有界格的性質(zhì)：設<L,∧,∨,0,1>是有界格,則a∈L有a∧0=0∨0=∧1=a,a∨1=1補元：設<L,∧,∨,0,1>是有界格,a∈L,若存在b∈L使得a∧b=0和a∨b=1成立,則稱b是a的補元 【定義11.8】有界分配格的補元惟一性定理：設<L,∧,∨,0,1>是有界分配格.若L中元素a存在補元,則存在惟一的補元. 【定理11.6】有補格:設<L,∧,∨,0,1>是有界格,若L中所有元素都有補元存在,則稱L為有補格.【定義11.9】布爾格（布爾代數(shù)）：如果一個格是有補分配格,則稱它為布爾格或布爾代數(shù).布爾代數(shù)標記為<B,∧,∨,,0,1>,為求補運算.【定義11.10】布爾代數(shù)的代數(shù)系統(tǒng)定義：設<B,?,?>是代數(shù)系統(tǒng),?和?是二元運算.若?和?運算滿足：(1)交換律,即∈B有a?b=b?a,a?b=b?a(2)分配律,即∈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ì)：設<B,∧,∨,,0,1>是布爾代數(shù),則(1)a∈B,(a)=a.(2)∈B,(a∧b)=a∨b,(a∨b)=a∧b（德摩根律）【定理11.7】原子：設L是格,0∈L,a∈L若b∈L有0?b?ab=a,則稱a是L中的原子【定義11.12】有限布爾代數(shù)的表示定理：設B是有限布爾代數(shù),A是B的全體原子構成的集合,則B同構于A的冪集代數(shù)P(A). 【定理11.8】推論1：任何有限布爾代數(shù)的基數(shù)為2n,n∈N.推論2：任何等勢的有限布爾代數(shù)都是同構的圖論無序積：A{()|xAyB}無向圖G=<>,其中(1)V為頂點集，元素稱為頂點；(2)E為VV的多重集，其元素稱為無向邊，簡稱邊?！径x14.1】有向圖<>,只需注意E是VV的多重子集 【定義14.2】n階圖：頂點個數(shù)為n.零圖：邊的個數(shù)為0.n階零圖記為平凡圖：1階零圖N1空圖：標定圖與非標定圖：依據(jù)頂點和邊是否命名標識。有向圖的基圖：有向邊改為無向邊后的圖。頂點與邊的關聯(lián)關系(,) 關聯(lián)：與,關聯(lián) 關聯(lián)次數(shù)：0(不關聯(lián))，1()，2() 環(huán)：與同一頂點關聯(lián)次數(shù)為2的邊； 孤立點：不與任何邊關聯(lián)的頂點。頂點相鄰：兩個頂點之間有邊。邊相鄰：兩條邊有公共端點。平行邊：關聯(lián)的端點相同的兩條邊（有向圖中方向相同）。vV(G)(G為無向圖) v的鄰域： v的閉鄰域： v的關聯(lián)集：vV(D)(D為有向圖) v的后繼元集： v的先驅(qū)元集： v的鄰域： v的閉鄰域：多重圖：含平行邊的圖；簡單圖：即不含平行邊又不含環(huán)的圖。【定義14.3】度（度數(shù)）：設<>為無向圖,vV,d(v)——v的度數(shù),簡稱度設<>為有向圖,vV, 出度(v)：v作為邊的始點的次數(shù) 入度d(v)：v作為邊的終點的次數(shù)度（度數(shù)）d(v)：(v)+d(v)最大度(G){d(v)∈V(G)}最小度(G)={d(v)∈V(G)}最大出度+(D){(v)∈V(D)}最小出度+(D){(v)∈V(D)}最大入度(D){(v)∈V(D)}最小入度(D){(v)∈V(D)}最大度(D){d(v)∈V(D)}最小度(D){d(v)∈V(G)}奇頂點度：度為奇數(shù)的頂點偶度頂點：度為偶數(shù)的頂點 【定義14.4】握手定理：設<>為任意無向圖，{v12,…},,則 設<>為任意有向圖，{v12,…},,則 【定理14.1】【定理14.2】推論：任何圖(無向或有向)中，奇度頂點的個數(shù)是偶數(shù).度數(shù)列：{v1,v2,…,}為無向圖G的頂點集，稱d(v1),d(v2),…,d()為G的度數(shù)列{v1,v2,…,}為有向圖D的頂點集度數(shù)列：d(v1),d(v2),…,d()出度列：(v1),(v2),…,()入度列：d(v1),d(v2),…,d()可圖化的：非負整數(shù)列(d1,d2,…,)，若存在以{v12,…}為頂點集的n階無向圖G,使得d()，則稱d是可圖化的。特別的，若得到的圖是簡單圖，則稱d是可簡單圖化的。非負整數(shù)列(d1,d2,…,)是可圖化的當且僅當為偶數(shù).【定理14.3】設G為任意n階無向簡單圖，則(G)n-1.【定理14.4】圖的同構：設G1=<V11>,G2=<V22>為兩個無向圖(兩個有向圖)，若存在雙射函數(shù)f1V2，對于,V1,()E1當且僅當(f(),f())E2（<>E1當且僅當<f(),f()>E2)并且,()（<>）與(f(),f())（<f()()>）的重數(shù)相同，則稱G1與G2是同構的，記作G1G2.【定義14.5】n(n1)階無向完全圖：每個頂點與其余頂點均相鄰的無向簡單圖，記作.邊數(shù)n(n1)階有向完全圖：每對頂點之間均有兩條方向相反的有向邊的有向簡單圖.邊數(shù)n(n1)階競賽圖：基圖為的有向簡單圖.【定義14.6】邊數(shù)n階k正則圖：=的無向簡單圖?！径x14.7】邊數(shù)<>,G=<V> 子圖：V’V且E’E,則稱G’為G的子圖，記為GG，稱G為G的母圖; 生成子圖：若GG且V，則稱G為G的生成子圖； 真子圖：若VV或EE，稱G為G的真子圖； 導出子圖：V（VV且V）的導出子圖，記作G[V]； E（EE且E）的導出子圖，記作G[E]. 【定義14.8】補圖：設<>為n階無向簡單圖，以V為頂點集，以所有使G成為完全圖的添加邊組成的集合為邊集的圖，稱為G的補圖，記作.若G,則稱G是自補圖 【定義14.9】Gv：從G中將v與關聯(lián)的邊去掉GV：從G中刪除V中所有的頂點Ge：將e從G中去掉GE：刪除E中所有邊【定義14.10】通路與回路：給定圖<>（無向或有向的），G中頂點與邊的交替序列=v0e1v1e2…稱為從v0到的通路，其中1,是的端點.；若v0，為回路。中的邊數(shù)稱為通路的長度.簡單通路與簡單回路：所有邊各異。初級通路(路徑)與初級回路(圈)：中所有頂點各異（v0除外），所有邊也各異復雜通路與復雜回路：有邊重復出現(xiàn) 【定義14.11】在n階圖G中，若從頂點到（）存在通路，則從到存在長度小于或等于n1的通路.【定理14.5】推論：在n階圖G中，若從頂點到（）存在通路，則從到存在長度小于或等于n1的初級通路（路徑）在一個n階圖G中，若存在到自身的回路，則一定存在到自身長度小于或等于n的回路.【定理14.6】推論：在一個n階圖G中，若存在到自身的簡單回路，則一定存在長度小于或等于n的初級回路.頂點的連通性：<>為無向圖，若與之間有通路，則稱與是連通的，記為連通圖：若V，uv，則稱G是連通的；【定義14.12】連通分支：{V12,…}，稱G[V1],G[V2],…[]為連通分支，其個數(shù)稱為連通分支數(shù)，記為p(G)【定義14.13】短程線uv：，u與v之間長度最短的通路距離d()：短程線的長度 【定義14.14】d()0,u?v時d()=d()()d()()d()<>,VV 點割集：p(GV)>p(G)，且對任意VV均有p(GV)(G)，則V為點割集 割點：{v}為點割集，則v為割點 【定義14.15】<>,EE邊割集：p(GE)>p(G)且有極小性則E是邊割集割邊（橋）：{e}為邊割集e是割邊（橋）【定義14.16】G為連通非完全圖 點連通度(G)={|V為點割集}。規(guī)定()=n1;若G非連通，(G)=0 連通圖：若(G)k，則稱G為連通圖【定義14.17】設G為連通圖 邊連通度(G)={|E為邊割集}規(guī)定：若G非連通，則(G)=0r邊-連通圖：若(G)r，則稱G是r邊-連通圖 【定義14.18】,,之間的關系：(G)(G)(G)【定理14.7】<>為有向圖 可達：存在從到有通路 相互可達：且 【定義14.19】<>為有向圖 弱連通(連通)：基圖為無向連通圖 單向連通：V，或 強連通：V， 【定義14.21】有向圖的連通性判別法：(1)D強連通當且僅當D中存在經(jīng)過每個頂點至少一次的回路；【定理14.8】(2)D單向連通當且僅當D中存在經(jīng)過每個頂點至少一次的通路?！径ɡ?4.9】二部圖(二分圖)(偶圖)：設<>為一個無向圖，若能將V分成V1和V2(V1V2，V1V2=)，使得G中的每條邊的兩個端點都是一個屬于V1，另一個屬于V2，則稱G為二部圖(或稱二分圖、偶圖等)，稱V1和V2為互補頂點子集，常將二部圖G記為<V12>.完全二部圖：若G是簡單二部圖，V1中每個頂點均與V2中所有的頂點相鄰，則稱G為完全二部圖，記為，其中1|，2|.【定義14.22】二部圖的判別法：無向圖<>是二部圖當且僅當G中無奇圈?！径ɡ?4.10】關聯(lián)矩陣M(G)：無向圖<>，，，令為與的關聯(lián)次數(shù)，稱()nm為G的，記為M(G).【定義14.23】(4)平行邊的列相同關聯(lián)矩陣M(D)：有向圖<>，令則稱()nm為D的關聯(lián)矩陣，記為.【定義14.24】(4)平行邊對應的列相同鄰接矩陣：設D＝()是有向圖，V={v1,…}，構造矩陣[]如下：(1n)稱A為圖D的鄰接矩陣?！径x14.25】鄰接矩陣的含義：設A為有向圖D的鄰接矩陣，{v1,v2,…,}為頂點集，則A的l次冪（l1）中元素為D中到長度為l的通路數(shù)，其中為到自身長度為l的回路數(shù)，而為D中長度為l的通路總數(shù)，為D中長度為l的回路總數(shù).【定理14.11】可達矩陣P(D)：設<>為有向圖.{v1,v2,…,},令稱()nn為D的可達矩陣，記作P(D)，簡記為P.【定義14.26】歐拉通路：經(jīng)過圖（無向圖或有向圖）中每條邊一次且僅一次行遍所有頂點的通路.歐拉回路：經(jīng)過圖中每條邊一次且僅一次行遍所有頂點的回路.歐拉圖：具有歐拉回路的圖.半歐拉圖：具有歐拉通路而無歐拉回路的圖【定義15.1】平凡圖是歐拉圖.歐拉通路是簡單通路，歐拉回路是簡單回路無向歐拉圖的判別法：(1)無向圖G是歐拉圖當且僅當G連通且無奇度數(shù)頂點.【定理15.1】(2)無向圖G是半歐拉圖當且僅當G連通且恰有兩個奇度頂點.【定理15.2】有向歐拉圖的判別法：(1)有向圖D是歐拉圖當且僅當D是強連通的且每個頂點的入度都等于出度.【定理15.3】(2)有向圖D是半歐拉圖當且僅當D是單向連通的，且D中恰有兩個奇度頂點，其中一個的入度比出度大1，另一個的出度比入度大1，而其余頂點的入度都等于出度.【定理15.4】算法(求歐拉回路)：(1)任取v0V(G)，令P00.(2)設=v0e1v1e2…已經(jīng)行遍，按下面方法從E(G){e12,…}中選取1：(a)1與相關聯(lián)；(b)除非無別的邊可供行遍，否則1不應該為=G{e12,…}中的橋.(3)當(2)不能再進行時，算法停止.哈密頓通路：經(jīng)過圖（無向圖或有向圖）中所有頂點一次僅一次的通路.哈密頓回路：經(jīng)過圖中所有頂點一次僅一次的回路.哈密頓圖：具有哈密頓回路的圖.半哈密頓圖：具有哈密頓通路且無哈密頓回路的圖. 【定義15.2】平凡圖是哈密頓圖.哈密頓通路是初級通路，哈密頓回路是初級回路.哈密頓圖的必要條件：設無向圖<>是哈密頓圖，對于任意V1V且V1，均有p(GV1)1| 【定理15.6】推論：設無向圖<>是半哈密頓圖，對于任意的V1V且V1均有p(GV1)11哈密頓通路的充分條件：設G是n階無向簡單圖，若對于任意不相鄰的頂點，均有d()()n1則G中存在哈密頓通路.【定理15.7】推論（哈密頓圖的充分條件）：設G為n(n3)階無向簡單圖，若對于G中任意兩個不相鄰的頂點，均有d()()n則G中存在哈密頓回路，從而G為哈密頓圖帶權圖：設Ｇ＝()是圖，若G的