置由于没有边，因此为0.
邻接矩阵： 【提示】
n个结点的邻接矩阵为n×n矩阵，即n行n列矩阵。无向图的邻接矩阵是对称矩阵.
第1章主要介绍集合论的基本概念和结论，集合的运算及其性质，以及利用运算性质进行集合表达式的化简和集合恒等式的证明等内容．考试经常涉及到的题型有以下4个：
欧拉通路、欧拉图的判别方法 汉密尔顿图的判断方法
平面图的判断方法
（1）定义的要点：图Ｇ满足无向，连通，经过每条边一次且仅一次，经过每个结点（注意：点可重复经过，边不能重复经过），这四点缺一不可．
如果同时满足这四点，当始点与终点不重合时，就是欧拉通路． 如果同时满足这四点，当始点与终点重合时，就是欧拉图． （2）欧拉图判定定理的要点：无向、连通图Ｇ是欧拉图的（充要条件是）Ｇ不含奇数度结点． 若无向、连通图Ｇ是欧拉图，那么Ｇ一定不含奇数度结点．
反之，若无向、连通图Ｇ不含奇数度结点，那么Ｇ一定是欧拉图． （3）欧拉通路判定定理的要点：无向、连通图Ｇ是欧拉通路的（充要条件是）Ｇ不含奇数度结点或只含2个奇数度结点．当Ｇ不含奇数度结点时，Ｇ是欧拉图 ．
若无向、连通图 是欧拉通路，那么 不含奇数度结点或只含2个奇数度结点．
反之，若无向、连通图Ｇ不含奇数度结点或只含2个奇数度结点，那么Ｇ一定是欧拉通路．当Ｇ不含奇数度结点时，Ｇ是欧拉图．
那么在考试中是怎样考的呢？我们来看5道历年真题：
[例1] 若集合A的元素个数为10，则其幂集的元素个数为( )．
A．ｍ为奇数 B．ｎ为偶数
C．ｎ为奇数 D．ｍ为偶数 [答案]：C [分析]
关键：无向完全图的总度数为，平均每个结点的度数为，如果中存在欧拉图，则每个结点的度数为偶数，于是ｎ为奇数．
知识点：根据欧拉图定义，每个结点的度数都是偶数，不含奇数度结点，完全图是连通图． [例2] 无向图Ｇ存在欧拉回路，当且仅当Ｇ连通且_________ [答案]：所有结点的度数全为偶数
[分析]
关键：欧拉图判定定理的要点：连通、不含奇数度结点． 知识点：欧拉图判定定理：无向连通图Ｇ是欧拉图的（充要条件是）Ｇ不含奇数度结点．
[例3]判断下列各题正误，并说明理由． （2008年9月试卷第15题） 如图1所示的图G存在一条欧拉回路.
均
[答案]：正确． [分析]
关键：欧拉图判定定理的要点：连通、不含奇数度结点． 知识点：欧拉图判定定理：无向连通图G是欧拉图的（充要条件是）G不含奇数度结点．
因为图Ｇ为连通的，且结点的度数分别为2,4,4,4,4，均为偶数，不含奇数度结点，所以Ｇ存在一条欧拉回路． [例4]判断下列各题正误，并说明理由． （2008年7月试卷第6题） 如图所示的图Ｇ存在一条欧拉回路．
[答案]：错误.因为图G为中包含度数为奇数的结点.
[分析]
关键：欧拉图判定定理的要点：连通、不含奇数度结点．
知识点：欧拉图判定定理：无向连通图是欧拉图的（充要条件是）G不含奇数度结点．． [例5]]判断下列各题正误，并说明理由．
如果图G是无向图，且其结点度数均为偶数，则图G是欧拉图 [答案]：错误.因为题中的图G缺少连通的条件.
[分析]
关键：根据欧拉图定义，缺少连通的条件．当图不连通时，图Ｇ不是欧拉图． 知识点：欧拉图的要点是：连通、无向图、不含奇数度结点．本题缺少连通条件．
【易错点】
容易漏掉欧拉图的部分要点．
（1）定义的要点：图Ｇ存在一条路，经过每个结点一次且仅一次． 在满足定义的条件下，若这条路是回路，则图Ｇ是汉密尔顿图．． 在满足定义的条件下，若这条路不是回路，则图Ｇ是汉密尔顿通路． （2）定理4.2.1：如果图中具有一条汉密尔顿回路（即汉密尔顿图），则对于Ｖ的每个非空子集
S，均有其中是的连通分支
也就是说，从图G中去掉若干个结点（至少一个结点），得到的连通分支数（即连通图数）不大于去掉的点数.。
[例1]若图
中有一条汉密尔顿回路，则对于的G每个非空子集S，在G中删除非空子集中的所有结点得到的
与W满足关系式__________．
连通分支数为W，则S中的结点数
[答案]：
[分析]
关键：记住定理4.2.1的条件和结论． 知识点：定理4.2.1：如果图
，其中
【易错点】
容易机械记忆定理，用
中具有一条汉密尔顿回路（即汉密尔顿图），则对于Ｖ的每个非空子集Ｓ，均有
是
的连通分支．
表示分支数．
．
【提示】
本题叙述与定理叙述不同，这里是用Ｗ表示
[例2] 若Ｇ是一个汉密尔顿图，则Ｇ一定是( )
A．平面图 B．对偶图
C．欧拉图 D．连通图 [答案]：D [分析]
（1）汉密尔顿图定义：Ｇ存在一条回路，经过每个点一次且仅一次．
（2）连通图定义：对任意两点【提示】
，存在路径，使得一点达到另一点
汉密尔顿图定义要点：G存在一条回路，经过每个点一次且仅一次
．
，则
．
（1）定义的要点：任意两条边，除结点外没有任何交点．
（2）欧拉定理：连通平面图G的结点数为v，边数为e，面数为，则
（3）定理4.3.3：设G是一个有v个结点e条边的连通、简单、平面图，若那么在考试中是怎样考的呢？我们来看2道历年真题：
[例1] 设连通平面图G的结点数为5，边数为6，则面数为______________． 关键：利用欧拉定理：连通平面图G的结点数为v，边数为e，面数为
解 应填
．
分别表示G的结点数，边数和面数，则v，e和
，则
满足的关系式______________． ．
，则
．
[例2] 设G是连通平面图，v，e，
关键：利用欧拉定理：连通平面图G的结点数为v，边数为e，面数为
解 应填 ．
[例3] 设G是具有n个结点m条边k个面的连通平面图，则m等于______________． （2010年1月试卷第9题） 关键：利用欧拉定理：连通平面图G的结点数为n，边数为m，面数为k，则解 应填
．
．
一、题型分析
树是图论中的重要部分之一，其在计算机科学与技术领域有着广泛的应用，二叉树更是程序设计中的一种基本的数据结构.
本章主要介绍树、生成树、二叉树、树根、最优树等概念及相关的结论与算法，包括求最小生成树的Kruskal算法、构造最优树的Huffman算法以及前缀码的求法. 经常涉及到的题型有： 1.树叶与结点间的计算 2.画最小生成树并求其权
3.构造最优树（Huffman算法）并求其权 4.求前缀码
因此，在本章学习过程中希望大家要清楚地知道一些概念：
树 连通无简单回路的无向图G. 树中次数为1的顶点称为树叶．次数大于1的顶点称为分支点或内部顶点． 森林 一个无向图称为森林，如果它的每个连通分图都是树． 树的判别 给定图T，则以下命题关于图T为树的定义等价． (1) T是无回路的连通图；
(2) 图T无回路且e＝v－1，其中e是边数，v是顶点数； (3) 图T连通且e＝v－1；
(4) 图T无回路，若增加一条新边，得到且仅得到一个回路； (5) 图T连通，但删去任一边后图便不连通（v≥0）； (6) 图T的每一对顶点之间有且仅有一条路（v≥0）．
生成树 给定一个无向图G，若G的一个生成子图T是树，则称T为G的生成树或支撑树．T的边称为树枝． 生成树的结论 任何连通图至少有一棵生成树．
权与带权图 n个结点的连通图G，每边指定一正数，称为权，每边带权的图称为带权图．G的生成树T中树枝的权之和称为T的权，记作W(T)．
有向树 如果一个有向图在不考虑边的方向时是一棵树，那么该有向图就是有向树．
根树与树根 一棵有向树T，若恰有一个顶点的入度为0，其余顶点的入度都为1，则称T为根树；入度为0的顶点称为树根；出度为0的顶点称为树叶；入度为1出度不为0的顶点称为内点；根与内点统称为分支点；从树根到T的任一顶点v的通路（顶点不同的路）的长度称为v顶点的层数；层数最大的顶点的层数称为树高．
[例1] 设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 条边后使之变成树．
【答案】4 【分析】
运用教材中的 定理5.1.1，可以作出正确选择．因为定理5.1.1中给出的图G为树的等价定义之一是图G连通且e＝v-1（e是边数，v是顶点数）．若图G变为树，则边数e＝6-1＝5。由于题中结点的总度数为18，根据定理3.1.1，总度数应为边数2倍，可知此图中有边数9条。所以应该删去9-5＝4条边才能使图G 是树。
【易错点】
大家对集合中有的元素用集合形式表示的情形容易混淆，但这种类型考题中经常出现，大家一定要习惯．本题主要是检查大家对属于关系∈和包含关系?是否理解，能否正确运用。
【提示】
首先检查各选项给出的关系符号∈和?左边的式子是集合A的元素还是子集，然后判断选项中使用的关系符号是否正确，确定选项。
[例2] 已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 ． [答案] 5 [分析]
设无向树T的树叶数为x，因为树叶是度数为1的结点．
那么，由定理3.1.1（握手定理）设G是一个图，其结点集＝－合为V，边集合为E，则
得： 4+3+2+x=2（8-1），即x=5．应填5． 【易错点】
题中没有直接给出图Ｇ的边数，而是给出了结点的总度数，这里大家要清楚总度数和边数之间的关系。
【提示】
设G是有ｎ个结点，ｍ条边的连通图，必须删去Ｇ的( m-n+1 )条边，才能确定G的一棵生成树
求最小生成树的方法主要有避圈法与破圈法．那到底什么是避圈法和破圈法？我们一起来看一看： 避圈法：图G有n个顶点，以下算法产生的是最小生成树（避圈法由kfuskal给出. （1）选择最小的边e1，置边数i←1； （2）i=n-1结束，否则转3）；
（3）设定已选定e1 ，e2,，…，ei，，在G中选取不同于e1，e2,，…，ei的边ei+1，使{ e1，e2,，…，ei，ei+1}无回路，且ei+1是满足此条件的带权最小的边； （4）i←i+1，转2）． ? 破圈法：
（1）初始令 G0,= G, i←0；
（2）若Gi中不含圈，则转（3）；否则，设C为Gi中的一个圈，ei为C上带权最大的边，令Gi+1= Gi - ei ； i← i+1，转（1）．
（3）结束．
结束时G中的图为最小生成树。
最小生成树的权等于最小生成树各边权值的和。
[例1] 图G=
（1）画出Ｇ的图形； （2）写出Ｇ的邻接矩阵；
（3）求出Ｇ权最小的生成树及其权值． [解题过程]
（1）因为V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，则G的图形表示为：
（2）根绝邻接矩阵的定义，写出邻接矩阵为： （3）用避圈法： 第1步：选(a, b)边； 第2步：选(a c)边； 第3步：选(c, e)边； 第4步：选(b, d)边．
这样，得到了最小的生成树，如下图中粗线所示． 最小的生成树的权为2+1+1+3=7．
【提示】 求最小生成树可以利用避圈法或者破圈法．
求最小生成树的权就是各边权值之和
设T是一棵根树，若T的每个分支点的出度至多为m，则称T为m叉树；若T的每个分支点的出度恰好等于m，则称T为m叉正则树；若T是m叉正则树，且每个树叶的层数均为树高，则称T为完全m叉正则树；若T是m叉树且为有序树，则称T为m叉有序树；若T是m叉正则树且为有序树，则称T为m叉正则有序树；若T是m叉完全正则树且为有序树，则称T为m叉完全正则有序树；若m=2，则T称为二叉树．
带权二叉树 ?给定一组权w1，w2，…，wt，不妨设w1≤w2≤…≤wt．设有一棵二叉树，共有t片树叶，分别带权w1，w2，…，wt，则该二叉树称为带权二叉树．
最优树? 设在有t个树叶的带权二叉树T中，带权为wi (i=1,…,t)的树叶，其通路长度为L(wi)，则将w(T) =?wiL(wi) (i=1,…,t)称为该带权二叉树的权．在所有带权w1，w2，…，wt的二叉树 中，w(T)最小的树称为最优树．
用Huffman算法得到的最优树． （Huffman）：设T为带权w1
≤w2≤…≤wt的最优树，若将以带权w1，w2的树叶为儿子的分枝点改为带权w1+w2的树叶，得到一棵树T’，则T’也是最优树．
最优树的权：每片树叶的权乘以它到树根的长度取和
正则m叉树结论? 设有正则m叉树，其树叶数为t，分枝数为i，则(m-1)i=t-1．
[例1] 画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它们的权 [解题过程]
Huffman算法：从1, 2, 2, 3, 4中选1, 2为最低 层结点，并从权数中删去，再添上他们的和数，从 小到大排列，即2，3，3，4；
再从2，3，3，4中选2，3为倒数第2层结点， 并从上述数列中删去，再添上他们的和数，从小到
大排列，即3，4，5；
然后，从3，4，5中选3，4为倒数第2层结点，
并从上述数列中删去，再添上他们的和数，从小到大排列， 即5，7；……
最优二叉树如右图所示。
最优二叉树权值为：1×3+2×3+2×2+3×2+4×2=27
【提示】
最优树的权：每片树叶的权乘以它到树根的长度取和
在求前缀码前，我们需要了解何为前缀码: 给定一个序列集合，若没有一个序列是另一个序列的前缀，该序列集合称为前缀码．
结论：任何一棵二叉树的树叶可对应一个前缀码． 任何一个前缀码都对应一个二叉树
【提示】
最优树的权：每片树叶的权乘以它到树根的长度取和．
[例1] 给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 ，则该序列集合构成前缀码． 【答案】 0 【分析】
根据定义5.2.10 给定一个序列集合，若没有一个序列是另一个序列的前缀，则该序列集合为前缀码。
本章主要介绍命题、联结词的概念，命题公式与翻译，真值表与等价公式，重言式与蕴含式，范式和命题逻辑的推理理论等内容。经常涉及到的题型有： 将陈述句翻译成命题公式 求命题公式的真值 命题公式类型的判断 等价公式的证明 求范式和主范式
判断有效结论的直接证法和间接证
因此，在本章学习过程中希望大家要清楚地知道：
命题表述为具有确定真假意义的陈述句．命题必须具备二个条件：语句是陈述句；语句有唯一确定的真假意义．因此判断一个句子是否为命题，应首先判断它是否为陈述句，再判断它是否有唯一的真值．
例如，“北京是中国的首都”是陈述句，有确定的真假意义，是命题，为真命题．
将陈述句翻译成命题公式关键在于陈述句的逻辑含义要与命题公式的逻辑含义保持一致。因此首先要注意陈述句中表示特殊逻辑关系的词语的含义，其次要掌握五个联结词“”所表示的命题间的逻辑关系：“
，，
，
，
” 是唯一一元联结词，表示否定；合取联结词“”在语句中相
当于“不但…而且…”，“既…又…”；析取联结词“”在语句中表示“或”的含义；条件联结词“”在语句中表示“如果P则Q”或“只有Q，才P”；双条件联结词“”在语句中相当于“…当且仅当…”．
例如，“我们不能划船，又跑步”。设P：我们划船，G：我们跑步，那么该命题符号化为：
或．
[例1] 将语句“他是学生．”翻译成命题公式． （2009年10月试卷第11题） [解题过程]
依据命题必须具备的二个条件，可设P：他是学生， 则该语句翻译成命题公式为： P． [例2] 将语句“今天没有人来．”翻译成命题公式． [解题过程]
依据命题必须具备的二个条件以及否定联结词“ 可设 P：今天有人来，
”的定义，
则语句“今天没有人来．” 翻译成命题公式为 P。
[例3] 将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式．