《离散数学复习要点.doc》由会员分享，可在线阅读，更多相关《离散数学复习要点.doc（9页珍藏版）》请在三一办公上搜索。
1、精选优质文档-倾情为你奉上离散数学复习要点 第一章命题逻辑一、典型考查点1、命题的判断 方法：陈述句 真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材P1 2、联结词运算定律 记住特殊的：111，000，1 00，111，001详见P5 3、命题符号化 步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用，只有P才Q，应为QP；除非P否则Q，应为PQ。 B设出原子命题写出符号化公式。详见P5 4、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P95、真值表的构造 步骤： 命题变元按字典序排
2、列，共有2n个真值赋值。 对每个指派，以二进制数从小到大或从大到小顺序列出。 若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。详见P8。6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P157、等价式 详见P22表1.6.2 证明方法：真值表完全相同 用等价演算 利用AB的充要条件是AB且BA。主要等价式：(1)双否定：AA。(2)交换律：ABBA，ABBA，ABBA。3)结合律：(AB)CA(BC)，(AB)CA(BC)，(AB)CA(BC)。(4) 分配律：A
3、(BC)(AB)(AC)，A(BC)(AB)(AC)。(5) 德摩根律：(AB)AB，(AB)AB。(6) 等幂律：AAA，AAA。(7) 同一律：ATA，AFA。(8) 零律：AFF，ATT。(9) 吸收律：A(AB)A，A(AB)A。(10) 互补律：AAF，(矛盾律)，AAT。(排中律)(11) 条件式转化律：ABAB，ABBA。(12) 双条件式转化律：AB(AB)(BA)(AB)(AB)8、蕴含式 详见P23表1.6.3 证明方法：前件真导后件真方法 后件假导前件假方法 真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。用定义，证AB，即证AB是永真式。9、范式求法 步
4、骤： 使用命题定律，消去公式中除、和以外公式中出现的所有联结词； 使用(P)P和德摩根律，将公式中出现的联结词都移到命题变元之前； 利用结合律、分配律等将公式化成析取范式或合取范式。10、主范式的求法 重点 步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如PPP。(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则PP（QQ)或PP（QQ)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现， 这样得到了给定公式的主析取（合取）范式。注意：主析取范式
5、与主合取范式之间的联系。例如：(PQ)Qm1m3M0M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。详见P1611、推理证明：重点 方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。重点规则（主要蕴含式）：(1) PQP化简(2) PQQ化简(3) PPQ附加(4) PPQ变形附加(5)QPQ变形附加(6) (PQ)P变形化简(7) (PQ)Q变形化简(8) P，(PQ)Q假言推理(9) Q，(PQ)P拒取式(10) P，(PQ)Q析取三段论(11) (PQ)，(QR)PR条件三段论(12) (PQ)，(QR)PR 双条件
6、三段论文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。详见P21二、强化练习1.命题的是( )A.走，看电影去B.x+y0C.空集是任意集合的真子集D.你明天能来吗?2.下列式子为重言式的是( )A.PPQ B.(PQ)(PQ) C. (P Q)D.(PQ) (PQ)3下列为两个命题变元P，Q的小项是（）APQ P B PQ C PQD PPQ4下列语句中是真命题的是（）A我正在说谎B严禁吸烟C如果1+2=3，那么雪是黑的D如果1+2=5，那雪是黑的5设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（）A P Q B P Q C（PQ）D（ P Q）6命题公式（
7、P（PQ）Q是（）A矛盾式B蕴含式C重言式D等价式7命题公式（PQ）R的成真指派是（）A000，001，110， B001，011，101，110，111 C全体指派 D无8设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）A PQBP Q CP QDP Q9下面联结词运算不可交换的是（）AB CD 10下列命题公式不是重言式的是（）AQ（PQ）B（PQ）P C（P Q）（ PQ）D（PQ）（ PQ）11.设命题变元为P，Q，R，则小项m100=_，大项M010=_。12.置换规则：在证明的任何步骤上，命题公式中的任何子命题公式都可以_，记为_规则。13.请用联结词，表示联
8、结词和联结词 ：_，_。14两个重言式的析取是_式，一个重言式与一个矛盾式的析取是_式。15命题公式（PQ） P的成真指派为_，成假指派为_。16.用等值演算求(PQ)R的主合取范式。17.列出(P(QR) (PQ)的真值表。19构造命题公式（PQ）P）R的真值表。20求下列公式的主合取范式和主析取范式：P（ P（Q（ QR）21构造命题公式（）P R的真值表。22求下列公式的主析取范式和主合取范式：（P（QR）（ P（ QR）。23.用推理方法证明：PQ，PR，QSRS。24构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵
9、去看电影时，小李也去。25构造下面推理的证明。只要A曾到过受害者房间并且11点以前没离开，A就犯了谋杀罪。A曾到过受害者房间。如果在11点以前离开，看门人会看见他。看门人没有看见他。所以A犯了谋杀罪。离散数学复习要点 第二章谓词逻辑一、典型考查点1、基本概念：个体词、个体域、谓词、特性谓词、辖域，详见P27；前束范式详见P36 2、谓词符号化 步骤：正确理解给定命题。必要时把命题改叙，使其中每个原子命题、原子命题之间的关系能明显表达出来。把每个原子命题分解成个体、谓词和量词；在全总论域讨论时，要给出特性谓词。找出恰当量词。应注意全称量词(x)后跟条件式，存在量词($x)后跟合取式。用恰当的联结
10、词把给定命题表示出来。详见P303、谓词公式类型的判定（永真式、永假式、可满足式） 方法：利用论域翻译成自然语言后进行判断。详见P344、自由变元与约束变元的判定 方法：按定义，关键是要看它在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)(BA(x)B(x)A(x)(e) ($x
11、)(A(x)B)($x)A(x)B (f) ($x)(A(x)B)($x)A(x)B (g) ($x)(A(x)B)(x)A(x)B (h) ($x)(BA(x)B($x)A(x)。(3) 量词分配律等价式：(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、蕴含式(a)(x)A(x)(x)B(x)(x)(A(x)B(x)(b) ($x)(A(x)B(x)($x)A(x)($x)B(x)(c) (x)(A(x)B(x)(x)A(x)(x)B(x)(d)
12、(x)(A(x)B(x)($x)A(x)($x)B(x)其中，A(x)和B(x)为含有x自由出现的任意公式。详见P356、前束范式 方法：把量词全部通过等值演算化到整个谓词公式的前面把量词前面的全部通过德摩根定律化到谓词公式的内部。详见P367、推理：方法：演绎（常用格式）、反证法、CP规则即附加前提等。对于命题逻辑中的所有规则都可用。特殊规则：(1)量词消去 (简称UI或US规则) (x)A(x)A(c) (x)A(x)A(y) ($x)A(x)A(c) 量词产生规则(简称EG或UG规则) A(c)($y)A(y) A(x)(y)A(y) 详见P38二、强化练习1.下列式子不是谓词合式公式的
13、是( )A.(x)(P(x)($x)(Q(x) A(x，y)B.(x)($y)P(x，y)C.(x)P(x)R(y)D.($x)P(x)Q(y，z)2.设个体域为实数集，特定元素a=0，函数f(x，y)=x-y，特定谓词F(x，y)为xy，下列公式真值为真的是( )A.(x)(y)F(x，f(f(x，y)，y)B.(x)(y)(F(f(x，y)，x)C.(x)(y)(z)(F(x，y)F(f(x，z)，f(y，z)D.(x)F(f(a，x)，a)3.对于公式(x)(y)P(x，y)Q(x，z)($x)P(x，y)，下列说法正确的是( )A.x是自由变元B.x是约束变元C.( x)的辖域是P(x
14、，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在公式（）F（x，y）（ y）G（x，y）中变元x是（）A自由变元B约束变元C既是自由变元，又是约束变元D既不是自由变元，又不是约束变元6下列等价式不正确的是（）ABCD7设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（）AB B（x）CD B(x)二、填空题8.一个公式，如果量词均在全式的_，其作用域延伸到整个公式的_，则该公式称为前束范式。9（x）（y）（P（x，y）Q
15、（y，z）xP（x，y）中x的辖域为_，x的辖域为_。10公式（）（F（x）G(y)）()(H(x)中的自由变元为_，约束变元为_。三、综合应用题11符号化下面命题，并构造推理证明：人是要死的，苏格拉底是人，所以苏格拉底是要死的。离散数学复习第三章集合与函数一、典型考查点1、基本概念判断：函数的入射、满射、双射及定理、复合运算，详见P72，73，75。幂集、差集、对称差、笛卡尔积，详见P46，47，43，49。全序关系，详见P68.。方法：理解概念即可，按定义的步骤计算。2、关系的相关概念判断：特殊关系：若R=，为空关系；若R=AB，为全域关系。R=|xA为A上的恒等关系，记为IA。方法：根据
16、定义判断。定义域: 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上关系自反性反自反性对称性反对称性传递性定义x xAxRxxARxRyyRxxRyR 除x =yxRyyRzxRz矩阵特征主对角线全为1主对角线全为0沿对角线对称沿主对角线不对称图特征每个顶
17、点都有环每顶点都没有环有边则双向边若有边，则是单向边集合特征IA RIA R=R-1=RIA R IA4、关系的运算：关系的集合运算，按集合的运算规律即可：交、并、补、差、对称差等。复合运算：按顺序运算，逆运算，交换每个元的第一、二位元素的位置即变。闭包运算：即先判断R本身是否具有自反（对称、传递），若有，则自反（对称、传递）闭包就是R本身，即r(R)=R(或s(R)=R,t(R)=R),若没有，则增加R的元素，加到恰好满足自反性为止，既不能多，也不少。详见P555、等价关系和划分的判断及证明：等价关系的证明：自反、对称、传递三个性质逐一验证。要注意给出的等价关系的条件的变通。等价关系与划分一
18、一对应，等价关系的等价类即为确定的划分的分块，即有关系的，划在同一块。划分中凡在同一个分块中的元，都写成满足关系的元，这样写出的关系R就是一个等价关系。6、相容关系和覆盖的判断：相容关系两个性质：自反和对称，注意：相容关系图的画法省略了自反和对称。覆盖按定义判断即可。详见P617、偏序关系与哈斯图：基本概念：三个性质：自反、反对称和传递；可比，就是有关系，abba；盖住，就是直接关系，中间没有第三个元，即若ab且不存在cA，使得acb。偏序关系与哈斯图：画图注意四点：使用盖住的联系来表示，省略全部向上的箭头，省略自反性的自环，省略了传递性。反之，由哈斯图写偏序关系也要注意这四点，除了直接的盖住
19、关系外，还有自反和传递也要写出来。8、求偏序关系的特殊元：设为偏序集，BA，bB， 若(x)(xBbx)为真，则称b为B的最小元。 若(x)(xBxb)为真，则称b为B的最大元。 若($x)(bxxb)为真，则称b为B的极小元。 若($x)(bxbx)为真，则称b为B的极大元。根据定义判断时，最小（大）元与极小（大）元是有区别的，最小（大）元是B中最小（大）的元素，它与B中其他元素都可比；而极小（大）元不一定与B中元素都可比，只要没有比它小（大）的元素，它就是极小（大）元。对于有穷集B，极小（大）元一定存在，且可能有多个，但最小（大）元不一定存在，若存在则必唯一。若B中只有一个极小（大）元，则
20、它一定是B的最小（大）元。详见P689、求上界下界上确界和下确界：设为偏序集，BA，bA， 若(x)(xBbx)为真，则称b为B的下界。 若(x)(xBxb)为真，则称b为B的上界。 若b是一下界且对每一个B的下界b有bb，则称b为B的最大下界或下确界，记为glb。 若b是一上界且对每一个B的上界b有bb，则称b为B的最小上界或上确界，记为lub。判断时注意，上界下界上确界和下确界是A集合上来找的，B的上界，下界，最小上界，最大下界都可能不存在。若存在，最小上界和最大下界是唯一的。详见P69二、强化练习1.设Z+是正整数集，f：Z+Z+Z+，f(n，m)=nm，则f( ) A.仅是入射B.仅是
21、满射C.是双射D.不是函数 2.关系矩阵所对应的关系具有自反性( )A. B.C. D.3.设R1和R2是集合A上的相容关系，不是相容关系( ) A.R1R2 B.RlR2 C.R1-1 D.RlR24集合A=1，2，10上的关系R=|x+y=10，xA，yA，则R的性质是（）A自反的B对称的C传递的、对称的D反自反的、传递的5若R和S是集合A上的两个关系，则下述结论正确的是（）A若R和S是自反的，则RS是自反的B若R和S是对称的，则RS是对称的C若R和S是反对称的，则RS是反对称的D若R和S是传递的，则RS是传递的6R=，则下列不是t（R）中元素的是（）ABCD7设A=1，2，3，4，5，6
22、，7，8，下列选项正确的是（）A1A B1，2，3A C4，5ADA8设M=x|f1(x)=0,N=x|f2(x)=0，则方程f1(x)f2(x)=0的解为（）AMNBMNCMNDM-N9设A-B=，则有（）AB=BB CAB DAB10A，B是集合，P（A），P（B）为其幂集，且AB=，则P(A)P(B)为（）AB CD，11设A=1，2，3，4，5，B=6，7，8，9，10，以下关系是从A到B的入射函数的是Af =,Bf =,Cf =,Df =,12下面关于关系R的传递闭包t(R)的描述最确切的是（）At(R)是包含R的二元关系Bt(R)是包含R的最小传递关系Ct(R)是包含R的一个传递关
23、系Dt(R)是任何包含R的传递关系13.设A=l，2，3，4，A上的二元关系R=，S=，则RS=_，(RS)-1=_。14设N是自然数集合，f和g是N到N的函数，且f（n）=2n+1，g（n）=n2，那么复合函数（ff）（n）=_（gf）（n）=_。15设复合函数gf是从A到C的函数，如果gf是满射，那么_必是满射，如果gf是入射，那么_必是入射。16设A=1，2，B=2，3，则A-A=_，A-B=_。17设A=1，2，B=2，3，则AA=_，AB=_。18设A=1，2，3，4上关系R=,，则R的自反闭包r(R)= _，对称闭包S（R）=_。19设f :RR,f (x)=x2-2,g :RR,
24、g(x)=x-1,那么复合函数=_，=_。20设A=,B=,那么dom(AB)=_,ran(AB)= _。18已知A=，1，B=，1，1，计算AB，AB，A的幂集P（A）。21设A=a,b,c,d，R=，求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中的最大元、最小元、极大元、极小元。24若集合A=1，2，3的幂集为P（A），集合B=，2，2的幂集为P（B），求P(A)P(B)。25 X=1 2 3 4，R=
25、,。（1）画出R的关系图；（2）写出R的关系矩阵；（3）说明R是否具有自反、反自反、对称、传递性质。26设A=a,b,c,P(A)是A的幂集，R为A上的包含关系，试给出的哈斯图，并给出子集a,b,a,c,c的极大元、极小元、最大元、最小元。27设R为NN上的二元关系，对任意,NN， R 的充要条件是b=d，证明R为等价关系。28.设A=|a，bZ+，Z+为整数集，A上的关系R=,|ad=bc，证明R是等价关系。29R是集合A上自反和传递的关系，试证明：RR=R。离散数学复习第四章代数系统一、典型考查要点：1、运算的判断：方法：运算满足封闭性，即运算后产生的象仍在同一个集合中。详见P772、运算
26、性质的判断：运算性质：封闭、结合、交换、分配、幂等、吸收、消去 方法：根据定义，在所讨论的集中任取元素，符合定义即可。在运算表中可以判断：1）运算*具有封闭性，当且仅当运算表中的每个元素都属于A。2）运算*具有可交换性，当且仅当运算表关于主对角线是对称的。3）运算*具有等幂性，当且仅当运算表的主对角线上的每一元素与它所在行（列）的表头元素相同。详见P793、代数系统中特殊元：么元（单位元）、零元、逆元 判断方法：根据定义，在所讨论的集中找到特殊元，符合定义即可。在运算表中可以判断：1）A中关于运算*具有零元，当且仅当该元素所对应的行和列中的元素都与该元素相同。2）A中关于运算*具有幺元，当且仅
27、当该元素所对应的行和列依次与运算表的行和列相一致。3）设A中关于运算*具有幺元，a和b互逆，当且仅当位于a所在行和b所在列的元素及b所在行和a 所在列的元素都是幺元。详见P804、子代数的判定：关键两个条件:BA, 中的特殊元（么元或零元）与中相同。详见P825、特殊代数系统判定：（G，）封闭广群 结合半群 么元独异点 可逆群，根据定义，满足条件即可。详见P866、群的证明：方法：根据群的四个条件，逐一验证即可，注意：对于么元和逆元，先根据运算特点解出么元和逆元，再验证。详见P867、群的性质：1、是群|G|1无零元。2、G，是群中的唯一等幂元是幺元。3、群满足消去律：ba=cab=c 4、给
28、定群，则ax=b群中方程解是唯一的。5、是群 (ab)-1=b-1a-1 详见P878、子群及判定：三个判定定理根据已知条件选择，给定群及非空HG，则1、是的子群abH， a-1H 2、是的子群(a)(b)(a，bHab-1H)非空有限集H则abH9、特殊群的判断：1、阿贝尔群即满足交换律的群 2、循环群即群中每个元都由某一个元的n次幂生成，这个元就是生成元。3、 同余类整数加法，乘法，构成群：i +mj=(i+j)(mod m) imj=(ij)(mod m)10、环、整环、域之间的关系及判定：1、，若是Abel群，是半群，对于+是可分配的，则称是环2、可交换含幺环，且无零因子，则称为整环。
29、3、可交换环，若为群，则称为域4、环、整环、域之间的关系：域一定是整环，整环一定是环，反之不成立。详见P9311、格、子格、分配格、有补格的判定：1、格：即偏序集中，任意两个元素都有最小上界和最大下界。2、子格：子集，运算,封闭即可。3、分配格：含有五角格和钻石格为子图的都不是分配格，但链是分配格。4、有补格：每个元素都至少有一个补元素的有界格。求补元时，满足：ab=1(即全上界)，和ab=0(即全下界) 详见P97二、强化练习1.在整数集上，不是二元运算( )A.加法 B.减法 C.乘法D.除法2.设A是奇数集合，为乘法运算，则是( )A.半群 B.群 C.循环群D.交换群3.不满足结合律是
30、( )A.a*b=min(a，b) B.a*b=max(a，b)C.a*b=2(a+b)D.a*b=2ab4在N上，可结合的是（ ）Aab=a-2b Bab=mina，b Cab=-a-b Dab=|a-b|5整环和域是（ ）A整环一定是域B域不一定是整环C域一定是整环D域一定不是整环6设集合A=1，2，3，10， A上是不封闭的是（）Ax*y=maxx,yBx*y=minx,yCx*y=GCDx,y,即x,y的最大公约数 Dx*y=LCMx,y,即x,y的最小公倍数7设H，K是群（G，）的子群，下面代数系统是（G，）的子群的是（）A（HK，）B（HK，）C（K-H，）D（H-K，）4下列所示
31、的哈斯图所对应的偏序集中能构成格的是（）A BCD8.代数系统是整环，则是_，是_，且无零因子。9.在实数集R上定义运算ab=a+b+ab，则幺元为_，元素2的逆元为_。10设S是非空有限集，代数系统中，其中P（S）为集合S的幂集，则P（S）对运算的单位元是_，零元是_。11在中，2的阶是_。12设是格，其中A=1，2，3，4，6，8，12，24，为整除关系，则3的补元是_。13有理数集Q中的*运算定义如下：a*b=a+b-ab，则*运算的单位元是_，设a有逆元，则其逆元a-1=_。14是一个群，其中Zn=0,1,2,n-1,xy=(x+y)mod n，则在中，1的阶是_，4的阶是_。15设H
32、是形如的22阶矩阵的集合，H中定义通常的矩阵乘法运算。验证H是群，=。16在整数集Z上定义：，证明：是一个群。17设H是G的有限子集，则是群的子群当且仅当是群的子代数。离散数学复习第五章图论一、典型考查要点1、图的基本概念：方法：度：点连接的边的条数，自环算2度；生成子图：点不减少，边减少；完全图：每个点都与余下的点有边；同构：两个图总可以画成相同的。详见P1102、握手定理：结点度数总和等于边数的两倍，即deg(v)=2|E|，用于边点度之间的计算。3、路的两个定理及证明： 1、在一个具有n个结点的图中，如果从结点vj到vk存在一条路，则从结点vj到vk存在一条不多于n-1条边的路。推论：在
33、一个具有n个结点的图中，若从结点vj到vk存在一条路，则必存在一条从vj到vk而边数小于n的通路。详见P1154、连通图的判定及证明：1、无向连通图：任意两点都有路，即都走得通，只有一个连通分支。2、有向图中：强连通，任意两点都有路，即都走得通；弱连通，去掉方向后才连通；单侧连通， 每对点，只要一个点可达另一点。3、强连通的充要条件证明：一个有向图是强连通的充分必要条件是G有一个回路，它至少包含每个结点一次。详见P116-1175、边割集、点割集的判定及证明：点割集：图中去掉这些点及关联的边后，恰好不连通。定理：一个连通无向图G中的结点v是割点的充分必要条件是存在两个结点u和w，使得结点u和w
34、的每一条路都通过v。 边割集：图中去掉这些边后，恰好不连通，连通分支变为2。定理：G的一条边e不包含在G的回路中当且仅当e是G的割边。详见P116-1176、邻接矩阵、可达矩阵的表示：邻接矩阵：，表示图中点与点的关系，可以利用它的Ak来求长度为k的路的条数，即定理：设A为简单图G的邻接矩阵，则Ak中的i行j列元素akij等于G中联结vi到vj的长度为k的链(或路)的数目。可达矩阵：可以利用它来判定连通性，全为1，就是连通的。详见P117-1187、欧拉图及应用：欧拉路：边遍行且只能一次的路，点可以重复。欧拉回路：边遍行且只能一次的回路。判定：欧拉路存在当且仅当G连通，且有零个或两个奇数度结点。
35、欧拉回路存在当且仅当G连通，并且所有点度数都为偶数。应用到一笔画问题，即有没有欧拉路。8、汉密尔顿图及应用：汉密尔顿路：点遍行且只能一次的路。汉密尔顿回路：点遍行且只能一次的回路。判定：1、必要条件：若图有汉密尔顿回路，则V的每个非空子集S均有W(G-S)|S|，其中W(G-S)是G-S的连通分支数。可以利用这个必要条件来判定有些图不是汉密尔顿图。2、充分条件：图G有n个点的简单图,如果每一对结点度数之和大于等于n-1,则G中存在一条汉密尔顿路。若每一对结点度数之和大于等于n,则存在汉密尔顿回路。3、应用到网路连通、朋友开会排座位等，就是先利用题目中的联系，有关系就确定一条边，构造一个图，找一
36、条汉密尔顿路或汉密尔顿回路即可。详见P1219、平面图的判定：1、平面图：画在平面上，边不相交叉。判定：平面图不含与K3,3,或K5同胚的子图。K3,3,K5及彼得森图都不是平面图。2、欧拉公式：n-m+r=2,计算边点面之间的关系问题。面的次数即围着这个面的边的条数，单独的边要算2次。必要条件：给定连通简单平面图G=。若|V|3，则e3v-6。详见P12510、树的6个等价定义：(1)无回路的连通图(2)无回路且e=v-1 (3)连通且e=v-1(4)无回路，但增加一边后得到且仅得一个回路(5)连通，但删去任一边后就不连通(6)每一对结点间有且仅有一条通路。利用e=v-1和握手定理计算边点的
37、数目。详见P12811、最小生成树：连通图中权之各最小的生成树，利用避圈法：边的权由小到大依次画入生成树中，但不能形成回路，若有回路就不画入，这样直到形成生成树为止，最小生成树不唯一。应用在网络连通上，造价最少的问题中。详见P12912、M叉树详见P120，根树表示算式：根据算式运算的顺序，由内向外形成根树。详见P131二、强化练习13.13图的最小入度是( )A.0 B.1 C.2 D.32.下面既是汉密尔顿图又是欧拉图的图形是( )3.树有3个5度点、1个4度点、3个2度点，其它的都是1度，边是( ) A.17 B.18 C.19 D.205G是 n个结点的简单图，有（）A(G)nB(G)
38、nC(G)nD(G)n6具有4个结点的非同构的无向树的数目是（）A2B3 C4D57简单图G所有结点的度数之和为12，则G边一定有（）A3 B4 C5 D68下列不一定是树的是（）A无回路的连通图B有n个结点，n-1条边的连通图C每对结点之间都有通路的图D连通但删去一条边则不连通的图9欧拉回路是（）A路径B迹C既是初级回路也是迹D既非初级回路也非迹10.若回路中，除_外_各不相同，则此回路称为圈(或初级回路)。11.偶图记为Kn,m那么当_时，Kn,m是平面图，当_时，Kn,m是非平面图。12.若图中存在_，它经过图中所有的边恰好_次，则称该图为欧拉图。13在24图中，结点v2的度数是_。25
39、设图D=，V=v1，v2，v3，v4，若D的邻接矩阵A=，则deg-（v1）=_，从v2到v4长度为2的路有_条。14如14图的有补格中，c的补元是_，b的补元是_。15在根树中，若每一个结点的出度_m,则称这棵树为m叉树。如果每一个结点的出度_m或0，则称这棵树为完全m叉树。16简单图G有n个结点，m条边，设m(n-1)(n-2)，证明：G是连通的。17.求30图所示格的所有5元子格。18.用矩阵的方法求31图中结点u2，u5之间长为2的路径的数目。1928给出了一个有向图。（1）求出它的邻接矩阵A；（2）求出A2，A3，A4及可达矩阵P。20证明：一个图是强连通的，当且仅当图中有一个回路，它至少包含每个结点一次。21证明：边e是图G的一条割边，当且仅当图G中不存在包含边e的简单回路。22今有n个人，已知他们中任何2人的朋友合起来一定包含其余n-2人。试证明：（1）当n3时，这n个人能排成一列，使得中间任何人是其两旁的人的朋友，而两头的人是其左边（或右边）的人的朋友。（2）当n4时，这n个人能排成一圆圈，使得每个人是其两旁的人的朋友。23在某次国际会议的预备会中，共有8人参加，他们来自不同的国家。已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。专心-专注-专业
