筆記離散數(shù)學

1、離散數(shù)學復習筆記 數(shù)理邏輯邏輯：以研究人的思維形式及思維規(guī)律為目的的一門學科數(shù)理邏輯：利用數(shù)學符號來協(xié)助推理的一門形式邏輯學命題：能表達判斷并具有確定真值的陳述句真值：每個命題都具有的一個值，要么為真，要么為假，不能隨著環(huán)境變化原子命題：不能再分解的命題復合命題：由原子命題符號及聯(lián)結(jié)詞組成的有意義的命題表達式否定非P 合取P而且Q  析取P可兼或Q 排斥析取P不可兼或Q 單條件若P則Q 雙條件P當且僅當Q命題公式：滿足特定條件的合法的命題表達式分量：命題公式中的原子命題翻譯：將自然語言轉(zhuǎn)化為數(shù)理邏輯語言真值表：對一個命題公式而言，將對于其分量的各種可能的真值指派匯聚成的表兩個命題等價

2、：對兩個命題公式A,B,若對于AB中的所有命題變元P1P2.對天安門的任一組真值指派A，B相同對應的行的真值相同，則稱A與B等價等價定律：交換律，結(jié)合律，分配律，摩根律，否定律，同一律重言式：永真式，無論對命題變元作何種真值指派，它都等價于T的命題公式永假式：無論對命題變元作何種真值指派，它都等價于F的命題公式用一個命題公式代替重言式中同一個分量，依然為重言式蘊含式：若A->B永真則稱A蘊含B，記做A=>B原命題等價于它的逆否命題三個性質(zhì)：傳遞性，A=>B A=>C A=>(BC)， A=>B C=>B AvC=>B有效結(jié)論：H1，H2、Hn，C

3、為一組命題公式，若H1H2.Hn=>C,稱C是一組條件下的有效結(jié)論三種方法：真值表法，直接證法，間接證法其他連接詞：條件否定，與非，或非規(guī)范命題表達式：只含非且或合取范氏：當且僅當具有A1A2.An形式，A1，A2.An都是命題變元或其否定組成的析取式析取范式：當且僅當具有A1vA2v.vAn形式，A1，A2.An都是命題變元或其否定組成的合取式一個命題公式的合取范氏或析取范氏并不是唯一的n個命題變元的合取式，稱作布爾合取或小項，其中每個變元與它的否定不能同時存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次 PQ P非Q一般n個命題變元共有2n個小項n個命題變元的析取式，稱作布爾析取或大項，其中每個變元

4、與它的否定不能同時存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次 PvQ Pv非Q主析取范式：對于給定的命題公式，如果有一個等價公式，它僅由小項的析取所組成，則稱該等價式為原式的主析取范式主合取范式：對于給定的命題公式，如果有一個等價公式，它僅由大項的合取所組成，則稱該等價式為原式的主合取范式集合論集合：滿足一定特征的對象的全體擴張原則：兩個集合相等，當且僅當他們有相同的元素抽象原則：任給一個集合U和一個性質(zhì)P，存在一個集合A，使得A的各個元素恰好是U的具有性質(zhì)P的那些成員集合表示：列舉法，特征法冪集：對給定的集合A，稱以A的全體子集為元素的集合為A的冪集集合的基數(shù)：|A|元素的個數(shù)無限集合：元素個數(shù)能與某

5、個真子集一一對應的集合序偶：有序的二元數(shù)組<x,y>笛卡爾積：稱A*B=<x,y>|x屬于A且y屬于B二元關(guān)系：以序偶作為元素的集合即關(guān)系xRy，關(guān)系前域指x，關(guān)系值域指y，關(guān)系域是前域和值域的并集。兩集合A與B的笛卡爾積的任一子集，稱為A到B的一個關(guān)系，若A=B，則稱該子集為A上的一個關(guān)系關(guān)系表示：集合表示法，關(guān)系矩陣法，關(guān)系圖表示法關(guān)系性質(zhì)：自反關(guān)系（x屬于X，<x,x>屬于R），反自反關(guān)系（x屬于X，<x,x>不屬于R）【存在既不反自反也不自反的關(guān)系】對稱性 x，y屬于X，且<x,y>屬于R，則<y,x>屬于R，反對

