离散数学大作业.doc

离散数学大作业 班级：15计算机2班 学号：20150200224 姓名：王鹏 时间：2017.6.317第一章 命题逻辑1.1命题及其表示法 命题的概念: 数理逻辑将能够判断真假的陈述句称作命题。1.2命题联结词1. 否定联结词P 与原命题相反2. 合取联结词 同时为真，才为真3. 析取联结词 同时为假，才为假4. 蕴涵联结词 当且仅当p为真，q为假5. 等价联结词 同时为真，或同时为假才为真1.3 命题公式、翻译与解释1. 命题公式定义 命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P是公式，则P是公式；（3）如果P、Q是公式，则PQ、PQ、PQ、 PQ都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。2. 命题的翻译 可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。 命题翻译时应注意下列事项：（1）确定所给句子是否为命题。（2）句子中联结词是否为命题联结词。（3）要正确的选择原子命题和合适的命题联结词。1.4 真值表与等价公式1. 真值表定义 将公式G在其所有解释下所取得的真值列成一个表，称为G的真值表。构造真值表的方法如下：（1）找出公式G中的全部命题变元，并按一定的顺序排列成P1，P2，Pn。 （2）列出G的2n个解释，赋值从000（n个）开始，按二进制递加顺序依次写出各赋值，直到111为止（或从111开始，按二进制递减顺序写出各赋值，直到000为止），然后从低到高的顺序列出G的层次。（3）根据赋值依次计算各层次的真值并最终计算出G的真值成真赋值+成假赋值=2n2. 命题公式的分类 定义 设G为公式：（1）如果G在所有解释下取值均为真，则称G是永真式或重言式； （2）如果G在所有解释下取值均为假，则称G是永假式或矛盾式； （3）如果至少存在一种解释使公式G取值为真，则称G是可满足式。3. 等价公式 定义 设A和B是两个命题公式，如果A和B在任意赋值情况下都具有相同的真值，则称A和B是等价公式。记为AB。性质定理设A、B、C是公式，则（1）AA（2）若AB则BA（3）若AB且BC则AC定理 设A、B、C是公式，则下述等价公式成立：（1）双重否定律 AA（2）等幂律 AAA ； AAA（3）交换律 ABBA ； ABBA（4）结合律 （AB）CA（BC）（AB）CA（BC）（5）分配律 （AB）C（AC）（BC）（AB）C（AC）（BC）（6）德摩根律 （AB）AB（AB）AB（7）吸收律 A（AB）A；A（AB）A（8）零一律 A11 ； A00（9）同一律 A0A ； A1A（10）排中律 AA1（11）矛盾律 AA0（12）蕴涵等值式 ABAB（13）假言易位 ABBA（14）等价等值式 AB（AB）（BA）（15）等价否定等值式 ABABBA（16）归缪式 （AB）（AB）A4. 置换规则 定理（置换规则） 设（A）是一个含有子公式A的命题公式，（B）是用公式B置换了（A）中的子公式A后得到的公式，如果AB，那么（A）（B）。1.5 对偶与范式1. 对偶定义 在仅含有联结词、的命题公式A中，将联结词换成，将换成，如果A中含有特殊变元0或1，就将0换成1，1换成0，所得的命题公式A*称为A的对偶式。例：公式（PQ）（PQ） 的对偶式为：（PQ）（PQ）定理 设A和A*互为对偶式，P1，P2，Pn是出现在A和A*中的所有原子变元，若将A和A*写成n元函数形式，则（1）A（P1，P2，Pn）A*（P1，P2，Pn）（2）A（P1，P2，Pn）A*（P1，P2，Pn） 定理（对偶原理）设A、B是两个命题公式，若AB，则A*B*，其中A*、B*分别为A、B的对偶式。2. 范式定义 仅由有限个命题变元及其否定构成的析取式称为简单析取式，仅由有限个命题变元及其否定构成的合取式称为简单合取式。定义 仅由有限个简单合取式构成的析取式称为析取范式。仅由有限个简单析取式构成的合取式称为合取范式。定理（范式存在定理）任何命题公式都存在着与之等价的析取范式和合取范式。3. 主范式定义 设G为公式，P1，P2，Pn为G中的所有命题变元，若G的析取范式中每一个合取项都是P1，P2，Pn的一个极小项，则称该析取范式为G的主析取范式。矛盾式的主析取范式为0。定理 任意的命题公式都存在一个唯一的与之等价的主析取范式。 定义 设G为公式，P1，P2，Pn为G中的所有命题变元，若G的合取范式中每一个析取项都是P1，P2，Pn的一个极大项，则称该合取范式为G的主合取范式。通常，主合取范式用表示。重言式的主合取范式中不含任何极大项，用1表示。 定理 任意的命题公式都存在一个唯一的与之等价的主合取范式。1.6 公式的蕴涵1. 蕴涵的概念定义 设G、H是两个公式，若GH是永真式，则称G蕴涵H，记作GH。蕴涵关系有如下性质：（1） 对于任意公式G，有GG；（2）（2）对任意公式G、H，若GH且HG，则GH；（3） 若GH且HL，则GL。2. 基本蕴涵式（1）PQP； （2）PQQ；（3）PPQ； (4) QPQ；（5）P（PQ）； （6）Q（PQ）；（7）（PQ）P； （8）（PQ）Q；（9）P，PQQ； （10）Q，PQP；（11）P，PQQ； （12）PQ，QRPR；（13）PQ，PR，QRR； （14）PQ，RS（PR）（QS）；（15）P，QPQ。1.7 其它联结词与最小联结词组1. 其它联结词定义 设P、Q为命题公式，则复合命题P Q称为P和Q的不可兼析取，当且仅当P与Q的真值不相同时，PQ的真值为1，否则PQ的真值为假。定义 设P、Q是两个命题公式，复合命题P Q称为命题P、Q的条件否定，当且仅当P的真值为1，Q的真值为0时，P Q的真值为1，否则 PQ的真值为0。2. 最小联结词组定义 设S是一些联结词组成的非空集合，如果任何的命题公式都可以用仅包含S中的联结词的公式表示，则称S是联结词的全功能集。特别的，若S是联结词的全功能集且S的任何真子集都不是全功能集，则称S是最小全功能集，又称最小联结词组。 定理 ，是联结词的全功能集。 定理 ，是联结词的全功能集。定理 ，、，是最小联结词组。 定理 ，是最小联结词组。1.8 命题逻辑推理理论1.8.1 命题逻辑推理理论定义 如果G1，G2，Gn蕴涵H，则称H能够由G1，G2，Gn有效推出，G1，G2，Gn称为H的前提，H称为G1，G2，Gn的有效结论。称（G1G2Gn）H是由前提G1，G2，Gn推结论H的推理的形式结构。2. 推理规则下面给出推理中常用的推理规则。1 前提引入规则：可以在证明的任何时候引入前提；2 结论引入规则：在证明的任何时候，已证明的结论都可以作为后续证明的前提；3 置换规则：在证明的任何时候，命题公式中的任何子命题公式都可以用与之等价的命题公式置换。4 假言推理规则：P，PQQ5 附加规则：PPQ；6 化简规则：P，QP；7 拒取式规则： Q，PQP；8 假言三段论规则：PQ，QRPR；9 析取三段论规则：P，PQQ；10.构造性二难规则：PQ，PR，QRR；11.合取引入规则：P，QPQ3. 推理常用方法1.直接证法 直接证法就是根据一组前提，利用前面提供的一些推理规则，根据已知的等价公式和蕴涵式，推演得到有效的结论的方法，即有前提直接推导出结论。 2间接证法 间接证法主要有如下两种情况。 （1）附加前提证明法 有时要证明的结论以蕴涵式的形式出现，即推理的形式结构为：（G1G2Gn）（RC）设（G1G2Gn）为S，则上述推理可表示为证明S（RC），即证明S（RC）为永真式。 用附加前提证明法证明下面推理。前提：P（QR），SP，Q 结论：SR证明：（1）SP 前提引入规则 （2）S 附加前提引入规则 （3）P （1）（2）析取三段论规则 （4）P（QR） 前提引入规则 （5）QR （3）（4）假言推理规则 （6）Q 前提引入规则 （7）R （5）（6）假言推理规则2）归缪法定义 设G1，G2，Gn是n个命题公式，如果G1G2Gn是可满足式，则称G1，G2，Gn是相容的。否则（即G1G2Gn是矛盾式）称G1，G2，Gn是不相容的。例 用归缪法证明。前提：PQ，PR，QS 结论：SR证明（1）（SR） 附加前提引入规则 （2）SR （1）置换规则 （3）S （2）化简规则 （4）R （2）化简规则 （5）QS 前提引入规则 （6）QS （5）置换规则 （7）Q （3）（6）析取三段论 （8）PQ 前提引入规则 （9）P （7）（8）析取三段论规则 （10）PR 前提引入规则 （11）PR （10）置换规则 （12）R （9）（11）析取三段论规则 （13）RR （4）（12）合取引入规则第二章 谓词逻辑第三章2.1 谓词逻辑命题的符号化 1个体词 ：个体词是指研究对象中不依赖于人的主观而独立存在的具体的或抽象的客观实体 个体常项或个体常元 ： 个体变项或个体变元 ： 个体域或论域 ： 2谓词：用来刻画个体词的性质或个体词之间关系的词 一般来说，“x是A”类型的命题可以用A（x）表达。对于“x大于y”这种两个个体之间关系的命题，可表达为B（x，y），这里B表示“大于”谓词。我们把A（x）称为一元谓词,B（x，y）称为二元谓词，M（a，b，c）称为三元谓词，依次类推，通常把二元以上谓词称作多元谓词。 2.2 谓词逻辑公式与解释1. 谓词逻辑的合式公式 定义2.1 设P（x1，x2，xn）是n元谓词公式，其中，x1x2，xn是个体变项，则称P（x1，x2，xn）为谓词演算的原子公式。 定义2.2 谓词演算的合式公式定义如下：（1）原子公式是合式公式；（2）若A是合式公式，则（A）也是合式公式；（3）若A，B是合式公式，则（AB）、（AB）、（AB）、（AB）是合式公式；（4）若A是合式公式，则x A、x A是合式公式；（5）只有有限次地应用（1）（4）构成的符号串才是合式公式。 2. 约束变元与自由变元 1约束变元与自由变元的概念定义 2.3 在公式x F（x）和x F（x）中，称x为指导变元，F（x ）为相应量词的辖域或作用域。在x和x的辖域中，x的所有出现都称为约束出现，F（x）中不是约束出现的其他变元均称为自由出现。 2约束变元的换名与自由变元的代入 自由变元的代入规则是：（1）对于谓词公式中的自由变元，可以代入，此时需要对公式中出现该自由变元的每一处进行代入。（2）用以代入的变元与原公式中所有变元的名称都不能相同。2.2.3 谓词逻辑公式的解释 定义2.4 谓词逻辑公式的一个解释I，是由非空区域D和对G中常项符号、函数符号、谓词符号以下列规则进行的一组指定组成：（1）对每一个常项符号指定D中一个元素。（2）对每一个n元函数符号，指定一个函数。（3）对每一个n元谓词符号，指定一个谓词。显然，对任意公式G，如果给定G的一个解释I，则G在I的解释下有一个真值，记作TI（G）。 定义2.5 若存在解释I，使得G在解释I下取值为真，则称公式G为可满足的，简称I满足G。定义2.6 若不存在解释I，使得I满足G，则称公式G为永假式（或矛盾式）。若G的所有解释I都满足G，则称公式G为永真式（或重言式）。2.3 谓词逻辑约束公式的等价与蕴涵3. 谓词逻辑的等价公式 定义2.7 设A、B是命题逻辑中的任意两个公式，设它们有共同的个体域E，若对任意的解释I都有TI（A）= TI（B），则称公式A、B在E上是等价的，记作AB。 定理1 设A（x）是谓词公式，有关量词否定的两个等价公式：（1）x A（x）xA（x）（2）x A（x）xA（x）定理2 设A（x）是任意的含自由出现个体变项x的公式，B是不含x出现的公式，则有（1）x（A（x）B）x A（x）B（2）x（A（x）B）x A（x）B（3）x（A（x） B）x A（x） B（4）x（BA（x）B x A（x）（5）x（A（x）B） x A（x）B（6）x（A（x）B）x A（x）B（7）x（A（x） B）x A（x） B（8）x（BA（x）Bx A（x） 定理3 设A（x）、B（x）是任意包含自由出现个体变元x的公式,则有：（1）x（A（x）B（x）x A（x）x B（x）（2）x（A（x）B（x）x A（x）x B（x） x（A（x）B（x）x A（x）x B（x） 2.3.2 谓词逻辑的蕴涵公式 定义2.8 设A、B是命题逻辑中的任意两个公式，若AB是永真式，则称公式A蕴涵公式B，记作AB。 定理4 下列蕴涵式成立（1）x A（x）x B（x）x（A（x）B（x）（2）x（A（x）B（x）x A（x）x B（x）（3）x（A（x） B（x）x A（x） x B（x）（4）x（A（x） B（x）x A（x） x B（x）（5）x A（x） x B（x）x（A（x） B（x）3. 多个量词的使用 定义2.9 设谓词公式G，不包含联结词，。把G中出现的联结词，互换；命题常量T，F互换；量词，互换之后得到的公式称为G的对偶公式，记作G*。 定理5（对偶定理） 设A、B是任意两个公式并且不包含联结词，。若AB，则A*B*。2.4 前束范式 定义2.10 一个谓词公式，如果量词均在全式的开头，且辖域延伸到公式的末尾，则该公式称为前束范式。 定理6 对任意一个谓词公式都可以化为与它等价的前束范式。 定义2.11 若一个谓词公式，具有如下形式，则称该公式为前束析取范式。 定义2.12 若一个谓词公式，具有如下形式，则称该公式为前束合取范式。 定理7 任意谓词公式都可以化为与其等价的前束析取范式和前束合取范式。2.5 谓词演算的推理理论 1全称指定规则（简称US规则） 这条规则有下面两种形式：(1)x P（x）P（y）(2)x P（x）P（c）其中，P是谓词，（1）中y为任意不在P（x）中约束出现的个体变元；（2）中c为个体域中的任意一个个体常元。 2存在指定规则（简称ES规则） x P（x）P（c）其中，c为个体域中使P成立的特定个体常元。必须注意，应用存在指定规则，其指定的个体c不是任意的。 3全称推广规则（简称UG规则） P（y）x P（x） 4存在推广规则（简称EG规则）P（c）x P（x）其中，c为个体域中的个体常元，这个规则比较明显，对于某些个体c，若P（c）成立，则个体域中必有x P（x）。第三章 集合论3.1集合的概念与表示 集合的表示 ：1列举法2描述法 3.文氏图法 3.2 集合之间的关系定义3.1 如果集合A中的每一个元素都是集合B中的元素，则称A是B的子集，也可以说A包含于B，或者B包含A，这种关系写作AB 或 BA,如果A不是B的子集，即在A中至少有一个元素不属于B时，称B不包含A，记作BA 或 AB定义3.2 如果两个集合A和B的元素完全相同，则称这两个集合相等，记作AB。定理3.1 集合A和集合B相等的充分必要条件是AB且BA。 定义3.3 如果集合A是集合B的子集，但A和B不相等，也就是说在B中至少有一个元素不属于A，则称A是B的真子集，记作AB 或 BA 定义3.4 若集合U包含我们所讨论的每一个集合，则称U是所讨论问题的完全集，简称全集。 定义3.5 设A是有限集，由A的所有子集作为元素而构成的集合称为A的幂集，记作(A)，即(A)X|XA。在A的所有子集中，A和这两个子集又叫平凡子集。 定理3.2 设A是有限集，|A|=n，则A的幂集(A)的基为2。3.3 集合的运算3.3.1 集合的并运算定义3.6 任意两个集合A、B的并，记作AB，它也是一个集合，由所有属于A或者属于B的元素合并在一起而构成的，即ABx | xA或xB 用文氏图表示集合之间的并运算：用平面上的矩形表示全集U。用矩形内的圆表示U中的任一集合。图中表示了集合A和集合B的并集。阴影部分就是AB。 由集合并运算的定义可知，并运算具有以下性质：（1）幂等律：AAA （2）同一律：AA（3）零律：AUU （4）结合律：(AB)CA(BC)（5）交换律：ABBA 3.3.2 集合的交运算定义3.7 任意两个集合A、B的交记作AB，它也是一个集合，由所有既属于A又属于B的元素构成，即AB x | xA且xB 集合的交运算的文氏图表示，见图，其中阴影部分就是AB。 由集合交运算的定义可知，交运算有以下性质：（1）幂等律：AAA（2）同一律：AUA（3）零律：A（4）结合律：(AB)CA(BC)（5）交换律：ABBA定理3.3 设A，B，C是三个集合，则下列分配律成立：A（BC）（AB）（AC）A（BC）（AB）（AC） 定理3.4 设A，B为两个集合，则下列关系式成立：A（AB）A A（AB）A这个定理称为吸收律，可以用文氏图验证 3.3.3 集合的补 定义3.8 设A、B是两个集合，A-B也是一个集合。它是由属于集合A但不属于集合B的所有元素组成的。A-B称为集合B关于A的补集(或相对补)。即-Bx|x且xBA-B也称为集合A和B的差集。 定义3.9 设U是全集，A是U的一个子集，称U-A为A关于全集的补集，也叫做A的绝对补集，简称为补集。记作A。即U-x|x且x 集合的补运算有以下性质（1）双重否定律：（A）A（2）摩根律：U（3）摩根律：U（4）矛盾律：A（A）（5）排中律：A（A）U为了简单，约定A（B）表示为AB，A（B）表示为 AB。 定理3.5 设A、B是两个集合，则下列关系式成立：（AB）AB（AB）AB这个定理称为德摩根定律。 定理3.6 设A、B、C是任意三个集合，则下列关系式成立：A-BAB A-BA-（AB） 3.3.4 集合的对称差 定义3.10 设A、B是两个集合，集合A和B的对称差记作AB，它是一个集合，其元素或属于A，或属于B，但不能既属于A又属于B。即AB(AB)-(AB) 集合的对称差的文氏图表示 由对称差的定义易得下列性质：（1）AA（1）（2）AA（3）A（4）ABBA（5）（AB）CA（BC）（6）AB(A-B)(B-A)3.4 包含排斥原理定理3.7 设A、B为有限集合，|A|、|B|为其基数，则|AB|A|+|B|-|AB|这个结论称作包含排斥原理。 第七章 图论7.1 图的基本概念7.1.1 图的基本类型 定义7.1 所谓图G是一个三元组，G=，其中V(G)是一个非空的结点集合，E（G）是边的集合，G是从边集合E到结点无序偶或有序偶集合上的函数。 定义7.2 如果两个结点之间有多条边（对于有向图，则有多条同方向的边），则称这些边为平行边，两相结点a，b间平行边的条数称为边的重数。含有平行边的图称为多重图，不含平行边和自回路的图称为简单图。 7.1.2 图中结点的度数 1无向图中结点的度数 定义7.3 设图G是无向图，v是图G中的结点，所有与v关联的边的条数，称为点v的度数，记作deg(v)。定理7.1 设图G是具有n个点，m条边的无向图，其中结点集合为V=v1，v2，vn，则 2有向图中结点的度数 定义7.4 设图G是有向图，v是图G中的结点，以v为始点的有向边的条数称为v的出度，记个deg+(v)，以v为终点的有向边的条数称为v的入度，记作deg(v)。 定理7.2 设有向图G具有n个结点，m条边，其中结点构成的集合V=v1，v2，vn，则有 7.1.3 完全图 1无向完全图 定义7.6 在n阶无向图中，如果任意两个不同的结点之间都有一条边关联，则称此无向图为无向完全图，记作Kn。定理7.3 n个结点的无向完全图Kn的边数是。 2有向完全图 定义7.7 在n阶有向图中，如果任意两个结点都有两条方向相反的有向边关联，且每一个结点都有自回路，则称此有向图为有向完全图。 定理7.4 n个结点的有向完全图Kn的边数是n2。 3竞赛图 定义7.8 设G为n阶有向图，如果G的底图为无向完全图Kn，则称G为竞赛图。 7.1.4 图的同构 定义7.9 设图G的点集为V，边集为E，图G的点集为V，边集为。如果存在着V到V的双射函数f，使对任意的u，vV，(u，v)E（或E），当且仅当（f（u），f（v）E（或E），则称图G和G 同构，记作GG。 7.1.5 补图 定义7.10 设G=为任意的n阶无向简单图，则所有使G成为Kn添加的边和G的n个结点构成的图称为图G的补图，记作。 定义7.11 设G=是任意一个n阶无向图，V=v1，v2，vn，称d（v1），d（v2），d（vn）为G的度数列。对于结点标定的无向图，它的度数列是唯一的。反之，对于给定的非负整数列d=（d1，d2，dn），若存在以V=v1，v2，vn为结点n阶无向图G，使得d（vi）=di，则称d是可图化的。特别地，若得到的图是简单图，则称d是可简单图化的。 定理7.5 设非负整数列d=（d1，d2，dn），当且仅当为偶数时，d是可图化的。 定理7.6 设非负整数列d=（d1，d2，dn），（n-1）d1d2d n0，则d是可简单图化的，当且仅当对于每个整数r，1r（n-1），r（r-1）+且为偶数。 定理7.7 设非负整数列d=（d1，d2，dn），（n-1）d1d2d n0，则d是可简单化的当且仅当d=（-1，-1，-1，）。 7.1.6 子图 定义7.12 设G=和G=是两个图，（1）若VV且EE，则称G是G的子图；（2）若G是G的子图，但VV或EE，则称G是G的真子图；（3）若G是G的子图，且V=V，则称G是G的生成子图或支撑子图。 7.2 路与回路7.2.1 通路与回路 定义7.13 在无向图（或有向图）G=中，设v0，v1，vnV，e0，e1，enE，其中ei是关联于结点vi-1，vi的边，交替序列v0e0v1e1en-1 vn称为联结v0到vn的通路或路。v0和vn分别称为通路的起点和终点，通路中所含边的条数称为该通路的长度。如果通路中的始点与终点相同，则称这条路为回路。 定理7.8 在n阶无向图中，如果存在一条从vi到vj的通路，则从vi到vj必有一条长度不大于n-1的基本通路。 定理7.9 在n阶无向图中，如果存在一条通过vi的回路，则必有一条长度不大于n的通过vi 的基本回路。 7.2.2 图的连通性 1无向图的连通性 定义7.14 设图G是无向图，u和v是图G中的两个结点，如果u和v之间有通路，则称u，v是连通的，并规定u与自身是连通的。 定义7.15 若图G是平凡图或G中任意两点都是连通的，则称图G为连通图，否则称G为非连通图或分离图。 定义7.16 设无向图G=为连通图，若存在非空点集VV，使图G删除了V的所有结点后，所得到的子图是不连通图，而删除V的任何真子集后，得到的子图仍然是连通图，则称V是G的一个点割集。若某一个结点构成一个点割集，则称该结点为割点。 定义7.17 设无向图G=为连通图，若存在非空边集EE，使图G删除了E的所有边后，所得到的子图是不连通图，而删除E的任何真子集后，得到的子图仍然是连通图，则称E是G的一个边割集。若某一个边构成一个边割集，则称该边为割边（或桥）。 定理7.10 对于任何图G，都有下面不等式成立：k其中，k、分别为G的点连通度、边连通度和结点的最小度。 定理7.11 一个无向连通图G中的结点w是割点的充分必要条件是存在两个结点u和v，使得结点u和v的每一条路都通过w。 2有向图的连通性 定义7.18 在有向图G=中，若从结点u到v有通路，则称u可达v。 定义7.19 有向图的连通性分为强连通、单向连通和弱连通三种。 定义7.20 设G是有向图，G是其子图，若G是强连通的（单向连通的，弱连通的），且没包含G的更大的强连通(单向连通，弱连通)子图，则称G是G的极大强连通子图(极大单向连通子图，极大弱连通子图)，也称为强分支（单向分支，弱分支）。 7.2.4 关键路径 定义7.21 在计划评审图中，关键路径是从发点到收点的通路中权和最大的路径。处于关键路径上的结点称为关键状态，处于关键路径上的边称为关键活动或关键工序。 定义7.22 设计划评审图G，任意的viV（G），称从发点沿着关键路径到达vi所需的时间，称为vi的最早完成的时间，记作TE（vi）。 定理7.13 设PE=v|TE（v）已经算出，TE=V-PE，若TE，则存在vTE，使得PE 定义7.23 在保证收点vn的最早完成时间TE（vn）不增加的条件下，自发点v1最迟到达vi所需要的时间，称为vi的最晚完成时间，记作TL（vi）。7.3 图的矩阵表示7.3.1 图的邻接矩阵表示 定义7.25 设图G的结点集合为V，边集为E，且V=v1，v2，vn，令则称矩阵Aaij为图G的邻接矩阵。定义7.26 设n阶简单有向图G=，V=v1，v2，vn令 则称矩阵Ppij为图G的可达矩阵。记作P（G），简记为P。 7.3.2 图的关联矩阵表示 定义7.27 设无环无向图G=，V=v1，v2，vn，E=e1，e2，em，则矩阵M（G）=（mij）nm，其中mij=称M（G）为完全关联矩阵。 定义7.28 设简单有向图G=，V=v1，v2，vn，E=e1，e2，em，则矩阵M（G）=（mij）nm，其中称M（G）为G的完全关联矩阵。7.4 欧拉图7.4.1 欧拉图的定义 定义7.29 给定无孤立结点图G，如果图中存在一条通过图中各边一次且仅一次的回路，则称此回路为欧拉回路，具有欧拉回路的图，称为欧拉图。如果图中存在一条通过图中各边一次且仅一次的通路，则称此通路为欧拉通路，具有欧拉通路的图，称为半欧拉图。 7.4.2 欧拉图的判定1无向图的欧拉定理 定理7.17 无向连通图G是欧拉图的充分必要条件是图中各点的度数为偶数。 定理7.18 无向连通图是半欧拉图的充分必要条件是：图中至多有两个奇数度结点。 2有向图的欧拉定理 定理7.19 设图G是有向连通图，图G是欧拉图的充分必要条件是：图中每个结点的入度和出度相等。 定理7.20 设图G是有向连通图，图G是半欧拉图的充分必要条件是：至多有两个结点，其中一个结点的入度比它的出度多1，另一个结点的出度比它的入度多1，而其他结点的入度和出度相等。 7.5 哈密尔顿图 7.5.2 哈密尔顿图的判定 定理7.21 设图G=是哈密尔顿图，则对于结点集V的每个非空子集S，都有W（G-S）|S|成立，其中W（G-S）是G-S中的连通分支数。 定理7.22 设图G是具有n个结点（v1，v2，vn）的无向简单图，如果图G中任意两个不同结点的度数之和大于等于n-1，即 deg(vi)+deg(vj)n-1则图G具有哈密尔顿通路，即G是半哈密尔顿图。 定理7.23 设图G是具有n个结点（v1，v2，vn）的无向简单图，如果图G中任意两个不同结点的度数之和大于等于n，即deg（vi）+deg（vj）n则图G具有哈密尔顿回路，即G为哈密尔顿图。 定义7.31 给定图G=，V中有n个结点，若将图G中度数之和至少是n的非邻接结点连接起来得到图G，对图G重复上述步骤，直到不再有这样的结点存在为止，所得到的图，称为图G的闭包，记作C（G）。 定理7.24 当且仅当一个简单图G的闭包是哈密尔顿图时，则图G是哈密尔顿图。 定理7.25 竞赛图必有哈密尔顿通路. 定理7.26 强连通的竞赛图必有哈密尔顿通路. 7.6 树7.6.1 无向树 1无向树的定义与性质 定义7.32 设T是无回路的无向简单连通图，则称T为无向树，或简称为树。在树中，度数为1的点称为树叶，度数大于1的点称为内结点或分枝点。 定理7.27 设T是含n个结点和m条边的简单无向图，则下列各结论都是等价的，都可作为无向树的定义。（1）T连通且无回路。（2）T中任意两个不同的结点间，有且仅有一条通路相连。（3）T无回路且n=m+1。（4）T连通且n=m+1。（5）T连通，但删去树中任意一条边，则变成不连通图。（6）T连通且无回路，若在T中任意两个不邻接的结点中添加一条边，则构成的图包含唯一的回路。 2生成树与最小生成树 定理7.29 一条回路和任何一棵生成树的补图至少有一条公共边。 定理7.30 有一个边割集和任何生成树至少有一条公共边。 定义7.34 在图的所有生成树中，树权之和最小的生成树，称为最小生成树。 定理7.31 设图有n个结点，可用下面的算法产生最小生成树。（1）选取最小边e1，设边数k=1；（2）若k=n-1，结束，否则转（3）；（3）设已选择边为e1，e2，ek，在G中选择不同于e1，e2，ek的边ek+1，使ek+1是满足e1，e2，ek，ek+1中无回路的权最小的边。（4）k=k+1，转（2）。 定义7.35 如果一个有向图的底图为无向树，则该有向图称为有向树。 定义7.36 在有向树T中，如果有且仅有一个入度为0的点。其他点的入度均为1，则称有向树T为有根树，简称根树。入度为0的点称为根，出度为0的点称为树叶或叶片，出度不为0的点称为分枝点或内结点。 定义7.37 根树包含一个或多个结点，这些结点中某一个称为根，其他所有结点被分成有限个子根树。 定义7.38 在根树中，如果每一个结点的出度小于或等于k，则称这棵树为k叉树。若每一个结点的出度恰好等于k或零，则称这棵树为完全k叉树，若所有树叶的层次相同，称为正则k叉树当k=2时，称为二叉树。 7.6.3 周游算法 1前序周游算法 设需要周游的2叉树为T，其左子树为T1，右子树为T2，则前序周游算法的递归定义为:（1）访问T的根；（2）用前序周游算法遍历左子树T1；（3）用前序周游算法遍历右子树T2。2中序周游算法 其递归定义如下：（1）用中序周游算法遍历T的左子树；（2）访问T的根；（3）用中序周游算法遍历T的右子树。 7.6.4 前缀码与最优树 定义7.40 如果在码中，没有一个码字是另一个码字的前缀，则称这样的码为前缀码。 定理7.32 任意一棵给定的完全2叉树，可以产生唯一的一个二元前缀码。 定理7.33 任何一个前缀码都对应一棵完全2叉树. 定义7.41