（1）a,b,c全映射到2；
（2）a 映射到1，b 和 c映射到2； （3）b 映射到1，a 和 c映射到2； （4）c 映射到1，a 和 b映射到2； （5）a 映射到2，b 和 c映射到1； （6）b 映射到2，a 和 c映射到1； （7）c 映射到2，a 和 b映射到1； （8）a,b,c全映射到1；
因此，函数个数为8．另外，此类题目也可以作以下分析．A到B映射个数可以描述为： C30+C31+C32+C33=8 正确答案：8 【提示】
函数概念中，有两点尤其要注意．第一，是函数的单值性，即对于A中任何元素，必须有B中元素映射 f 唯一对应；第二，是函数的定义域，即A是函数 f 定义域
[例2] 判断说明：设N、R分别为自然数集与实数集，f：N→R，f (x)=x+6，则 f 是单射． [答案]：正确 [分析]
设x1，x2为自然数且x1≠ x2，则有 f(x1)= x1+6 ≠ x2+6= f(x2)，故 f 为单射．
【提示】
“单射”概念中，强调的是对于不同定义域中的值，通过函数映射得到的对应值不同，这种“一对一”是从前到后的一对一，并不要求从后到前一对一．
[例3] 设A={a，b}，B={1，2}，R1，R2，R3是A到B的二元关系，且R1={ ,
C．R3 D．R1和R3 [答案]：B [分析]
函数的概念中，强调两点：第一，函数的单值性，即对于每一个定义域中的值，只能有一个对应函数值；第二，函数的定义域必须为集合A．本题中的R2不符合函数概念强调的第一点．
（1）偏序关系
设R是非空集合A上的二元关系，如果R是自反的、反对称的和传递的，则称R是A上的偏序关系或者简称序关系．偏序关系记作≤．∈≤，则称a小于等于b，记作a ≤ b． （2）哈斯图 作图规则：
i．去掉每个结点的自回路，用空心点表示集合的元素；
ii．对于集合任意元素a和b，若a≤b，则将a画在b的下方；
iii．对于集合任意元素a和b，若a 一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一；且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样． [例1] 若偏序集 的哈斯图如所示，则集合A的最大元为a，最小元不存在． [答案] 错误 集合A的最大元不存在，a是极大元． 若a为最大元，则对于任意x∈A，必有 【易错点】 哈斯图不是简单的层次关系图，不要用层次关系判断最大元、最小元、极大元、极小元等． 【提示】 最小元应小于等于其它各元素；最大元应该大于等于其它各元素；极小元应该小于等于一些元素，而与剩下的元素没有关系；极大元应该大于等于一些元素，而与剩下的元素没有关系．最大元和最小元不一定存在，如果存在则必定唯一. [例2] 设集合A={1，2，3，4，5}，偏序关系≤是A上的整除关系，则偏序集 上的元素5是集合A的（ ）. A．最大元 B．极大元 C．最小元 D．极小元 [答案] B 由于元素4和5没有整除关系，显然5不是最大元． 同理，5和2没有整除关系，5也不是最小元． 【提示】 整除关系是常考的一类偏序关系．两个元素是否具备整除关系可以不直接表达，所以题型描述简单，但是同学们需要将序关系的概念应用到此类题目中才能正确辨别． 第3章是图论的基础部分，主要介绍图论的基本概念与结论，包括图的基本概念、图的连通性与连通度、图的矩阵表示等.经常涉及到的题型有： 已知点集和边集画图，求结点的度数，画补图 握手定理计算题 强分图（连通）、单向分图（连通）、弱分图（连通）的判断 求点割集，割点，边割集，割边 无向简单图，已知点集和边集求邻接矩阵 我们将反映对象及其相互关系的图分为无向图和有向图，那我们就仔细了解一下它们，以及它们的区别、联系： 1. 无向图是一个有序的二元组 2. 有向图是一个有序的二元组 ① 用图形表示无向图和有向图时，用小圆圈表示顶点，用顶点之间的连线表示无向边，用有方向的连线表示有向边. ② 在无向图中，与结点相关联的边的条数，称为该结点的度数，记作deg(V)，用Δ(G)表示最大度，用δ(G)表示最小度. ③ 在有向图中，对于任何结点，出度就是以其为始点的边的条数，入度就是以其为终点的边的条数，出度与入度之和称为该结点的度数. ④ 如果图G与图H互为补图，则它们的顶点集相同，且它们的边集的并集等于其完全图的边集. [例1]设图G＝ （1）画出G的图形表示； （2）求出每个结点的度数； （3）画出图G的补图的图形． [解题过程] （1）关系图 先根据G的结点集画出图中的5个结点，这里的结点按逆时针排列，也可以按顺时针排列.再根据边集，在邻接的结点间将边画出. （2）在图示中观察每个结点连接的边数，计算出各结点的度数. deg(v1)=2 deg(v2)=3 deg(v3)=4 deg(v4)=3 deg(v5)=2 （3）补图 补图的结点集与原图的结点集相等，补图的边集是那些由结点集确定的完全图中去掉原图中的边所留下的边组成 的.补图的边数＝完全图的边数－原图的边数.又因为5个结点的完全图的边数为条 条.所以10－7＝3 [例2] 设G是一个n阶无向简单图，n是大于等于2的奇数．证明G与中的奇数度顶点个数相等(补图)． [证明过程]分析] 因为握手定理：结点度数之和等于边数的2倍，所以图G的结点度数总和一定是偶数. 又因为n是奇数，图G有奇数个结点，所以n阶完全图每个顶点度数为偶数. 因此，奇数＋奇数＝偶数，若G中顶点v的度数为奇数，则在补图中的奇数度顶点个数相等． 【提示】 补图与原图的结点集相等，补图与原图的边数之和等于其结点的完全图的边数. 是G的 中v的度数一定也是奇数，所以G与 那么在考试中是怎样考的呢？我们来看2道历年真题： [例1] 设图G＝ B． C． D． [答案]：Ｃ [分析] 选项A，不对. 因为没有连加符号∑，不能表示所有度数之和. 选项B，不对. 不但没有连加符号∑，而且边数 也没有乘以2. 选项C，正确. 有连加符∑，还有边数 选项D，不对. 乘以2.表示所有的度数之和等于边数的2倍. 没有将边数也没有乘以2. 【提示】 不论图中有奇数个结点或者偶数个结点，图的度数之和都是偶数. 【易错点】 同学们容易忘记将边数乘以2倍，容易忘记表示所有度数之和的连加符号. [例2] 设G是一个图，结点集合为V，边集合为E，则G的结点度数之和为_________ ． [答案]2（或“边数的两倍”） [分析] 根据握手定理，在图中所有结点的度数之和等于边数的2倍. 【提示】 不论图中有奇数个结点或者偶数个结点，图的度数之和都是偶数 那么在考试中是怎样考的呢？我们来看2道历年真题： [例1] 设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( )． （2009年1月试卷第2题） A．（a）是强连通的 B．（b）是强连通的 C．（c）是强连通的 D．（d）是强连通的 [答案] Ｄ [分析] 选项A，不对. （a）图存在一点（左下角点）不可达其它点，所以不是强连通图.但图存在一点（左上角点）可达其它各点，所以是单向连通图，也是弱连通图. 选项B，不对. b）图存在一点（右上角点）不可达其它点，所以不是强连通图.但图存在一点（右下角点）可达其它各点，所以是单向连通图，也是弱连通图. 选项C，不对. （c）图存在两点（右上和左下角点）不可达其它点，所以不是强连通图.但图略去边的方向后，是连通图，所以是弱连通图. 选项D，正确. （d）图中任何两结点互相可达，所以是强连通图，当然也是单向连通图和弱连通图. 易错点】 同学们要完全理解弱连通图、意向连通图、强连通图的概念，不能将它们混淆. 【提示】 强连通图一定是单向连通图和弱连通图；单向连通图一定是弱连通图.反之，不成立. [例2] 判断下图是哪类连通图. ⑴ ⑵ （3） [解题过程] （1）存在V1点，可达其它各点V2 、V3、V4，所以是单向连通图.但图中V3点不可达其它点，所以不是强连通图. （2）略去边的方向后，不是连通图，所以不是任何连通图. （3）存在V1点，可达其它各点V2、V3、V4. 存在V2点，可达其它各点V1 、V3 、V4. 存在V3点，可达其它各点V1 、V2 、V4. 存在V4点，可达其它各点V1、V2、V3. 因此，任何两结点都可达，所以是强连通图 【提示】 强连通图一定是单向连通图和弱连通图；单向连通图一定是弱连通图.反之，不成立. 那么在考试中是怎样考的呢？我们来看2道历年真题： [例1] 如图一所示，以下说法正确的是 ( )． （2008年9月试卷第4题） A．e是割点 B．{a, e}是点割集 C．{b, e}是点割集 D．{d}是点割集 [答案] Ａ [分析] 选项A，正确. 去掉点e和其连接的边后，图就不连通了. 选项B，不对． 虽然去掉点ａ、点e和其连接的边后，图就不国通了.但是单单去掉点e和其连接的边后也可以不连通，所以不应该包括点a． 选项C，不对. 虽然去掉点b、点e和其连接的边后，图就不连通了.但是单单去掉点e和其连接的边后也可以不连通，所以不应该包括点b. 选项D，正确. 去掉点d和其连接的边后，图依然连通. 【提示】 点割集里只有一个结点时，这个结点才是割点. 【易错点】 同学们要准确地确定点割集里的结点，不能含多余的结点. [例2] 如图一所示，以下说法正确的是( ）． （2010年7月试卷第4题） A．｛（a，e）｝是割边 B．｛(a, e)｝是边割集 C．{（a，e） ,（b，ｃ）}是边割集 D．｛(ｄ, e)｝是边割集 [解题过程] [分析] 选项A，不对. 去掉边（a，e）后，图依然连通.而且{（a，e）}是集合. 选项B，不对.去掉边（a，e）后，图依然连通. 选项C，不对. 去掉边（a，e），（b，c）后，图依然连通. 选项D，正确. 去掉边（d，e）后，图就不连通了. 【提示】 边割集里只有一条边时，这条边才是割边． 【易错点】 同学们要准确地确定边割集里的边，不能含有多余的边． [例1]已知图G的邻接矩阵为 则则G有（ ）. （2008年7月试卷第5题） A．5点，8边 B．6点，7边 C．6点，8边 D．5点，7边 [解题过程] 选项A，不对。 因为无向图的邻接矩阵的上三角矩阵数字之和为7，所以边数为7。 选项B，不对。 因为邻接矩阵是5×5方阵，所以图的结点数为5个。 选项C，不对。 因为邻接矩阵是5×5方阵，所以图的结点数为5个。 因为无向图的邻接矩阵的上三角矩阵数字之和为7，所以边数为7。 选项D，正确。 【提示】 n个结点的邻接矩阵为n×n矩阵，即n行n列矩阵. 【易错点】 有向图的邻接矩阵里所有的数字之和等于边数.而因为无向图忽略了方向，所以无向图的邻接矩阵的上三角矩阵数字之和或者下三角矩阵数字之和才是边数.不要混淆． [例2]设G＝ 图G有4个结点，则G的邻接矩阵为4×4矩阵，按结点的序号排序，根据结点间的邻接关系，确定邻接矩阵中的对应数值。边（v1，v3）对应的位置为1，边（v2，v3）对应的位置为1，边（v2，v4）对应的位置为1，边（v3，v4）对应的位置为1.又因为是无向图，所以边没有方向，因此在（v3，v1）（v3，v2），（v 4，v2），（v4，v3）的位置也是1.其余的位