6、稱關(guān)系x屬于X，y屬于X，且<x,y>屬于R，<y,x>屬于R，則x=y【存在既對稱又反對稱的關(guān)系，存在既不對稱又不反對稱的關(guān)系】傳遞性 x,y,z屬于X，且<x,y><y,z>都屬于R，則<x,z>屬于R復合關(guān)系:<x,y>屬于R,<y,z>屬于S，則<x,z>屬于R復合S逆關(guān)系: <y,x>|<x,y>屬于R,x屬于X,y屬于Y閉包運算：通過往已知關(guān)系中添加序偶讓它達到某種要求的運算，叫閉包運算覆蓋：A為非空集合，S=s1,s2.sm其中Si屬于A，且S的并集為A，則S是

7、A的一個覆蓋劃分：若對一個覆蓋而言，S任意兩個子集的交集為空，則稱S是A的一個劃分注：兩劃分的交叉劃分也是原集合A的一個劃分交叉劃分是原兩劃分的加細等價關(guān)系：同時具備自反，對稱和傳遞三個性質(zhì)的關(guān)系即等價關(guān)系等價類：A上的等價關(guān)系R，A中的任意a，x屬于A，<x,a>屬于R，為元素a生成的R等價類商集：若R是A上的一個等價關(guān)系，則稱以A的所有等價類為元素的集合為A關(guān)于R的商集，為A/R定理：A上的一個等價關(guān)系R確定了A的一個劃分A/RA上的一個劃分也能確定A上的一個等價關(guān)系A(chǔ)上的兩個等價關(guān)系R1，R2，則成立 A/R1=A/R2等價于 R1=R2A上的等價關(guān)系與劃分是一一對應的相容關(guān)

8、系：給定集合A上的關(guān)系r，若r是自反的、對稱的、則稱r是相容關(guān)系最大相容類：設r是集合A上的相容關(guān)系，不能真包含在任何其他相容類中的相容類，稱作最大相容類在相容關(guān)系圖中，最大完全多邊形的頂點集合，就是最大相容類定理：設r是有限集合A上的相容關(guān)系，C是一個相容類，那么必存在一個最大相容類Cr，使得C屬于Cr在集合A上給定相容關(guān)系r，其最大相容類的集合稱作集合A的完全覆蓋，記為Cr(A)偏序關(guān)系：A上的關(guān)系R，同時滿足自反，反對稱，傳遞三個性質(zhì)，則稱R為偏序關(guān)系鏈與反鏈：一個元素構(gòu)成的子集，既是鏈，又是反鏈全序關(guān)系：在偏序集A中，如果對任意的x,y屬于A，x*y y*x必有一個成立，則稱A為全序集

9、合或線序集合，而稱關(guān)系為全序關(guān)系或線序關(guān)系極大元，極小元必然存在，極大元，極小元可以不唯一。若B有最大元，則它們必然唯一良序關(guān)系：偏序集A，若B屬于A，B中總有最小元，則稱A是良序集良序集一定是全序集，有限元素的全序集一定是良序集函數(shù)性質(zhì)：入射（單射） x1和x2不等， 函數(shù)值不等滿射：對任意y屬于Y，存在x屬于X，使得y為x的函數(shù)雙射：既是入射又是滿射的函數(shù)逆函數(shù)：若f x->y 的雙射,則 逆函數(shù)是y->x 的雙射復合函數(shù)： g*f <x,y>屬于f <y,z>屬于g g在f的左可復合函數(shù)令g*f 是個復合函數(shù) 若g和f是滿射，則g*f是滿射 若g和f是

