離散數(shù)學(xué)高分筆記

高分筆記（離散數(shù)學(xué)）主要介紹集合論的基本概念和結(jié)論，集合的運(yùn)算及其性質(zhì)，以及利用運(yùn)算性質(zhì)進(jìn)行集合表達(dá)式的化簡(jiǎn)和集合恒等式的證明等內(nèi)容．考試經(jīng)常涉及到的題型有以下4個(gè)：集合與集合之間的包含、元素與集合之間的屬于關(guān)系冪集的計(jì)算集合之間的運(yùn)算利用集合運(yùn)算性質(zhì)證明集合恒等式大家對(duì)于集合與集合、元素和集合之間的關(guān)系往往容易混淆，那讓我們來(lái)仔細(xì)分析下二者的區(qū)別。1.集合與集合之間存在一種包含關(guān)系，用?、?、?、?等符號(hào)表示①對(duì)任意兩個(gè)集合A和B，若B中的每個(gè)元素都是A中的元素，則稱(chēng)B為A的子集，用B?A（B為A的子集）或A?B（B被A包含）表示．若B不是A的子集，即B?A不成立時(shí)，則稱(chēng)A不包含B，記作BA．A也是自己的子集．③對(duì)任意兩個(gè)集合A和B，若B?A且B≠A，則稱(chēng)B為A的真子集，用B?A或A?B表示．2.元素與集合之間存在一種從屬關(guān)系，用∈、等符號(hào)表示當(dāng)a是集合A中的元素，則稱(chēng)a屬于A，記作a∈A；若a不是集合A中的元素，則稱(chēng)a不屬于A，記作aA．那么在考試中是怎樣考的呢？我們來(lái)看2道歷年真題：[例1]若集合A＝{a，{a}，{1，2}}，則下列表述正確的是(C)．（2008年9月試卷第1題）A．{a，{a}}∈AB．{2}?AC．{a}?AD．∈A[分析]選項(xiàng)A，錯(cuò)了．因?yàn)閧a，{a}}是集合A＝{a，{a}，{1，2}}的子集，集合之間應(yīng)該用包含關(guān)系?表示，即{a，{a}}?A．選項(xiàng)B，錯(cuò)了．因?yàn)?不是集合A＝{a，{a}，{1，2}}的元素，當(dāng)然{2}也不是A的子集．正確的表示方法是{2}A．選項(xiàng)C，正確．因?yàn)閍是集合A＝{a，{a}，{1，2}}的元素，所以取元素a組成一個(gè)集合{a}就是A的子集，用包含關(guān)系?表示是正確的．注意：{a}也是集合A的元素，若屬于關(guān)系∈也是正確的．選項(xiàng)D，錯(cuò)了．因?yàn)榭占侨我庖粋€(gè)集合的子集，所以也是A的子集，集合之間應(yīng)該用包含關(guān)系?表示，即?A．[例2]若集合A={a，b}，B={a，b，{a，b}}，則（）．（2009年7月試卷第1題）A．A?B，且A∈BB．A∈B，但ABC．A?B，但ABD．AB，且AB[答案]A[分析]選項(xiàng)A，正確．因?yàn)榧螦={a，b}既是取集合B={a，b，{a，b}}中元素a，b組成的一個(gè)集合，是B的一個(gè)真子集，用A?B表示是正確的；但它也是B的元素，所以用A∈B表示也是正確的．選項(xiàng)B，錯(cuò)了．選項(xiàng)中第一個(gè)式子A∈B是正確的，但第二個(gè)式子AB是錯(cuò)的．因?yàn)榧螦={a，b}是取集合B={a，b，{a，b}}中元素a，b組成的一個(gè)集合，是B的一個(gè)真子集，應(yīng)該用A?B表示，而不是用AB表示．選項(xiàng)C，錯(cuò)了．選項(xiàng)中第一個(gè)式子A?B是正確的，但第二個(gè)式子AB是錯(cuò)的．因?yàn)榧螦={a，b}是集合B={a，b，{a，b}}中元素，應(yīng)該用A∈B表示，而不是用AB表示．選項(xiàng)D，錯(cuò)了．因?yàn)榧螦={a，b}是取集合B={a，b，{a，b}}中元素a，b組成的一個(gè)集合，是B的一個(gè)真子集，應(yīng)該用A?B表示，而不是用AB表示．又因?yàn)榧螦={a，b}是集合B={a，b，{a，b}}中元素，應(yīng)該用A∈B表示，而不是用AB表示．冪集的計(jì)算比較簡(jiǎn)單，先來(lái)看什么是冪集呢？1由集合A的所有子集組成的集合，稱(chēng)為APA的冪集，記作()或2A．若集合An是由個(gè)元素所組成的集合，則A的冪集由2n元素組成．當(dāng)=3時(shí)，的冪集由23=8個(gè)元素組成．舉個(gè)例子來(lái)說(shuō)，大家就會(huì)覺(jué)得比較簡(jiǎn)單了．設(shè)集合A={0,1,2}，則A的全部子集由以下子集組成：nA0元子集（即空集）：；1元子集：{0}，{1}，{2}；2元子集：{0,1}，{0,2}，{1,2}；A3元子集（即集合）：{0,1,2}．因此，計(jì)算集合A的冪集時(shí)，首先要按照上述方法寫(xiě)出集合A的全部子集，然后檢驗(yàn)寫(xiě)出的子集個(gè)數(shù)是否等于2n個(gè)，其中是集合A的元素個(gè)數(shù)n那么在考試中是怎樣考的呢？我們來(lái)看2道歷年真題：A[例1]若集合的元素個(gè)數(shù)為10，則其冪集的元素個(gè)數(shù)為()．（2008年7月試卷第3題）A．1024B．10C．100D．1[答案]：A[分析]由集合A的所有子集組成的集合，稱(chēng)為A的冪集，記作P(A)或2A.AnAAAn若集合是由個(gè)元素所組成的集合，則的冪集由2元素組成．本題集合有10個(gè)元素，因此的冪集由210=1024個(gè)元素組成．所以選項(xiàng)A是正確，其他選項(xiàng)都不對(duì)．【易錯(cuò)點(diǎn)】當(dāng)n比較大時(shí)，有些同學(xué)可能不會(huì)計(jì)算2的n次冪，即把2計(jì)算錯(cuò)了．【提示】10若集合A有n個(gè)元集，則其冪集P(A)有2n個(gè)元素．Aab[例2]設(shè)集合＝{，}，那么集合A的冪集是_________．（2008年7月試卷第6題）abab[答案]：{，{}，{}，{,}}[分析]按照冪集定義，集合＝{，}的所有子集就是A的冪集．AabA的全部子集由以下子集組成：0元子集（即空集）：；ab1元子集：{}，{}；Aab2元子集（即集合）：{，}．Aabab所以，集合的冪集是：{，{}，{}，{,}}集合之間的運(yùn)算有并（∪）、交（∩）、差（-）、補(bǔ)（~）和對(duì)稱(chēng)差（）等五種運(yùn)算，在做集合運(yùn)算的題目時(shí)，一定要按照它們的定義進(jìn)行計(jì)算。(1)集合A和B的并集A∪B＝{x|x∈AxB或∈}特點(diǎn)：所有屬于A或?qū)儆贐的元素組成的集合．見(jiàn)圖1(2)集合A和B的交集A∩B＝{x|x∈AxB且∈}特點(diǎn)：既屬于A又屬于B的所有元素組成的集合．見(jiàn)圖2(3)集合A和B的差集-＝{|∈ABxxA且xB}特點(diǎn)：由屬于A，而不屬于B的所有元素組成的集合．見(jiàn)圖3(4)集合A的補(bǔ)集AxxE且xA}~={|∈特點(diǎn)：由屬于全集E但不屬于集合A的元素組成的集合．見(jiàn)圖4補(bǔ)集總相對(duì)于一個(gè)全集而言，可以看作是全集E與集合A的差集．2(5)集合A與B的對(duì)稱(chēng)差A(yù)BBA＝(-)∪(-)ABAB＝(A∪B)-(A∩B)或特點(diǎn)：由分別屬于集合A與B的元素但不屬于它們公共元素組成的集合．見(jiàn)圖5A，B合成集合A×B叫做笛卡兒積，規(guī)定xyxA且y∈B}(6)把集合AB×＝{<,>|∈xy注意：由于有序?qū)?lt;,>中x,y的位置是確定的，因此A×B的記法也是確定的，不能寫(xiě)B(tài)×A.．成笛卡兒積的運(yùn)算一般不能交換.．雖然笛卡兒積的內(nèi)容是第2章2.1.1目的內(nèi)容，是二元關(guān)系的預(yù)備知但我們認(rèn)為把它作為集合的一種運(yùn)算考慮更好些。識(shí)，那么在考試中是怎樣考的呢？我們來(lái)看2道歷年真題：AB[例1]設(shè)={{1},{2},1,2}，={1,2,{1,2}}，試計(jì)算（2008年9月試卷第[分析]17即題）AB（1）-；AB（2）∩；（3）A×BA與B的差集A而不屬于B的所有元素組成的集合．（1）求集合A-B，就是求屬于A-B={{1},{2},1,2}-{1,2,{1,2}}={{1},{2}}．A與B的交集A∩B，就是求由A∩B={{1},{2},1,2}∩{1,2,{1,2}}={1,2}．A和B的公共元素組成的集合（2）求集合集合．即A×B，就是求一個(gè)元素是（3）求集合A與B的笛卡兒積有序?qū)Φ募?，而這些有序?qū)Φ牡谝粋€(gè)元素取自集合A，第二個(gè)元素取自集合A×B={{1},{2},1,2}×{1,2,{1,2}}={<{1},1>，<{1},2>，<{1},{1,2}>，<{2},1>，B．即<{2},2>，<{2},{1,2}>，<1,1>，<1,2>，<1,{1,2}>，<2,1>，<2,2>，<2,{1,2}>}【易錯(cuò)點(diǎn)】我們對(duì)集合中有的元素用集合形式表示的情形容易混淆，既不把{1},{2}看作集合元素，不把{1,2}看作集合B的元素，或者把{1}，{2}，{1,2}看作是相同的?！咎崾尽緼的笛卡兒積A×B是由集合A的每一個(gè)元素與集合B的各個(gè)元素合成有序?qū)?lt;x,y>（其中x意∈A且y∈B）作為元素的集合．所謂有序?qū)褪侵敢粋€(gè)有順序的數(shù)組，如<x,y>，x,y的位置是確定的，不能隨放置。AabBab[例2]設(shè)={{,},1,2}，={,,{1},1}，試計(jì)算（2009年1月試卷第17題）AB（1）-；AB（2）∪；ABAB（3）（∪）-（∩）B的所有元素組成的集合．即A和B的所有元素組成的集合．即[分析]（1）求集合A與B的差集abA-B，就是求ab-={{,},1,2}-{,,{1},1}={{,},2}．A而不屬于屬于ABabA與B的并集A∪BabA∪B，就是求ab={{,},1,2}∪{,,{1},1}={{,},1,2,,,{1}}．（2）求集合由集合ababA∪Babab={{,},1,2,,,{1}}ab（3）因?yàn)锳Bab∩={{,},1,2}∩{,,{1},1}={1}ABABabababab∪）-（∩）={{,},1,2,,,{1}}-{1}={{,},2,,,{1}}．所以（如同實(shí)數(shù)運(yùn)算有交換律、面以恒等式的形式給出集合運(yùn)算滿足的主要運(yùn)算律結(jié)合律和分配率等。集合的運(yùn)算也有許多運(yùn)算律。,其中下A,B,C為任意集合這些恒等式是證明其它集合恒等式、化簡(jiǎn)集合表達(dá)式的主要依據(jù),正確運(yùn)用這些恒等式是做好集合證明或化簡(jiǎn)題的關(guān)鍵．因此,大家要通過(guò)練習(xí)逐步掌握這些集合運(yùn)算性質(zhì).,E為全集。3A∪B=B∪AA∩B=B∩A1、交換律2、結(jié)合律3、分配律4、同一律5、冪等律6、零律(A∪B)∪C=A∪(B∪C)(A∩B)∩C=A∩(B∩C)A∪(B∩C)=(A∪B)∩(A∪C)A∩(B∪C)=(A∩B)∪(A∩C)A∪=AA∩E=AA∪A=AA∩A=AA∪E=EA∩=A∪~A=EA∩~A=7、補(bǔ)余律8、吸收率A∪(A∩B)=AA∩(A∪B)=AA-(B∪C)=(A-B)∩(A-C)A-(B∩C)=(A-B)∪(A-C)～(B∪C)=~B∩~C9、摩根律～(B∩C)=~B∪~C~=E~E=10、雙補(bǔ)律~（~A）=A[例1]試證明集合等式8題）A∪(B∩C)=(A∪B)∩(A∪C)．（2008年9月試卷第19題、2009年10月試卷第[證明過(guò)程]若對(duì)A∪(B∩C)中的任一元素則有x∈A或x∈B∩C，x，即x∈A∪(B∩C),即x∈A或x∈B且x∈A或x∈C,也即x∈A∪B且x∈A∪C，得x∈(A∪B)∩(A∪C)．所以A∪(B∩C)?(A∪B)∩(A∪C)．①反之，若對(duì)(A∪B)∩(A∪C)中的任一元素x，即x∈(A∪B)∩(A∪C),則有x∈A∪B且x∈A∪C,即x∈A或x∈B且x∈A或x∈C,也即x∈A或x∈B∩C，得x∈A∪(B∩C)．所以(A∪B)∩(A∪C)?A∪(B∩C)．②由①和②得A∪(B∩C)=(A∪B)∩(A∪C)．【提示】集合恒等式的證明方法通常有二：(1)要證明A=B，只需要證明A?B，又A?B；(2)通過(guò)運(yùn)算律進(jìn)行等式推導(dǎo).[例2]設(shè)A，B是任意集合，試證明：若A×A=B×B，則A=B．（2010年1月試卷第18題）A×A的元素，即<x,x>∈A×A．[證明過(guò)程]設(shè)對(duì)A中的任一元素x，即x∈A，那么有序?qū)?lt;x,x>∈B×B，則有<x,x>是笛卡兒積因?yàn)锳×A=B×B，故有所以A?B．①x∈B．又設(shè)對(duì)B中的任一元素x，即x∈B，那么有序?qū)?lt;x,x>∈A×A，則有x∈A．<x,x>是B×B的元素，即<x,x>∈B×B．因?yàn)锳×A=B×B，故有4所以B?A．②由①和②得A=B．第2章主要介紹關(guān)系的概念及運(yùn)算、關(guān)系的性質(zhì)與閉包運(yùn)算、等價(jià)關(guān)系、相容關(guān)系和偏序關(guān)系三個(gè)重要關(guān)系、函數(shù)以及函數(shù)相關(guān)知識(shí)等內(nèi)容．考試經(jīng)常涉及到的題型有以下5個(gè)：關(guān)系的概念理解以及關(guān)系的并、交、補(bǔ)、差以及復(fù)合和逆關(guān)系等運(yùn)算關(guān)系自反和反自反、對(duì)稱(chēng)和反對(duì)稱(chēng)等性質(zhì)的概念理解與判定；自反、對(duì)稱(chēng)和傳遞閉包運(yùn)算等價(jià)關(guān)系偏序關(guān)系和哈斯圖函數(shù)的概念和性質(zhì)所謂“關(guān)系”，就是指客體之間的相互聯(lián)系，是一種普遍存在的現(xiàn)象．任何一個(gè)有序?qū)希Q(chēng)為一RR個(gè)“二元關(guān)系”，簡(jiǎn)稱(chēng)“關(guān)系”，記作．對(duì)于二元關(guān)系，abR若<，>∈，可記作aRb；abR若<，>，則記作ab．RAaAbAR[例1]如果是非空集合上的等價(jià)關(guān)系，∈，∈，則可推知中至少包含等元素．a(chǎn)abb[答案]<，>，<，>[分析]由等價(jià)關(guān)系的概念，知道R具備了自反性、對(duì)稱(chēng)性和傳遞性．根據(jù)已知A上的元素a和b，根據(jù)自反的概念，知道R中必須包含和，由對(duì)稱(chēng)和傳遞概念，得知{，}也具備對(duì)稱(chēng)性和傳遞性，因此對(duì)應(yīng)A上的關(guān)系R至少應(yīng)該包含元素，【易錯(cuò)點(diǎn)】本題目中要求的是最小等價(jià)關(guān)系，同學(xué)們?nèi)菀讓⒋鸢笇?xiě)為{<a，a>，<a，b>，<b，a>，<b，b>}．【提示】先加入自反關(guān)系，然后再根據(jù)等價(jià)關(guān)系加入必要的對(duì)稱(chēng)和傳遞所需的元素．ARxyxyxyAR[例2]集合={1，2，3，4，5，6，7，8}上的關(guān)系={<，>|+=10且，∈}，則的性質(zhì)為（）．A．自反的B．對(duì)稱(chēng)的C．傳遞且對(duì)稱(chēng)的D．反自反且傳遞的[答案]B分析]首先，可以寫(xiě)出關(guān)系R的有限集合表示，即{<2，8>，<8，2>，<3，7>，<7，3>，<4，6>，<6，4>，<5，5>}RRRR容易看出，<1，1>，因此不是自反的．<5，5>∈因此，不是反自反的．RRRR又因?yàn)?lt;2，8>∈，且<8，2>∈，而<2，2>，因此，不具備傳遞性．因此，答案選擇BARxyxAyAxyR[例3]若={1，2}，={<，>|∈，∈，+=10}，則的自反閉包為答案]{<1，1>，<2，2>}[分析]本題考核的是關(guān)系閉包的計(jì)算．計(jì)算關(guān)系閉包有集合法、矩陣法和關(guān)系圖法．本題目可以直接使用集合法計(jì)算公式r(R)=R∪I．A首先容易計(jì)算出R=Φ，I={<，1>，<2，2>}．Ar(R)=RII∪=={<，1>，<2，2>}AA（1）函數(shù)的概念5f是集合A到B的二元關(guān)系，若任意a∈A，存在bBab∈，且<，>∈f，Dom(f)=A，設(shè)則f是一個(gè)函數(shù)（映射）．函數(shù)是一種特殊的關(guān)系．A×BA中每一個(gè)注意：集合的任何子集都是關(guān)系，但不一定是函數(shù)．函數(shù)要求對(duì)于定義域a，B中有且僅有一個(gè)元素與a對(duì)應(yīng)，而一般的關(guān)系沒(méi)有這個(gè)限制．元素（2）單射、滿射和雙射的判斷a≠a?f(a)≠f(a)；單射：若1212y滿射：f(A)=B，即對(duì)任意雙射：?jiǎn)紊淝覞M射．（3）函數(shù)的復(fù)合B∈，存在xA∈，使得y=f(x)；fABgBCfgACgf(x)=g(f(x))．：→，：→，則·：→，即(·)復(fù)合成立的條件是：Ran(f)?Dom(g)．若AabcB[例1]設(shè)={，，}，={1，2}，作fAB：→，則不同的函數(shù)個(gè)數(shù)為_(kāi)_________[答案]：8[分析]本題目考核的是學(xué)生對(duì)函數(shù)概念的理解．函數(shù)可以有下面映射規(guī)則：abc（1）,,全映射到2；（2）a映射到1，b和c映射到2；2；（3）b映射到（4）c映射到（5）a映射到（6）b映射到（7）c映射到1，a和c映射到1，a和b映射到2，b和c映射到2，a和c映射到2，a和b映射到1；2；1；1；1；abc（8）,,全映射到A到B映射個(gè)數(shù)可以描述為：因此，函數(shù)個(gè)數(shù)為C8．另外，此類(lèi)題目也可以作以下分析．CCC0+++3=8238133正確答案：3【提示】函數(shù)概念中，有兩點(diǎn)尤其要注意．第一，是函數(shù)的單值性，即對(duì)于A中任何元素，必須有B中元素映射唯一對(duì)應(yīng)；第二，是函數(shù)的定義域，即A是函數(shù)f定義域fN、R分別為自然數(shù)集與實(shí)數(shù)集，f：N→R，f(x)=x+6，則f是單射．[例2]判斷說(shuō)明：設(shè)[答案]：正確[分析]xx≠x，則有12f(x)x1=+6≠+6=f(x)，故x2f為單射．x，為自然數(shù)且1設(shè)212【提示】“單射”概念中，強(qiáng)調(diào)的是對(duì)于不同定義域中的值，通過(guò)函數(shù)映射得到的對(duì)應(yīng)值不同，這種“一對(duì)一”是從前到后的一對(duì)一，并不要求從后到前一對(duì)一．[例3]設(shè)={，}，={1，2}，R，R，R是A到B的二元關(guān)系，且AabB3RabRaa={<，2>,<，2>}，={<，1>,<，212>,<，1>}，R={<，1>,<，2>}，則（21abA到B的函數(shù)．b）不是從3RB．RA．R和122D．R和1RC．R33[答案]：B[分析]函數(shù)的概念中，強(qiáng)調(diào)兩點(diǎn)：第一，函數(shù)的單值性，即對(duì)于每一個(gè)定義域中的值，只能有一個(gè)對(duì)應(yīng)函數(shù)值；A．本題中的R不符合函數(shù)概念強(qiáng)調(diào)的第一點(diǎn)．2第二，函數(shù)的定義域必須為集合（1）偏序關(guān)系設(shè)R是非空集合A上的二元關(guān)系，如果R是自反的、反對(duì)稱(chēng)的和傳遞的，則稱(chēng)R是A上的ab偏序關(guān)系或者簡(jiǎn)稱(chēng)序關(guān)系．偏序關(guān)系記作≤．<，>∈≤，則稱(chēng)a小于等于b，記作a≤b．（2）哈斯圖6作圖規(guī)則：i．去掉每個(gè)結(jié)點(diǎn)的自回路，用空心點(diǎn)表示集合的元素；a和b，若a≤b，則將a畫(huà)在b的下方；ii．對(duì)于集合任意元素iii．對(duì)于集合任意元素a和b，若a<b，且不存在c使a<c<b，則在a和b之間劃一條弧．（3）最小元、極小元、最大元和極大元，上界和下界一個(gè)子集的極大(小)元可以有多個(gè)，而最大(小)元若有，只能惟一；且極元、最元只在該子集內(nèi)；而上界與下界可在子集之外確定，最小上界是所有上界中最小者，最小上界再小也不會(huì)小于子集中的任一元素；可以與某一元素相等，最大下界也是同樣．AR<,>的哈斯圖如所示，則集合A的最大元為a，最小元不存在．[例1]若偏序集[答案]錯(cuò)誤A的最大元不存在，a是極大元．若a為最大元，則對(duì)于任意x∈A，集合x(chóng)aR必有<,>∈，但從圖中可以得知，ga<,>R，因此a不是最大元．同時(shí)，不存在xA∈，滿足xaR<,>∈，因此，a為極大元．【易錯(cuò)點(diǎn)】哈斯圖不是簡(jiǎn)單的層次關(guān)系圖，不要用層次關(guān)系判斷最大元、最小元、極大元、極小元等．【提示】最小元應(yīng)小于等于其它各元素；最大元應(yīng)該大于等于其它各元素；極小元應(yīng)該小于等于一些元素，而與剩下的元素沒(méi)有關(guān)系；極大元應(yīng)該大于等于一些元素，而與剩下的元素沒(méi)有關(guān)系．最大元和最小元不一定存在，如果存在則必定唯一.A={1，2，3，4，5}，偏序關(guān)系≤是A上的整除關(guān)系，則偏序集A<,≤>上的元素5是集合A的（）.[例2]設(shè)集合A．最大元C．最小元B．極大元D．極小元[答案]B由于元素4和5沒(méi)有整除關(guān)系，顯然5不是最大元．同理，【提示】5和2沒(méi)有整除關(guān)系，5也不是最小元．整除關(guān)系是常考的一類(lèi)偏序關(guān)系．兩個(gè)元素是否具備整除關(guān)系可以不直接表達(dá)，所以題型描述簡(jiǎn)單，但是同學(xué)們需要將序關(guān)系的概念應(yīng)用到此類(lèi)題目中才能正確辨別．第3章是圖論的基礎(chǔ)部分，主要介紹圖論的基本概念與結(jié)論，包括圖的基本概念、圖的連通性與連通度、圖的矩陣表示等.經(jīng)常涉及到的題型有：已知點(diǎn)集和邊集畫(huà)圖，求結(jié)點(diǎn)的度數(shù)，畫(huà)補(bǔ)圖握手定理計(jì)算題強(qiáng)分圖（連通）、單向分圖（連通）、弱分圖（連通）的判斷求點(diǎn)割集，割點(diǎn)，邊割集，割邊無(wú)向簡(jiǎn)單圖，已知點(diǎn)集和邊集求鄰接矩陣我們將反映對(duì)象及其相互關(guān)系的圖分為無(wú)向圖和有向圖，那我們就仔細(xì)了解一下它們，以及它們的區(qū)別、聯(lián)系：1.無(wú)向圖是一個(gè)有序的二元組<V，E>，記作G＝<V，E>，其中V≠稱(chēng)為頂點(diǎn)集，其元素稱(chēng)為頂點(diǎn)或結(jié)點(diǎn)；其中E稱(chēng)為邊集，其元素稱(chēng)為無(wú)向邊，簡(jiǎn)稱(chēng)為邊.2.有向圖是一個(gè)有序的二元組<V，E>，記作G＝<V，E>，其中V≠稱(chēng)為頂點(diǎn)集，其元素稱(chēng)為頂點(diǎn)或結(jié)點(diǎn)；其中E稱(chēng)為邊集，其元素稱(chēng)為有向邊，簡(jiǎn)稱(chēng)為邊.小提示：①用圖形表示無(wú)向圖和有向圖時(shí)，用小圓圈表示頂點(diǎn)，用頂點(diǎn)之間的連線表示無(wú)向邊，用有方向的連線表示有向邊.②在無(wú)向圖中，與結(jié)點(diǎn)相關(guān)聯(lián)的邊的條數(shù)，稱(chēng)為該結(jié)點(diǎn)的度數(shù)，記作deg(V)，用Δ(G)表示最大度，用δ(G)表示最小度.③在有向圖中，對(duì)于任何結(jié)點(diǎn)，出度就是以其為始點(diǎn)的邊的條數(shù)，入度就是以其為終點(diǎn)的邊的條數(shù)，出度與入度之和稱(chēng)為該結(jié)點(diǎn)的度數(shù).7④如果圖G與圖H互為補(bǔ)圖，則它們的頂點(diǎn)集相同，且它們的邊集的并集等于其完全圖的邊集.[例1]設(shè)圖G＝<V，E>，V＝{v，v，v，v，v}，E＝{(v,v)，(v,v)，(v,v)，(v,v)，(v,v)，(v,3123451213224343v)，(v,v)}，試554（1）畫(huà)出G的圖形表示；（2）求出每個(gè)結(jié)點(diǎn)的度數(shù)；（3）畫(huà)出圖[解題過(guò)程G的補(bǔ)圖的圖形．]（1）關(guān)系圖先根據(jù)G的結(jié)點(diǎn)集畫(huà)出圖中的5個(gè)結(jié)點(diǎn)，這里的結(jié)點(diǎn)按逆時(shí)針排列，也可以按順時(shí)針排列.再根據(jù)邊集，在鄰接的結(jié)點(diǎn)間將邊畫(huà)出.（2）在圖示中觀察每個(gè)結(jié)點(diǎn)連接的邊數(shù)，計(jì)算出各結(jié)點(diǎn)的度數(shù).deg(v)=21deg(v)=32deg(v)=43deg(v)=34deg(v)=25（3）補(bǔ)圖補(bǔ)圖的結(jié)點(diǎn)集與原圖的結(jié)點(diǎn)集相等，補(bǔ)圖的邊集是那些由結(jié)點(diǎn)集確定的完全圖中去掉原圖中的邊所留下的邊組成的.補(bǔ)圖的邊數(shù)＝完全圖的邊數(shù)－原圖的邊數(shù)3條.又因?yàn)?個(gè)結(jié)點(diǎn)的完全圖的邊數(shù)為條.所以10－7＝[例2]設(shè)G是一個(gè)補(bǔ)圖)．n階無(wú)向簡(jiǎn)單圖，n是大于等于2的奇數(shù)．證明G與中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等(是G的[證明過(guò)程]分析]因?yàn)槲帐侄ɡ恚航Y(jié)點(diǎn)度數(shù)之和等于邊數(shù)的2倍，所以圖G的結(jié)點(diǎn)度數(shù)總和一定是偶數(shù).又因?yàn)閚是奇數(shù)，圖G有奇數(shù)個(gè)結(jié)點(diǎn)，所以n階完全圖每個(gè)頂點(diǎn)度數(shù)為偶數(shù).因此，奇數(shù)＋奇數(shù)＝偶數(shù)，若G中頂點(diǎn)v的度數(shù)為奇數(shù)，則在補(bǔ)圖中v的度數(shù)一定也是奇數(shù)，所以G與中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等．【提示】補(bǔ)圖與原圖的結(jié)點(diǎn)集相等，補(bǔ)圖與原圖的邊數(shù)之和等于其結(jié)點(diǎn)的完全圖的邊數(shù).那么在考試中是怎樣考的呢？我們來(lái)看2道歷年真題：[例1]設(shè)圖G＝<V,E>，vV，則下列結(jié)論成立的是()．（2008年9月試卷第2題）A．B．C．D．8[答案]：Ｃ[分析]選項(xiàng)A，不對(duì)..因?yàn)闆](méi)有連加符號(hào)∑，不能表示所有度數(shù)之和.選項(xiàng)B，不對(duì)不但沒(méi)有連加符號(hào)∑，而且邊數(shù)也沒(méi)有乘以2.選項(xiàng)C，正確選項(xiàng)D，不對(duì).有連加符.∑，還有邊數(shù)乘以2.表示所有的度數(shù)之和等于邊數(shù)的2倍.沒(méi)有將邊數(shù)也沒(méi)有乘以2.【提示】【易錯(cuò)點(diǎn)】不論圖中有奇數(shù)個(gè)結(jié)點(diǎn)或者偶數(shù)個(gè)結(jié)點(diǎn)，圖的度數(shù)之和都是偶數(shù).同學(xué)們?nèi)菀淄泴⑦厰?shù)乘以2倍，容易忘記表示所有度數(shù)之和的連加符號(hào).[例2]設(shè)G是一個(gè)圖，結(jié)點(diǎn)集合為V，邊集合為E，則G的結(jié)點(diǎn)度數(shù)之和為_(kāi)________．[答案]2（或“邊數(shù)的兩倍”）[分析]根據(jù)握手定理，在圖中所有結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的【提示】2倍.不論圖中有奇數(shù)個(gè)結(jié)點(diǎn)或者偶數(shù)個(gè)結(jié)點(diǎn)，圖的度數(shù)之和都是偶數(shù)那么在考試中是怎樣考的呢？我們來(lái)看2道歷年真題：[例1]設(shè)有向圖（a）、（b）、（c）與（d）如圖一所示，則下列結(jié)論成立的是()．（2009年1月試卷第2題）A．（a）是強(qiáng)連通的B．（b）是強(qiáng)連通的D．（d）是強(qiáng)連通的C．（c）是強(qiáng)連通的[答案]Ｄ[分析]選項(xiàng)A，不對(duì).（a）圖存在一點(diǎn)（左下角點(diǎn)）不可達(dá)其它點(diǎn)，所以不是強(qiáng)連通圖.但圖存在一點(diǎn)（左上角點(diǎn)）可達(dá)其它各點(diǎn)，所以是單向連通圖，也是弱連通圖.選項(xiàng)B，不對(duì).b）圖存在一點(diǎn)（右上角點(diǎn)）不可達(dá)其它點(diǎn)，所以不是強(qiáng)連通圖.但圖存在一點(diǎn)（右下角點(diǎn)）可達(dá)其它各點(diǎn)，所以是單向連通圖，也是弱連通圖選項(xiàng)C，不對(duì)..（c）圖存在兩點(diǎn)（右上和左下角點(diǎn)）不可達(dá)其它點(diǎn)，所以不是強(qiáng)連通圖.但圖略邊去的方向后，是連通圖，所以是弱連通圖.選項(xiàng)D，正確（d）圖中任何兩結(jié)點(diǎn)互相可達(dá)，所以是強(qiáng)連通圖，當(dāng)然也是單向連通圖和弱連通圖易錯(cuò)點(diǎn)】同學(xué)們要完全理解弱連通圖、意向連通圖、強(qiáng)連通圖的概念，不能將它們混淆.【提示】..強(qiáng)連通圖一定是單向連通圖和弱連通圖；單向連通圖一定是弱連通圖.反之，不成立.[例2]判斷下圖是哪類(lèi)連通圖.9⑴⑵（3）[解題過(guò)程]（1）存在.V點(diǎn)，可達(dá)其它各點(diǎn)1V、V、V，所以是單向連通圖3.但圖中V3點(diǎn)不可達(dá)其它點(diǎn)，所以不是24強(qiáng)連通圖（2）略去邊的方向后，不是連通圖，所以不是任何連通圖（3）存在V點(diǎn)，可達(dá)其它各點(diǎn)1.V、V、V.324存在V點(diǎn)，可達(dá)其它各點(diǎn)2V、V、V.134存在V點(diǎn)，可達(dá)其它各點(diǎn)3V、V、V.124存在V點(diǎn)，可達(dá)其它各點(diǎn)V、V、V.4123因此，任何兩結(jié)點(diǎn)都可達(dá)，所以是強(qiáng)連通圖【提示】強(qiáng)連通圖一定是單向連通圖和弱連通圖；單向連通圖一定是弱連通圖.反之，不成立.那么在考試中是怎樣考的呢？我們來(lái)看[例1]如圖一所示，以下說(shuō)法正確的是A．e是割點(diǎn)2道歷年真題：()．（2008年9月試卷第4題）B．{a,e}是點(diǎn)割集D．wmu88qs是點(diǎn)割集C．{b,e}是點(diǎn)割集[答案]Ａ[分析]去掉點(diǎn)選項(xiàng)A，正確.e和其連接的邊后，圖就不連通了.選項(xiàng)B，不對(duì)．雖然去掉點(diǎn)ａ、點(diǎn)a．e和其連接的邊后，圖就不國(guó)通了.但是單單去掉點(diǎn).但是單單去掉點(diǎn)e和其連接的邊后也可以不連通，所以不應(yīng)該包括點(diǎn)e和其連接的邊后也可以不連通，所以不應(yīng)該包括點(diǎn)選項(xiàng)C，不對(duì).雖然去掉點(diǎn)b.b、點(diǎn)e和其連接的邊后，圖就不連通了選項(xiàng)D，正確.去掉點(diǎn)d和其連接的邊后，圖依然連通【提示】.點(diǎn)割集里只有一個(gè)結(jié)點(diǎn)時(shí)，這個(gè)結(jié)點(diǎn)才是割點(diǎn).【易錯(cuò)點(diǎn)】同學(xué)們要準(zhǔn)確地確定點(diǎn)割集里的結(jié)點(diǎn)，不能含多余的結(jié)點(diǎn).[例2]如圖一所示，以下說(shuō)法正確的是A．｛（a，e）｝是割邊C．{（a，e）,（b，ｃ）}是邊割集(）．（2010年7月試卷第B．｛(a,e)｝是邊割集D．｛(ｄ,e)｝是邊割集4題）[解題過(guò)程][分析]選項(xiàng)A，不對(duì).去掉邊（a，e）后，圖依然連通.而且{（a，e）}是集合a，e）后，圖依然連通.選項(xiàng)B，不對(duì)選項(xiàng)C，不對(duì).去掉邊（..去掉邊（a，e），（選項(xiàng)D，正確b，c）后，圖依然連通..去掉邊（d，e）后，圖就不連通了.【提示】邊割集里只有一條邊時(shí)，這條邊才是割邊．【易錯(cuò)點(diǎn)】10同學(xué)們要準(zhǔn)確地確定邊割集里的邊，不能含有多余的邊．[例1]已知圖G的鄰接矩陣為則則G有（）.（2008年7月試卷第5題）A．5點(diǎn)，8邊B．6點(diǎn)，7邊D．5點(diǎn)，7邊C．6點(diǎn)，8邊[解題過(guò)程]選項(xiàng)A，不對(duì)。因?yàn)闊o(wú)向圖的鄰接矩陣的上三角矩陣數(shù)字之和為選項(xiàng)B，不對(duì)。7，所以邊數(shù)為7。因?yàn)猷徑泳仃囀?×5方陣，所以圖的結(jié)點(diǎn)數(shù)為5個(gè)。選項(xiàng)C，不對(duì)。因?yàn)猷徑泳仃囀?×5方陣，所以圖的結(jié)點(diǎn)數(shù)為5個(gè)。因?yàn)闊o(wú)向圖的鄰接矩陣的上三角矩陣數(shù)字之和為選項(xiàng)D，正確。7，所以邊數(shù)為7。【提示】n個(gè)結(jié)點(diǎn)的鄰接矩陣為n×n矩陣，即n行n列矩陣.【易錯(cuò)點(diǎn)】有向圖的鄰接矩陣?yán)锼械臄?shù)字之和等于邊數(shù).而因?yàn)闊o(wú)向圖忽略了方向，所以無(wú)向圖的鄰接矩陣的上三角矩陣數(shù)字之和或者下三角矩陣數(shù)字之和才是邊數(shù).不要混淆．[例2]設(shè)G＝<V，E>，V＝{v，v，v，v}，E＝{(v,v)，(v,v)，(v,v)，(v,v)}，試寫(xiě)出其鄰接矩陣2.12341323434[解題過(guò)程]圖G有4個(gè)結(jié)點(diǎn)，則G的鄰接矩陣為4×4矩陣，按結(jié)點(diǎn)的序號(hào)排序，根據(jù)結(jié)點(diǎn)間的鄰接關(guān)系，確定鄰接矩陣中的對(duì)應(yīng)v，v）對(duì)應(yīng)的位置為v，v）對(duì)應(yīng)的位置為數(shù)值。邊（v，v）對(duì)應(yīng)的位置為11，邊（1，邊（1，邊（v，v）對(duì)應(yīng)的位343置為1.又因?yàn)槭菬o(wú)向圖，所以邊沒(méi)有方向，因此在（2324v，v）（v，v），（v，v），（v，v）的位置也是1.其余的位31324243置由于沒(méi)有邊，因此為0.鄰接矩陣：【提示】n個(gè)結(jié)點(diǎn)的鄰接矩陣為n×n矩陣，即n行n列矩陣。無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)矩陣.第1章主要介紹集合論的基本概念和結(jié)論，集合的運(yùn)算及其性質(zhì)，以及利用運(yùn)算性質(zhì)進(jìn)行集合表達(dá)式的化簡(jiǎn)和集合恒等式的證明等內(nèi)容．考試經(jīng)常涉及到的題型有以下歐拉通路、歐拉圖的判別方法漢密爾頓圖的判斷方法平面圖的判斷方法（1）定義的要點(diǎn)：圖Ｇ滿足無(wú)向，連通，經(jīng)過(guò)每條邊一次且僅一次，經(jīng)過(guò)每個(gè)結(jié)點(diǎn)（注意：點(diǎn)可重復(fù)經(jīng)過(guò)，邊不能重復(fù)經(jīng)過(guò)），這四點(diǎn)缺一不可．4個(gè)：如果同時(shí)滿足這四點(diǎn)，當(dāng)始點(diǎn)與終點(diǎn)不重合時(shí)，就是歐拉通路．如果同時(shí)滿足這四點(diǎn)，當(dāng)始點(diǎn)與終點(diǎn)重合時(shí)，就是歐拉圖．（2）歐拉圖判定定理的要點(diǎn)：無(wú)向、連通圖Ｇ是歐拉圖的若無(wú)向、連通圖Ｇ是歐拉圖，那么Ｇ一定不含奇數(shù)度結(jié)點(diǎn)．反之，若無(wú)向、連通圖Ｇ不含奇數(shù)度結(jié)點(diǎn)，那么Ｇ一定是歐拉圖．（3）歐拉通路判定定理的要點(diǎn)：無(wú)向、連通圖Ｇ是歐拉通路的點(diǎn)．當(dāng)Ｇ不含奇數(shù)度結(jié)點(diǎn)時(shí)，Ｇ是歐拉圖（充要條件是）Ｇ不含奇數(shù)度結(jié)點(diǎn)．（充要條件是）Ｇ不含奇數(shù)度結(jié)點(diǎn)或只含2個(gè)奇數(shù)度結(jié)．若無(wú)向、連通圖是歐拉通路，那么不含奇數(shù)度結(jié)點(diǎn)或只含2個(gè)奇數(shù)度結(jié)點(diǎn)．11反之，若無(wú)向、連通圖Ｇ不含奇數(shù)度結(jié)點(diǎn)或只含2個(gè)奇數(shù)度結(jié)點(diǎn)，那么Ｇ一定是歐拉通路．當(dāng)Ｇ不含奇數(shù)度結(jié)點(diǎn)時(shí)，Ｇ是歐拉圖．那么在考試中是怎樣考的呢？我們來(lái)看5道歷年真題：10，則其冪集的元素個(gè)數(shù)為[例1]若集合A的元素個(gè)數(shù)為A．ｍ為奇數(shù)C．ｎ為奇數(shù)[答案]：C[分析]()．B．ｎ為偶數(shù)D．ｍ為偶數(shù)關(guān)鍵：無(wú)向完全圖為偶數(shù)，于是ｎ為奇數(shù)．知識(shí)點(diǎn)：根據(jù)歐拉圖定義，每個(gè)結(jié)點(diǎn)的度數(shù)都是偶數(shù)，不含奇數(shù)度結(jié)點(diǎn)，完全圖是連通圖．的總度數(shù)為，平均每個(gè)結(jié)點(diǎn)的度數(shù)為，如果中存在歐拉圖，則每個(gè)結(jié)點(diǎn)的度數(shù)均[例2]無(wú)向圖Ｇ存在歐拉回路，當(dāng)且僅當(dāng)[答案]：所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)[分析]Ｇ連通且_________關(guān)鍵：歐拉圖判定定理的要點(diǎn)：連通、不含奇數(shù)度結(jié)點(diǎn)．知識(shí)點(diǎn)：歐拉圖判定定理[例3]判斷下列各題正誤，并說(shuō)明理由．1所示的圖G存在一條歐拉回路：無(wú)向連通圖Ｇ是歐拉圖的（充要條件是）Ｇ不含奇數(shù)度結(jié)點(diǎn)．（2008年9月試卷第15題）如圖.[答案]：正確．[分析]關(guān)鍵：歐拉圖判定定理的要點(diǎn)：歐拉圖判定定理：連通、不含奇數(shù)度結(jié)點(diǎn)．知識(shí)點(diǎn)：無(wú)向連通圖G是歐拉圖的（充要條件是）的度數(shù)分別為G不含奇數(shù)度結(jié)點(diǎn)．因?yàn)閳DＧ為連通的，且結(jié)點(diǎn)2,4,4,4,4，均為偶數(shù)，不含奇數(shù)度結(jié)點(diǎn)，所以Ｇ存在一條歐拉回路．（2008年7月試卷第6題）[例4]判斷下列各題正誤，并說(shuō)明理由．如圖所示的圖Ｇ存在一條歐拉回路．[答案]：錯(cuò)誤.因?yàn)閳D[分析]關(guān)鍵：歐拉圖判定定理的要點(diǎn)：歐拉圖判定定理[例5]]判斷下列各題正誤，并說(shuō)明理由．G是無(wú)向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖[答案]：錯(cuò)誤.因?yàn)轭}中的圖G缺少連通的條件[分析]關(guān)鍵：根據(jù)歐拉圖定義，缺少連通的條件．當(dāng)圖不連通時(shí)，圖G為中包含度數(shù)為奇數(shù)的結(jié)點(diǎn).：連通、不含奇數(shù)度結(jié)點(diǎn)．知識(shí)點(diǎn)：無(wú)向連通圖是歐拉圖的（充要條件是）G是歐拉圖G不含奇數(shù)度結(jié)點(diǎn)．．如果圖.Ｇ不是歐拉圖．知識(shí)點(diǎn)：歐拉圖的要點(diǎn)是：連通、無(wú)向圖、不含奇數(shù)度結(jié)點(diǎn)．本題缺少連通條件．【易錯(cuò)點(diǎn)】容易漏掉歐拉圖的部分要點(diǎn)．（1）定義的要點(diǎn)：圖Ｇ存在一條路，經(jīng)過(guò)每個(gè)結(jié)點(diǎn)一次且僅一次．在滿足定義的條件下，若這條路是回路，則圖Ｇ是漢密爾頓圖．．在滿足定義的條件下，若這條路不是回路，則圖Ｇ是漢密爾頓通路．（2）定理4.2.1：如果圖中具有一條漢密爾頓回路（即漢密爾頓圖），則對(duì)于Ｖ的每個(gè)非空子集S，均有其中是的連通分支12也就是說(shuō)，從圖G中去掉若干個(gè)結(jié)點(diǎn)（至少一個(gè)結(jié)點(diǎn)），得到的連通分支數(shù)（即連通圖數(shù)）不大于去掉的點(diǎn)數(shù).。[例1]若圖中有一條漢密爾頓回路，則對(duì)于的G每個(gè)非空子集S，在G中刪除非空子集中的所有結(jié)點(diǎn)得到的連通分支數(shù)為W，則S中的結(jié)點(diǎn)數(shù)與W滿足關(guān)系式__________．[答案]：[分析]關(guān)鍵：記住定理4.2.1的條件和結(jié)論．知識(shí)點(diǎn)：定理4.2.1：如果圖中具有一條漢密爾頓回路（即漢密爾頓圖），則對(duì)于Ｖ的每個(gè)非空子集Ｓ，均有的連通分支．，其中是【易錯(cuò)點(diǎn)】容易機(jī)械記憶定理，用表示分支數(shù)．【提示】本題敘述與定理敘述不同，這里是用Ｗ表示．[例2]若Ｇ是一個(gè)漢密爾頓圖，則Ｇ一定是()A．平面圖B．對(duì)偶圖C．歐拉圖D．連通圖[答案]：D[分析]（1）漢密爾頓圖定義：Ｇ存在一條回路，經(jīng)過(guò)每個(gè)點(diǎn)一次且僅一次．（2）連通圖定義：對(duì)任意兩點(diǎn)，存在路徑，使得一點(diǎn)達(dá)到另一點(diǎn)【提示】漢密爾頓圖定義要點(diǎn)：G存在一條回路，經(jīng)過(guò)每個(gè)點(diǎn)一次且僅一次（1）定義的要點(diǎn)：任意兩條邊，除結(jié)點(diǎn)外沒(méi)有任何交點(diǎn)．（2）歐拉定理：連通平面圖G的結(jié)點(diǎn)數(shù)為v，邊數(shù)為e，面數(shù)為，則．（3）定理4.3.3：設(shè)G是一個(gè)有v個(gè)結(jié)點(diǎn)e條邊的連通、簡(jiǎn)單、平面圖，若那么在考試中是怎樣考的呢？我們來(lái)看2道歷年真題：，則．[例1]設(shè)連通平面圖G的結(jié)點(diǎn)數(shù)為5，邊數(shù)為6，則面數(shù)為_(kāi)_____________．關(guān)鍵：利用歐拉定理：連通平面圖G的結(jié)點(diǎn)數(shù)為v，邊數(shù)為e，面數(shù)為，則．解應(yīng)填．[例2]設(shè)G是連通平面圖，v，e，分別表示G的結(jié)點(diǎn)數(shù)，邊數(shù)和面數(shù)，則v，e和滿足的關(guān)系式______________．關(guān)鍵：利用歐拉定理：連通平面圖G的結(jié)點(diǎn)數(shù)為v，邊數(shù)為e，面數(shù)為，則．解應(yīng)填．[例3]設(shè)G是具有n個(gè)結(jié)點(diǎn)m條邊k個(gè)面的連通平面圖，則m等于______________關(guān)鍵：利用歐拉定理：連通平面圖G的結(jié)點(diǎn)數(shù)為n，邊數(shù)為m，面數(shù)為k，則解應(yīng)填．（2010年1月試卷第9題）．．一、題型分析樹(shù)是圖論中的重要部分之一，其在計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域有著廣泛的應(yīng)用，二叉樹(shù)更是程序設(shè)計(jì)中的一種基本的數(shù)據(jù)結(jié)構(gòu).本章主要介紹樹(shù)、生成樹(shù)、二叉樹(shù)、樹(shù)根、最優(yōu)樹(shù)等概念及相關(guān)的結(jié)論與算法，包括求最小生成樹(shù)的Kruskal算法、構(gòu)造最優(yōu)樹(shù)的Huffman算法以及前綴碼的求法.經(jīng)常涉及到的題型有：1.樹(shù)葉與結(jié)點(diǎn)間的計(jì)算2.畫(huà)最小生成樹(shù)并求其權(quán)133.構(gòu)造最優(yōu)樹(shù)（Huffman算法）并求其權(quán)4.求前綴碼因此，在本章學(xué)習(xí)過(guò)程中希望大家要清楚地知道一些概念：樹(shù)連通無(wú)簡(jiǎn)單回路的無(wú)向圖G.樹(shù)中次數(shù)為1的頂點(diǎn)稱(chēng)為樹(shù)葉．次數(shù)大于1的頂點(diǎn)稱(chēng)為分支點(diǎn)或內(nèi)部頂點(diǎn)．森林一個(gè)無(wú)向圖稱(chēng)為森林，如果它的每個(gè)連通分圖都是樹(shù)．樹(shù)的判別給定圖T，則以下命題關(guān)于圖T為樹(shù)的定義等價(jià)．(1)T是無(wú)回路的連通圖；(2)圖T無(wú)回路且e＝v－1，其中e是邊數(shù)，v是頂點(diǎn)數(shù)；(3)圖T連通且e＝v－1；(4)圖T無(wú)回路，若增加一條新邊，得到且僅得到一個(gè)回路；(5)圖T連通，但刪去任一邊后圖便不連通（v≥0）；(6)圖T的每一對(duì)頂點(diǎn)之間有且僅有一條路（v≥0）．生成樹(shù)給定一個(gè)無(wú)向圖G，若G的一個(gè)生成子圖T是樹(shù)，則稱(chēng)T為G的生成樹(shù)或支撐樹(shù)．T的邊稱(chēng)為樹(shù)枝．生成樹(shù)的結(jié)論任何連通圖至少有一棵生成樹(shù)．權(quán)與帶權(quán)圖n個(gè)結(jié)點(diǎn)的連通圖G，每邊指定一正數(shù)，稱(chēng)為權(quán)，每邊帶權(quán)的圖稱(chēng)為帶權(quán)圖．G的生成樹(shù)T中樹(shù)枝的權(quán)之和稱(chēng)為T(mén)的權(quán)，記作W(T)．有向樹(shù)如果一個(gè)有向圖在不考慮邊的方向時(shí)是一棵樹(shù)，那么該有向圖就是有向樹(shù)．根樹(shù)與樹(shù)根一棵有向樹(shù)T，若恰有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度都為1，則稱(chēng)T為根樹(shù)；入度為0的頂點(diǎn)稱(chēng)為樹(shù)根；出度為0的頂點(diǎn)稱(chēng)為樹(shù)葉；入度為1出度不為0的頂點(diǎn)稱(chēng)為內(nèi)點(diǎn)；根與內(nèi)點(diǎn)統(tǒng)稱(chēng)為分支點(diǎn)；從樹(shù)根到T的任一頂點(diǎn)v的通路（頂點(diǎn)不同的路）的長(zhǎng)度稱(chēng)為v頂點(diǎn)的層數(shù)；層數(shù)最大的頂點(diǎn)的層數(shù)稱(chēng)為樹(shù)高．[例1]設(shè)圖G是有6個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的總度數(shù)為18，則可從G中刪去條邊后使之變成樹(shù)．【答案】4【分析】運(yùn)用教材中的定理5.1.1，可以作出正確選擇．因?yàn)槎ɡ鞧變?yōu)闃?shù)，則邊數(shù)e＝6-1＝5。由于題中結(jié)點(diǎn)的總度數(shù)為9-5＝4條邊才能使圖G是樹(shù)。【易錯(cuò)點(diǎn)】5.1.1中給出的圖G為樹(shù)的等價(jià)定義之一是圖G連通且e＝v-1（e是邊數(shù)，v是頂9條。所點(diǎn)數(shù)）．若圖18，根據(jù)定理3.1.1，總度數(shù)應(yīng)為邊數(shù)2倍，可知此圖中有邊數(shù)以應(yīng)該刪去大家對(duì)集合中有的元素用集合形式表示的情形容易混淆，但這種類(lèi)型考題中經(jīng)常出現(xiàn)，大家一定要習(xí)慣．本題主要是檢查大家對(duì)屬于關(guān)系∈和包含關(guān)系?是否理解，能否正確運(yùn)用?！咎崾尽渴紫葯z查各選項(xiàng)給出的關(guān)系符號(hào)∈和?左邊的式子是集合A的元素還是子集，然后判斷選項(xiàng)中使用的關(guān)系符號(hào)是否正確，確定選項(xiàng)。[例2]已知一棵無(wú)向樹(shù)T中有8個(gè)結(jié)點(diǎn)，4度，3度，2度的分支點(diǎn)各一個(gè)，T的樹(shù)葉數(shù)為．[答案]5[分析]設(shè)無(wú)向樹(shù)那么，由T的樹(shù)葉數(shù)為x，因?yàn)闃?shù)葉是度數(shù)為1的結(jié)點(diǎn)．定理3.1.1（握手定理）設(shè)G是一個(gè)圖，其結(jié)點(diǎn)集＝－合為V，邊集合為E，則得：4+3+2+x=2（8-1），即x=5．應(yīng)填5．【易錯(cuò)點(diǎn)】題中沒(méi)有直接給出圖Ｇ的邊數(shù)，而是給出了結(jié)點(diǎn)的總度數(shù)，這里大家要清楚總度數(shù)和邊數(shù)之間的關(guān)系?！咎崾尽吭O(shè)G是有ｎ個(gè)結(jié)點(diǎn)，ｍ?xiàng)l邊的連通圖，必須刪去Ｇ的(m-n+1)條邊，才能確定G的一棵生成樹(shù)求最小生成樹(shù)的方法主要有避圈法與破圈法．那到底什么是避圈法和破圈法？我們一起來(lái)看一看：避圈法：圖G有n個(gè)頂點(diǎn)，以下算法產(chǎn)生的是最小生成樹(shù)（避圈法由kfuskal給出.（1）選擇最小的邊e1，置邊數(shù)i←1；（2）i=n-1結(jié)束，否則轉(zhuǎn)3）；（3）設(shè)定已選定e1，e2,，…，ei，，在G中選取不同于e1，e2,，…，ei的邊ei+1，使{e1，e2,，…，ei，ei+1}無(wú)回路，且ei+1是滿足此條件的帶權(quán)最小的邊；（4）i←i+1，轉(zhuǎn)2）．?破圈法：（1）初始令G0,=G,i←0；（2）若Gi中不含圈，則轉(zhuǎn)（3）；否則，設(shè)C為Gi中的一個(gè)圈，ei為C上帶權(quán)最大的邊，令Gi+1=Gi-