离散数学复习要点2338

1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详2、联结词运算定律┐∧∨→记住特殊的：1∧11，0∨00，1→00，111，001详见P53、命题符号化步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。B设出原子命题写出符号化公式。详见P54、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P95、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。②大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开式的真值。详见P8。对每个指派，以二进制数从小到大或从)，最后列出所求公6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P157、等价式详见P22表1.6.2证明方法：①真值表完全相同主要等价式：(1)双否定：AA。(2)交换律：A∧BB∧A，A∨BB∨A，ABBA。3)结合律：(A∧B)∧CA∧(B∧C)，(A∨B)∨CA∨(B∨C)，(AB)CA(BC)。(4)分配律：A∧(B∨C)(A∧B)∨(A∧C)，A∨(B∧C)(A∨B)∧(A∨C)。(5)德·摩根律：(A∧B)A∨B，(A∨B)A∧B。(6)等幂律：A∧AA，A∨AA。(7)同一律：A∧TA，A∨FA。(8)零律：A∧FF，A∨TT。(9)吸收律：A∧(A∨B)A，A∨(A∧B)A。(10)互补律：A②用等价演算③利用AB的充要条件是AB且BA。A∨B，A→BB→A。(12)双条件式转化8、蕴含式详见P23表1.6.3证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。④用定义，证AB，即证A→B是永真式。9、范式求法步骤：①使用命题定律，消去公式中除、和以外公式中出现的所有联结词；②使用(P)P和德·摩根律，将公式中出现的联结词都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧PP。(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则PP∧（Q∨Q)或PP∨（Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。注意：主析取范式与主合取范式之间的联系。例如：(PQ)Qm1m3M0M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。详见P1611、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。重点规则（主要蕴含式）：(1)P∧QP化简(2)P∧QQ化简(3)PP∨Q附加(6)(P→Q)P变形化简(7)(P→Q)Q变形化简(8)P，(P→Q)Q假言推理P，(P∨Q)Q析取三段论(11)(P→Q)，(Q→R)P→R条件三段论(12)(PQ)，(QR)PR双条件三段论步：一命题符号化，二写出前提和结论，三进行证明。详见P21(4)PP→Q变形附加(5)QP→Q变形…1.命题的是()A.走，看电影去+y>0C.空集是任意2.下列式子为重言式的是(→P∨QB.(┐P∧Q)∧(P∨┐Q)C.┐(P3．下列为两个命题变元P，Q的小项是（）集合的真子集D.你明天能来吗)D.(P∨Q)(P→Q)A．P∧Q∧PB．P∨QC．P∧QD．P∨P∨Q4．下列语句中是真命题的是（）A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的C．（PQ）6．命题公式（P∧（P→Q））→Q是（）A．矛盾式B．蕴含式C．重言式D．等价式7．命题公式（P∧Q）→R的成真指派是（）B．001，011，101，110，111C．全体指派D．无“他虽聪明但不用功”的确的是（）A．Q→（P∨Q）B．（P∧Q）→PC．（P∧Q）∧（P∨Q）D．（P→Q）（P∨Q）11.设命题变元为P，Q，R，则小项m100=________，大项M010=________。12.置换规则：在证明的任何步骤上，命题公式中的任何子命题公式都可以________，记为________规则。13.请用联结词┐，∧表示联结词∨和联结词：________，________。14．两个重言式的析取是________式，一个重言式与一个矛盾式的析取是________式。15．命题公式（PQ）→P的成真指派为__________，成假指派为__________。16.用等值演算求(P→Q)→R的主合取范式。17.列出(P→(Q∨R))(P→Q)的真值表。.19．构造命题公式（（P∧Q）→P）∨R的真值表。20．求下列公式的21．构造命题公式（PQQR）→PR的真值表。22．求下列公式的主析取范式和主合取范式：（P→（QR））（P→（Q→R））。主合取范式和主析取范式：P∨（P→（Q∨（Q→R）））23.用推理方法证明：P∨Q，P→R，Q→S├R∨S。24．构造下面推理的小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。25．构造下面推理的A曾到过受害者房间并且11点以前没离开，A就犯了谋杀罪。A曾到过受害者房间。11点以前离开，看门人会看见他。看门人没有看见他。所以A犯了谋杀罪。证明。如果证明。只要如果在，离散数学复习要点第二章谓词逻辑一、典型考查点1、基本概念：个体词、个体域、谓词、特性谓词、辖域，详见P27；前2、谓词符号化步骤：①正确理解给定命题。把命题改叙，使其中每个原子命题、原子命题表达出来。②把每个原子命题分解成个体、谓词和量词；在全总论域讨论时，要给出特性谓词。③找出恰当注意全称量词(x)后跟条件式，存在量词(x)后跟合取式。④用恰当的联结词把给定命题表示出来。详见P303、谓词公式类型的判定（永真式、永假式、可满足式）方法：利用论域翻译成自然语言后进行判断。详见P34束范式详见P36必要时之间的关系能明显量词。应4、自由变元与约束变元的判定方法：按定义，关键是要看它在A中是约束出现，还是自由出现，若与量词的指导变元相同，就是约束出现，不同就是自由出现。详见P31。5、等价式(1)量词否定等价式：(a)(x)A(x)A(b)(x)A(x)A(2)量词辖域缩小或扩大等价式((a)(x)(A(x)∧B)(x)A(x)∧B(b)(x)(A(x)∨B)(x)A(x)∨B(c)(x)(A(x)→B)(x)A(x)→B(d)(x)(B→A(x))B→(x)A(x)(a)(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)(b)(x)(A(x)∨B(x))(x)A(x)∨(x)B(x)其中，A(x)，B(x)为有x自由出现的任何公式。详见P34356、前束范式方法：①把量词全部通过等值演算化到整个谓词公式的前面②把量词前面的┐全部通过德摩根定律化到谓词公式的内部。详见P36~A.(x)(P(x)→(x)(Q(x)∧A(x，y)))B.(x)∧(y)∨P(x，y))@3.对于公式(x)(y)P(x，y)∨Q(x，z)∧(x)P(x，y)，下列说法正确的是(是自由变元是约束变元)C.(x)的辖域是P(x，y)∨Q(x，z)D.(x)的辖域是P(x，y)4.设论域为{1，2}，与公式(x)┐A(X)等价的是()A.┐A(1)∨┐A(2)B.┐A(1)→┐(A2)C.┐A(1)∧┐A(2)D.A(1)→A(2)-5．在公式（x）F（x，y）→（y）G（x，y）中变元x是（）A．自由变元B．约束变元C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元6．下列等价式不正确的是（）A．x(P(x)Q(x))xP(x)xQ(x)B．x(P(x)Q(x))xP(x)xQ(x)C．x(P(x)Q(x))xP(x)xQ(x)D．x(P(x)Q)xP(x)Q7．设A（x）:x是人，B（x）：x，误命题“没有不犯错的误人”符号化为（）A．x(A(x)B(x))B．x(A(x)B（x））C．x(A(x)B(x))D．x(A(x)B(x))—二、填空题8.一个公式，如果量词均在全式的________，其作用域延伸到整个公式的________，则该公式称为前束范式。9．（x）（y）（P（x，y）Q（y，z））∧xP（x，y）中x的辖域为________，x的辖域为________。10．公式（x）（F（x）→G(y)）→(y)(H(x)L(x,y,z))中的自由变元为_________，约束变元为__________。三、综合应用题11．符号化下面命题，并构造推理证明：人是要死的，苏格拉底是人，所以苏格拉底是要死的。离散数学复习第三章集合与函数一、典型考查点\1、基本概念判断：函数的入射、满射、双射及定理、复合运算，详见P72，73，75。幂集、差集、对称差、笛卡尔积，详见P46，47，43，49。全序关系，详见P68.。方法：理解概念即可，按定义的步骤计算。2、关系的相关概念判断：①特殊关系：若R=，为空关系；若R=AB，为全域关系。R={<x,x>|xA}为A上的恒等系，记为IA。方法：根据定义判断。②定义域:D(R)={x|(y)(xRy)}值域:R(R)={y|(x)(xRy)}域:F(R)=D(R)+R(R),方法：定义域就是关系R中第一位元素的集合，值域就是R中第二位元素的集合，域就是定义域并上值域。③表示关方法：集合列举法\关系矩阵\关系图方法：根据题目条件，用列举法写出关系R，画出关系图（有向图）或写出关系矩阵。详见P50,51,52.3、关系的性质判断：判断方法如下：详见P54R是A上关系…自反性反自反性对称性传递性反对称性xA<x,x>xxAxRxxRy→yRxxRy→<y,x>R除x=yxRyyRz→xRz定义R沿对角线对、主对角线全为1主对角线全为0沿主对角线不对称矩阵特征称:有边则双向若有边，则是单向边图特征每个顶点都有环每顶点都没有边环IAR=集合特征IARR-1=R】RIAIA4、关系的运算：①关系的集合运算，按集合的运算规律即可：交、并、补、差、对称差等。②复合运算：按顺序运算，逆运算，交换每个元的第一、二位元素的位置即<x,y>变<y,x>。③闭包运算：即先判断R本身是否具有自反（对称、传递），若有，则自反（对称、传递）闭包就是R本身，即r(R)=R(或s(R)=R,t(R)=R),若没有，则增加R的元素，加到恰好满足自反性为止，既不能多，也不少。详见P555、等价关系和划分的判断及证明：①等价关系的证明：自反、对称、传递三个性质的条件的变通。②等价关系与划分一一对应，等价关系的等价类即为确定的划分的分块，即有关系的，划在同一块。划分中凡在同一个分块中的元，都写成满足关系的元，这样写出的关系R就是一个等价关系。逐一验证。要注意给出的等价关系6、相容关系和覆盖的判断：相容关系两个性质：自反和对称，注意：相容关系图的画法省略了自反和对称。覆盖按定义判断即可。详见P617、偏序关系与哈斯图直接关系，中间没有第三个元，即若a<b且不存在cA，使得a<c<b。②偏序关系与哈斯图住的联系来表示，省略全部向上的箭头，省略自反性的自环，省略了传递性。反之，由哈斯图写偏序关系也要注意这四点，除了直接的盖住关系外，还有自反和传递也要写出来。：①基本概念：三个性质：自反、反对称和传递；可比，就是有关系，a≤bb≤a；盖住，就是：画图注意四点：使用盖<A,≤>为偏序集，BA，bB，①若(x)(xBb≤x)为真，则称b为B的最小元。②若(x)(xBx≤b)为真，则称b为B的最大元。③若(x)(bxx≤b)为真，则称b为B的极小元。·④若根据定义判断时，最小（大）元与极小（大）元是有区别的，最小（大）元是B中最小（大）的元素，它与B中其他元素都可比；而极小（大）元不一定与B中元素都可比，只要没有比它小（大）的元素，它就是极小（大）元。对于B，极小（大）元一定存在，但最小（大）元不一定存在，若B中只有一个极小（大）元，则它一定是B的最小（大）元。详见P689、求上界下界上确界和下确界：设<A,≤>为偏序集，BA，bA，①若(x)(xBb≤x)为真，则称②若(x)(xBx≤b)为真，则称b为B的上界。③若b是一下界且对每一个B的下界b’有b’≤b，则称b为B的最大下界或下确界，记为glb。④若b是一上界且对每一个B的上界b’有b≤b’，则称b为B的最小上界或上确界，记为lub。有穷集且可能有多个，存在则必唯一。若b为B的下界。判断时注意，上界下界上确界和下确界是A集合上来找的，B的上界，下界，最小上界，最大下界都可能不存在。若下界是唯一的。详见P691.设Z+是正整数集，f：Z+×Z+→Z+，f(n，m)=nm，则f()A.仅是入射B.仅是满射C.是双射D.不是函数)1011000011013.设R1和R2是集合A上的相容关系，4．集合A={1，2，…，10}上的关系R={<x，y>|x+y=10，x∈A，y∈A}，则A．自反的B．对称的C．传递的、对称的D．反自反的、5．若R和S是集合A上的两个关系，则下述结论正确的是（）A．若R和S是自反的，则R∩S是自反的B．若C．若R和S是反对称的，则RS是反对称的D．若R和S是传递的，则2CR的性质是（）RS是对称的R∪S是传递的R和S是对称的，则6．R={<1，4>，<2，3>，<3，1>，<4，3>}，则下列不是t（R）中元素的是（）A．<1，1>B．<1，2>C．<1，3>D．<1，4>7．设A={{1，2，3}，{4，5}，{6，7，8}}，下列选项正确的是（）A．1∈AB．{1，2，3}AC．{{4，5}}AD．∈A8．设A．M∩N9．设A-B=，则有（）A．B=10．A，B是集合，P（A），P（B）为其幂集，A．B．{}C．{{}}D．{，{}}11．设A={1，2，3，4，5}，B={6，7，8，9，10}，以下关系是从A到B的入射函数的是]A．f={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>}B．f={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>}C．f={<1,6>,<2,7>,<4,9>,<3,8>}D．f={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>}12．下面关于关系A．t(R)是包含R的二元关系B．t(R)是包含R的最小C．t(R)是包含R的一个传递关系D．t(R)是任何包含R的传递关系13.设A={l，2，3，4}，A上的二元关系R={<1，2>，<3，4>，<4，3>}，S={<l，3>，<3，4>，<4，1>}，则R的传递闭包t(R)的描述最确切的是（）传递关系R～S=________，f（n）=2n+1，g（n）=n2，那么复合函数（ff）（n）=________gf是从A到C的函数，如果gf是满射，那么________必是满射，如果gf是入射，那么________-16．设A={1，2}，B={2，3}，则A-A=________，A-B=________。AA=__________，AB=__________。R的自反闭包r(R)=_________，对称闭包S（R）=__________。gfx=__________，()()=__________。19．设20．设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},那么dom(A∪B)=_______,ran(A∩B)=__________。18．已知A={{}，{，1}}，B={{，1}，{1}}，计算A∪B，A○+B，A的幂集P（A）。21．设A={a,b,c,d}，R={<a，b>，<a，d>，<b，c>，<c，a>，<d，a>}，求R的传递闭包。22.设A={2，3，6，12，24，36}，请画出A上整除关系的哈斯图，并给出子集{6，12，24，36}的下界、下确界、极大）23．设A={1，2，3，4，6，8，12，24}，R为A上的整除关系，试画<A，R>的哈斯图，并求A中的最大元、最小元、24．若集合A={1，{2，3}}的幂集为P（A），集合B={{，2}，{2}}的幂集为P（B），求P(A)∩P(B)。25．X={1234}，R={<1,1>,<3,1>,<1,3>,<3,3>,<3,2>,<4,3>,<4,1>,<4,2>,<1,2>}。（1）画出R的关系图；（2）写出R的关系矩阵；（3）说明R是否具有自反、反自反、对称、传递性质。26．设A={a,b,c},P(A)是A的幂集，R为A上的包含关系，试给出<P(A),R>的哈斯图，并给出子集{{a,b},{a,c},{c}}的极大元、极小元、最大元、最小元。27．设R为N×N上的二元关系，对任意<a，b>,<c，d>∈N×N，<a，b>R<c，d>的充要条件是b=d，证明R为等价关系。28.设A={<a，b>|a，b∈Z+，Z+为整数集}，A上的关系R={<<a，b>,<c，d>>|ad=bc}，证明R是等价关系。）A上自反和传递的关系，试证明：RR=R。29．R是集合离散数学复习第四章代数系统一、典型考查要点：1、运算的2、运算性质的取元素，符合定义即可。在运算运算具有可交换性，当且仅当运算表关于主对角线是对称的。的每一元素与它所在行（列）的表头元素相同。详见P793、代数系统中特殊元：么元（单位元）、零元、逆元判断方法：根据定义，在所讨论的集中可。在运算表中可以判断：1）A中关于运算具有零元，当且仅当该元素所对应的行和列中的元素都与该元素相同。2）A中关于运算具有幺元，当且仅当该元素所对应的行和列依次与运算表的行和列相一致。3）设A中关于运算幺元，a和b互逆，当且仅当位于a所在行和b所在列的元素及b所在行和a所在列的元素都是幺元。详见P804、子判定：关键两个条件:BA,<B，判断：方法：运算满足封闭性，即运算后产生的象仍在同一个集合中。详见P77等、吸收、消去方法：根据定义，在所讨论的集中表中可以判断：1）运算具有当且仅当运算表中的每个元素都属于A。2）3）运算具有当且仅当运算表的主对角线上判断：运算性质：封闭、结合、交换、分配、幂任封闭性，等幂性，找到特殊元，符合定义即具有封闭广群结合半群么元独异点可逆群，根据定义，满足条件即可。详>中的特殊元（么元或零元）与<A，>中相同。详见P82代数的5、特殊代数系统判定：（G，）见P86/6、群的证明：方法：根据群的四个条件，逐一验证即可，注意：对于么元和逆元，先根据运算特点解出么元和逆元，>是群∧|G|＞1<G，⊙>是群<G，⊙>中的唯一等幂元是幺元。3、群>是群(a⊙b)-1=b-1⊙a-1满足消去律：b⊙a=c⊙ab=c4、给定群5、<G，⊙详见P878、子群及判定：三个判定定理根据已知条件选择，给定群⊙b∈H，a-1∈H2、<H，⊙>是<G，⊙>的子群(a)(b)(a，b∈H→a⊙b-1∈H)非空有限集9、特殊群的判断：1、阿贝尔群即满足交换律的群2、循环群即群中每个元都由某一个元的n次幂生成，这个元就是3、同余类整数加法，乘法，<Z，+m><Z，×m>构成群：[i]+m[j]=[(i+j)(modm)][i]×m[j]=[(i×j)(modm)]10、环、整环、1、<R，+，·>，若①<R，+>是Abel群，②<R，·>是半群，③·对于+是可分配的，则称<R，+，·>是环2、可交换<R，+，·>，且无零因子，则称<R，+，·>为整环。3、可交换环<R，+，·>，若<R-{0}，·>为群，则称<R，+，·>为域4、环、整环、立。详见P9311、格、子格、分配格、有1、格：即最小上界和最大下界。2、子格：子集，运算∨,∧封闭即可。3、分配格：含有五角格和钻石格为子图的都不是分配格，但链是分配格。4、有补格：每个元素都至少有一个补元素的有界格。求补元时，满足：a∨b=1(即全上界)，和a∧b=0(即全下界)详见P97>及非空1、<H，⊙>是<G，⊙>的子群aH则a⊙b∈H生成元。域之间的关系及判定：含幺环域之间的关系：域一定是整环，整环一定是环，反之不成补格的判定：<A,≤>偏集序中，任意两个元素都有,二、强化练习1.在整数集上，不是二元运算2.设A是奇数集合，×为乘法运算，则3.不满足结合律是)*b=min(a，b)*b=max(a，b)*b=2(a+b)*b=2ab4．在N上，可结合的是（）A．ab=a-2bB．ab=min{a，b}C．ab=-a-bD．ab=|a-b|5．整环和域是（）A整环一定是域B域不一定是整环C域一定是整环D域一定6．设集合A={1，2，3，……，10}，A上是不封闭的是（）A．x*y=max{x,y}B．x*y=min{x,y}C．x*y=GCD{x,y},即x,y的最大公约数D．x*y=LCM{x,y},即x,y的最小公倍数()A.加法B.减法C.乘法D.除法<A，×>是()A.半群B.群C.循环群D.交换群(不是整环7．设H，K是群（G，）的子群，下面代数系统是（G，）的子群的是（）！A．（H∩K，）B．（H∪K，）C．（K-H，）D．（H-K，）4．下列所示的哈斯图所对应的偏集序中能构成格的是（）A．8.代数系统<A，*，9.在实数集R上定义运算ab=a+b+ab，则幺元为________，元素2的逆元为________。10．设S是非空有限集，代数系统<P（S），∪>中，其中P（S）为集合S的幂集，则P（S）对∪运算的单位元是________，零元是________。11．在<Z6,○+>中，2的阶是________。12．设<A，≤>是格，其中A={1，2，3，4，6，8，12，24}，≤为整B．C．D．<A，*>是________，<A，>是整环，则>是________，且无零因子。除关系，则3的补元是________。《13．有理数集Q中的*运算定义如下：a*b=a+b-ab，则*运算的单位元是__________，设a有逆元，则其逆元a-1=__________。14．<Zn,>是一个群，Zn={0,1,2,……,n-1},xy=(x+y)modn，则在<Z6,>中，其中1的阶是__________，4的阶是__________。111101xxx0101。15．设H是形如的2×2阶矩阵的集合，H中定义通常的矩阵乘法运算。验证H是群，=abab2,a,bZ16．在整数集Z上定义：，证明：<Z，>是一个群。>的子代数。17．设H是G的有限子集，则<H，>是群<G，>的子群当且仅当<H，>是群<G，离散数学复习第五章图论一、典型考查要点1、图的基本概念：方法：度：点连接的边的条数，自环算2度；生成子图：点不减少，边减少；完全图：每个点都与余下的点有边；同构：两个图总可以画成相同的。详见P110·2、握手定3、路的两个定一条不多于n-1条边的vk而边数小于n的通路。详见P1154、连通图的1、无向连通图：走得通，有只一个连通分支。2、有向图中：强连通，弱连通，去掉方向后才连通；单侧连通，每对点，要只一个点可达另一点。3、强连件证明：一个有强连通的充分必要条件是G有一个回路，它至少包含每个次。详见P116-1175、边割集、点割集的割集：图中去掉这些点及关联的边后，恰好不连通。定G中的结点v是割点的充分必要条件是存在两个u和w，使得结点u和w的每一条过v。边割集：图中去掉这些边后，恰好不连通，连通分支变为2。定G的一条边e不包含在G的回路中当且仅当e是G的割边。详见P116-117理：结点度数总和等于边数的两倍，即deg(v)=2|E|，用于边点度n个结点的图中，如vj到vk存在一条n个结点的图中，vj到vk存在一条之间的计算。理及证明：1、在一个具有果从结点路，则从结点vj到vk存在路。推论：在一个具有若从结点路，则必存在一条从vj到判定及证明：任意两点都有路，即都任意两点都有路，即都走得通；通的充要条向图是结点一判定及证明：点理：一个连通无向图结点路都通理：1viviadjvaij0jnadjvorij6、邻接矩阵、可达矩阵的表示：邻接矩阵：j，表示图中点与点的关系，可以利用它的Ak来求长度为k的路的条数，即定理：设A为简单图G的邻接矩阵，则Ak中的i行j列元素akij等于G中联结vi到vj的长1路ij从v到v不存在路可以Pij0度为k的链(或路)的数详见P117-1187、欧拉图及应用：欧拉路：边遍行且只能一次的路，点可以G连通，且有零个或两个奇数度结点。欧拉回路存在当且仅当笔画问题，即有没有欧拉路。8、汉密尔顿图及应用：汉密尔顿路：点遍行且只能一次的路。件：若图有汉密尔顿回路，则V的每个非空子集S均有W(G-S)≤|S|，其中W(G-S)是G-S的连通分支数。可以用这个必要条件来判定有些图不是汉密尔顿图。2、充分条件：图G有n个点的简单图,如果每一对结点度数之和大于等于n-1,则G中存在一条汉密尔顿路。对结点度数之和大于等于n,则存在汉密尔顿回路。3、应用到网路连通、朋友开会排座位等，就是先利用题目中的联系，有关系就确定一条边，构造一个图，找一条汉密尔顿路或汉密尔顿回路即可。详见P1219、平面图的1、平面图：画在平面上，边不相交叉。判定：平面图不得森图都不是平面图。2、欧拉公式：n-m+r=2,计算边点面之间的关系问题。面的次数即围着这个面的边的条数，单独2次。必要条件：给定连通简单平面图G=<V，E，>。若|V|≥3，则e≤3v-6。详见P125利用它来判定连通性，全为1，就是连通的。目。可达矩阵：重复。欧拉回路：边遍行且只能一次的回路。判定：欧拉路存在当且仅当G连通，并且所有点度数都为偶数。应用到一汉密尔顿回路：点遍行且只能一次的回路。判定：1、必要条利若每一判定：含与K3,3,或K5同胚的子图。K3,3,K5及彼的边要算…10、树的6个等价定义：回路(5)连通，但删去任一边后就不连通详见P128(1)无回路的连通图(2)无回路且e=v-1(3)连通且e=v-1(4)无回路，但增加一边后得到且仅得一个(6)每一对结点间有且仅有一条通利用e=v-1和握手定理计算边点的数目。路。11、最小生成树：连通图中权之各最小的生成树，利用避圈法：