10、入射，則g*f是入射，都是雙射，g*f是雙射圖論圖的定義：平面上由一些點和連接兩點之間的連線構(gòu)成的圖形有向圖-每條邊都有方向的圖，無向圖-每條邊都沒有方向的圖，混合圖-既有有向邊又有無向邊的圖點邊關(guān)聯(lián)，點點（邊邊）鄰接（相鄰） 結(jié)點v的度-v關(guān)聯(lián)的邊數(shù)（環(huán)在算度數(shù)時，規(guī)定按兩次計），所有結(jié)點的度數(shù)和=邊數(shù)x2空圖：沒有邊的圖，平凡圖：一個點的空圖，有向圖的出入度，奇偶點：度為奇偶數(shù)的點圖的基本定理1、無向圖的度為邊數(shù)的兩倍2、圖的奇點個數(shù)一定為偶數(shù)，若不包含重邊，也不含環(huán)，則稱G為簡單圖完全圖：任兩結(jié)點之間有且僅有一條邊相連的n個結(jié)點的圖有向完全圖：完全圖每條邊上任意添加一個方向同構(gòu)：兩個圖若

11、存在一個映射 ，點到點，邊和邊也映射，則兩個圖同構(gòu)必要條件：結(jié)點數(shù)目相同，邊數(shù)相等，度數(shù)相同的結(jié)點數(shù)目相等，與同度點相鄰的點的度數(shù)應對應相同補圖：兩個圖點和邊相互補充子圖：點和邊都屬于另一個圖的子集，真子圖：點或邊不全包含路與回路路的長度：路經(jīng)過的邊的次數(shù)， 路，跡，通路，回路，閉跡，圈定理：n個結(jié)點的圖當中存在長為l的路，那么G中必存在長度小于等于n-1的路兩點連通：兩點之間有路相連，連通是等價關(guān)系，確定V的一個劃分，誘導子圖為G的連通分支刪除某點和邊不連通，但刪除這些點或邊的子集依然連通，也就是必須要刪除的點和邊一個點的點割集叫做割點，一條邊的邊割集叫做割邊，也叫做橋，點連通度是最小的點割

12、集數(shù)目，邊連通度是最小的邊割集數(shù)目，完全圖的連通程度最強，都為N-1歐拉圖1、歐拉回路：經(jīng)過G中每條邊一次且僅一次的回路2、歐拉圖：含有歐拉回路的圖3、歐拉圖充要條件：G無孤立點，那么G是歐拉圖【G連通且無奇點】漢密爾頓圖1、漢密爾頓圈：經(jīng)過圖G中每個點一次且僅一次的圈2、漢密爾頓圖：含有漢密爾頓圈的圖，至今無充分必要條件3、閉包：簡單圖G是漢密爾頓圖等價于它的閉包是也是漢密爾頓圖樹1、樹：連通的無圈回路的無向圖2、森林：無圈圖3、生成樹：作為圖G的支撐子圖的一棵樹，任一連通圖都至少有一棵生成樹4、帶權(quán)圖：每條邊上都帶有一個給定權(quán)值的圖5、最小生成樹：邊權(quán)和最小的生成樹，不唯一6、有向樹：在不

13、考慮邊上方向時為一棵樹的有向圖7、根樹：一棵恰有一個結(jié)點的入度為0，其余結(jié)點的入度為1的有向樹8、有序樹：結(jié)點間擁有順序的根樹，任意一棵有序樹都可以改寫成一棵對應的二叉樹9、m叉樹，完全m叉樹：同二叉樹10、通路長度：根樹中，從根結(jié)點到某個結(jié)點的通路經(jīng)過的邊數(shù)稱為此結(jié)點的通路長度11、帶權(quán)二叉樹：每片樹葉i都帶權(quán)值wi的二叉樹12、最優(yōu)二叉樹必是完全二叉樹代數(shù)系統(tǒng)1、n元運算符：A，B為給定的集合，An->B為A上的一個n元運算2、代數(shù)系統(tǒng)：非空集合A，以及定義在其上的若干運算，就稱為一個代數(shù)系統(tǒng)，如果一個運算在A上滿足封閉性，針對A中的兩個元素，運算結(jié)果也屬于A3、幺元：e*a=a e

14、左幺元 a*e=a 右幺元 如果A中同時存在左幺元和右幺元，則必存在幺元4、零元：q*a=q a*q=q 左右零元 同時存在左零元和右零元，則存在零元5、逆元：a*b=e b為a的右逆元，b*a=e b為a的左逆元 a*b=b*a=e b為a的逆元半群1、廣群：代數(shù)系統(tǒng)<A,*>稱為廣群，若*在A上滿足封閉性2、半群：<S,*>為半群，若滿足封閉性和可結(jié)合性3、子半群：<S,*>是半群，<B,*>是半群，B屬于S，稱<B,*>是<S,*>的子半群4、獨異點：含有幺元的半群稱為獨異點，設<s,*>是一個獨異點，則

15、在它的乘法表中任何兩行或任何兩列都是不相同的，設<S,*>是一個獨異點，在S中任取兩個元素a和b，如果a和b都有逆元，那么a*b也必有逆元群與子群1、群：設<G,*>是一個代數(shù)系統(tǒng)，*是G上的二元運算，如果*在G上是封閉的并且是可結(jié)合性的，存在幺元，每個元素的逆元也存在于G中，稱代數(shù)系統(tǒng)為一個群2、有限群：設<G，*>是一個群，如果G是一個有限集，則稱<G,*>是一個有限集，如果G是一個無限集，則稱<G,*>是一個無限群3、子群：<G,*>是一個群，B是G的非空子集，<B,*>也作成一個群，稱<B，*&g

16、t;是<G,*>的子群4、群的性質(zhì)：每個元素的逆元唯一若|G|>1，則G中無零元群中滿足消去律子群與原群具有相同的幺元5、非空子集成為子群的兩個充分條件-設群<G,*>,B是G的一個非空子集，滿足B是有限集，*在B中滿足封閉性，則<B,*>必為<G,*>的子群-設<G,*>是一個群，S是G的一個非空子集，如果對S中任何元素a,b，都有a*b逆屬于S，那么<S,*>必為<G,*>的子群阿貝爾群1、定義：<G,*>是一個群，如果群中的運算*還滿足交換律，即對任何兩個元素x,y屬于G，都有x*y=y

17、*x,則稱為一個阿貝爾群2、定理：<G,*>是群，那么它是交換群的充要條件是，任意a,b (a*b)*(a*b)=(a*a)*(b*b)循環(huán)群1、定義：<G,*>是一個群，如果群G中存在一個元素a，使得G中任何元素都可以表示成元素a的整數(shù)冪，則稱<G,*>是一個循環(huán)群，元素a稱為循環(huán)群中的一個生成元2、性質(zhì)：任何循環(huán)群必為阿貝爾群，一般說來，阿貝爾群未必是循環(huán)群3、群的元素的階：設<G,*>是一個群，a是群G中任一個元素，如果有正整數(shù)r存在使得ar=e成立，對任何小于r的正整數(shù)m，am=e皆不成立，則稱a是一個有限階元素，并稱該元素的階

18、位r  北航離散復習筆記   第二章 謂詞邏輯1、項：用于表達個體的符號串，相當于漢語中的名詞2、公式：用于表達命題的符號串，相當于漢語中的句子3、使用符號：個體變元【變元】，個體常元【常元】，函數(shù)符號，謂詞符號，量詞符號，聯(lián)結(jié)詞符號，圓括號和逗號4、若公式B是公式A的子串，則稱B為A的子公式，每個原子公式僅有的子公式是它自己5、不出現(xiàn)變元的項稱為基項，也稱為閉項，沒有自由變元的公式稱為語句，也稱為閉公式。沒有約束變元的公式稱為開公式6、論域也稱為個體域7、永真式：A在每個解釋中為真，永假式類似(矛盾式，不可滿足式)8、重言式：用謂詞邏輯公式分

19、別同時替換命題邏輯公式A中的不同命題變元得到的謂詞邏輯公式。命題邏輯永真式的替換實例稱為重言式9、重言式一定是永真式，永真式未必是重言式，永真式都是可滿足式，可滿足式未必是永真式第三章 公理系統(tǒng)1、定義：指從事先給定的公里出發(fā)，根據(jù)推理規(guī)則推導出一系列定理，由此而形成的演繹系統(tǒng)2、組成：符號集，公式集，公理集，推理規(guī)則集，定理集3、性質(zhì)：可靠性【只要公設都真，每個定理就真】，完備性【公設集的每個邏輯推論都是公理系統(tǒng)的定理】，協(xié)調(diào)性，獨立性第四章 歸結(jié)法原理1、文字的有窮集合稱為子句，不包含任何文字的子句稱為空子句2、如果真值賦值v滿足子句集S中的每個子句，則稱v滿足S，如果至少有一個真值賦值滿

20、足子句集S，則稱S是可滿足的，否則S是不可滿足的3、如果一個文字恰為另一個文字的否定，則稱它們?yōu)橄喾吹奈淖?。L1，L2是相反的文字，C1，C2是子句，稱C11-L1 U  C2-L2為C1和C2的歸結(jié)子句4、若C是C1，C2的歸結(jié)子句，則C是C1，C2的邏輯推論5、子句集S是不可滿足的當且僅當存在S的反駁6、前束范式形式Q1v1.QvnB,Q1v1.Qnvn為該前束范式的前束詞，稱B為它的母式7、不出現(xiàn)存在量詞存在的前束范式稱為無 存在 前束范式8、若B是前束范式A的無存在 前束范式，則A不可滿足當且僅當B不可滿足9、不出現(xiàn)變元的文字稱為基文字，基文字的有窮集合稱為基子句10、如果解

21、釋I滿足子句集S中的每個子句，則稱I滿足S，如果至少有一個解釋滿足子句集S，則稱S是可滿足的，否則S為不可滿足的第五章 集合的基本概念和運算1、集合：人們直觀上或思想上能夠明確區(qū)分的一些對象所構(gòu)成的一個整體，通過枚舉法和抽象法展示2、基數(shù)：有窮集A的元素個數(shù)稱為A的基數(shù)3、如果集合A中的每個元素都是集合，則稱A為集合的聚合，或者集合族4、集合歸納定義的三個組成部分：基礎(chǔ)語句【直接規(guī)定某些對象是該集合的元素】，歸納語句【規(guī)定由已知元素得到新元素的辦法】，權(quán)限語句【限定集合的范圍，保證定義集合的唯一性】5、字母表：符號的有窮非空集合稱為字母表，也稱為符號集6、將兩個對象x，y按x前y后的順序構(gòu)成的

22、序列稱為有序偶，分別稱x,y為有序偶的第一元，第二元7、笛卡爾乘積兩個集合的乘積，A中的元素為第一元素，B中的元素為第二元素，構(gòu)成有序偶第六章 關(guān)系1、關(guān)系：任何有序偶的集合稱為二元關(guān)系，簡稱關(guān)系2、定義域：關(guān)系R中所有有序偶的第一元組成的集合3、值域：關(guān)系R中所有有序偶的第二元組成的集合4、關(guān)系矩陣：從X到Y(jié)的關(guān)系，m*n的關(guān)系5、R是自反的：R的關(guān)系矩陣的主對角線全為1，R的關(guān)系圖中每個頂點上都有自環(huán)【對應反自反】6、R是對稱的：R的關(guān)系矩陣是對稱矩陣，R的關(guān)系圖中沒有單向邊（或者無弧或者兩條相反方向的?。緦磳ΨQ】7、R是傳遞的：R的關(guān)系圖中從頂點x到頂點y有長度大于1的通路，必有從

23、x到y(tǒng)的有向邊8、關(guān)系復合：R是從x到y(tǒng)的關(guān)系，S是從y到z的關(guān)系，稱x到z的一個關(guān)系為R,S的復合關(guān)系9、逆關(guān)系：將R中的每個有序偶的第一元與第二元對調(diào)就得到逆關(guān)系，關(guān)系矩陣轉(zhuǎn)置，關(guān)系圖中每條有向邊反向10、閉包：R的自反閉包是包含R的最小自反的關(guān)系。B是A的閉包滿足B是自反、對稱、傳遞的，A屬于B，對于集合X上的任何自反關(guān)系C，只要A屬于C，則B屬于C11、若R是非空集合P上自反的、反對稱的、傳遞的關(guān)系，則稱R為偏序關(guān)系或偏序12、若R是非空集合P上反自反的、傳遞的關(guān)系，則稱R為嚴格偏序關(guān)系或嚴格偏序13、偏序集中x是y的緊鄰前元，則稱y遮蓋x14、<A,>是偏序集，B屬于A，

24、b屬于B，對于每個x屬于B，都有x<=b, b為B的最大元【最小元b<=x】，b<x稱b為B的極大元【極小元x<b】15、<A,>是偏序集，B屬于A，b屬于A，對于每個x屬于B，都有x<=b, b為B的上界【下界b<=x】，B的上界集合的最小元為B的最小上界，上確界，B的下界集合的最大元為B的最大下界，下確界；最大元一定是上確界， 最小元一定是下確界。每個集合最多只有一個上確界16、良序集：<P,<=>偏序,P的每個非空子集都有最小元，稱<=為良序，<P,<=>為良序集；良序集必為全序集，全序集未必是良序

25、集，良序的逆關(guān)系未必是良序17、若A是非空集合S的非空子集的聚合，并且UA=S，則稱A為S的覆蓋18、A為S的覆蓋，A中任意兩不同元素B,C，B交C為空，則A為S的劃分，A的元素為劃分塊，A的元素個數(shù)為A的秩【每個塊都不是空集，S的每個元素都在一個塊中，任何兩不同塊都沒有公共元素】19、等價關(guān)系：R是非空集合X上自反的、對稱的、傳遞的關(guān)系20、等價類：一個等價類元素之間互相等價，有不同的元素代表的等價類或者相等，或者不相交。所有等價類的并集是集合X，等價類的聚合確定了集合X的一個劃分21、商集：R等價類的集合是X的劃分，并稱它為X模R的商集22、每個等價關(guān)系確定一個劃分，每個劃分確定一個等價關(guān)

26、系第七章 函數(shù)1、設f是從集合X到Y(jié)的關(guān)系，若對每個x屬于X存在唯一y屬于Y，<x,y>屬于f，則稱f為從X到Y(jié)的函數(shù)，記為X到Y(jié)2、f是從X到Y(jié)的函數(shù)，A屬于X，從A到Y(jié)的函數(shù)稱f受限制于A3、對于每個x存在唯一的y屬于Y，使得<x,y>屬于f，稱f為從X到Y(jié)的偏函數(shù)4、滿射：對于每個y屬于Y，都存在x屬于X，使得f(x)=y，稱f為滿射5、單射：對于任意x，y屬于X，只要f(x)=f(y)，就有x=y，只有x不等y，f(x)不等f(y)6、雙射：既是單射，也是滿射7、f是從X到Y(jié)的函數(shù)，g是從Y到Z的函數(shù)，f和g【滿射->滿射；單射->單射；雙射->

27、;雙射】8、常值函數(shù)：設函數(shù)f:X->Y,如果對于所有x屬于X，存在某一個y屬于Y，使得f(x)=y稱f為常值函數(shù)9、設f：X->Y是雙射函數(shù)，則其逆關(guān)系是雙射函數(shù)Y->X10、雙射集合構(gòu)成群：封閉性；結(jié)合律；有單位元；有逆元第八章 自然數(shù)1、集合A是無窮集當且僅當A與它的某些真子集等勢2、集合A是有窮集當且僅當A與它的任何真子集都不等勢3、與某個自然數(shù)等勢的集合稱為有窮集，否則稱為無窮集4、任何有窮集只與一個自然數(shù)等勢5、任何與自然數(shù)集合等勢的集合稱為可數(shù)無窮集6、有窮集和可數(shù)無窮集統(tǒng)稱為可數(shù)集，不是可數(shù)集的無窮集稱為不可數(shù)集7、任何無窮集必有可數(shù)無窮子集8、可數(shù)集合刪去或

28、者合并一個有窮集合仍然是可數(shù)集合9、兩個可數(shù)集合的并，笛卡爾積仍然是可數(shù)集第九章 圖的基本概念1、帶權(quán)圖：為每條弧或邊指定了權(quán)的圖稱為帶權(quán)圖2、關(guān)聯(lián)、相鄰、鄰接，自環(huán)，平行弧，平行邊，多重弧圖，多重邊圖，簡單圖，引出弧，引入弧，引出次數(shù)，引入次數(shù)，孤立點（次數(shù)0），懸掛點（次數(shù)1），懸掛邊，零圖（每個頂點都是孤立點），平凡圖3、次數(shù)為奇數(shù)的頂點稱為奇頂點，次數(shù)為偶數(shù)的頂點為偶頂點，在任何圖中奇頂點的個數(shù)必為偶數(shù)4、正則圖：所有頂點次數(shù)都是同一個數(shù)；完全圖：任何兩個頂點之間都有一條邊的簡單無向圖；有向完全圖：任何兩頂點恰有一條弧的簡單有向圖5、同構(gòu)圖：同樣的頂點數(shù)，同樣的邊數(shù)，對于任意自然數(shù)K，

29、次數(shù)為k的頂點數(shù)一樣多，有同樣多的環(huán)6、子圖/部分圖，真子圖，補圖，通路，長度，簡單通路，基本通路，回路，簡單回路，基本回路，無回路圖，半通路，強連通，單向連通，弱連通，不連通7、若從頂點u可以到達頂點v，則存在從u到v的基本通路8、有向圖D是單向連通的當且僅當D有完備通路9、鏈，簡單鏈，基本鏈，閉合鏈，圈，割點（去掉不連通），割邊（去掉不連通），強連通分圖，弱連通分圖，壓縮（把每個強連通分圖作為一個點）第十章 樹1、定義：連通且無圈的無向圖為樹，非平凡樹中至少有兩片樹葉2、稱為頂點或弧指定了次序的根數(shù)是有序樹3、每個頂點的引出次數(shù)都等于m或0的根數(shù)稱為完全m元樹4、在所有帶權(quán)為p1.pn的二

30、元樹中，權(quán)最小的帶權(quán)二元樹稱為最優(yōu)二元樹5、生成樹，破圈法，最小生成樹，割集（G中分離出E后成為兩個連通分支，E是最小要分離的量）；基本割集（只包含一個樹枝的割集）6、每個圈與任何生成樹的補至少有一條公共邊，每個圈都包含弦；每個割集與任何生成樹至少有一條公共邊；任何圈和任何割集都有偶數(shù)條公共邊第十四章 二分圖1、V分成兩個非空子集X,Y，并且使得同一子集中的任何兩個頂點都互不臨界，G為二分圖2、非平凡無向圖G是二分圖當且僅當G的每個圈的長度都是偶數(shù)3、M屬于E，若M中任何兩條邊都不相鄰，則稱M為G的匹配，邊數(shù)最多的匹配稱為最大匹配4、M是二分圖G的匹配，P是G中的基本鏈，P中任何相鄰的兩條邊恰有一條屬于M，則稱P為關(guān)于M的交錯鏈5、與M中的邊關(guān)聯(lián)的頂點為M的飽和頂點，稱不與M中任何邊關(guān)聯(lián)的頂點為M的非飽和頂點；兩個端點都是匹配M的非飽和頂點的交錯鏈稱為關(guān)于M的可擴充鏈；最大匹配M當且僅當G中不存在關(guān)于M的可擴充鏈第十五章 平面圖1、若能將無向圖G畫在平面上，而使邊不在非頂點處相交，