《离散数学题型梳理-第3章 图的基本概念与性质_中学教育-中考.pdf》由会员分享，可在线阅读，更多相关《离散数学题型梳理-第3章 图的基本概念与性质_中学教育-中考.pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 1 离散数学常考题型梳理 第 3 章 图的基本概念与性质 一、题型分析 本章是图论的基础部分，主要介绍图论的基本概念与结论，包括图的基本概念、图的连通性与连通度、图的矩阵表示等经常涉及到的题型有：3-1 已知点集和边集画图，求结点的度数，画补图。3-2 握手定理计算题。3-3 强分图（连通）、单向分图（连通）、弱分图（连通）的判断。3-4 求点割集，割点，边割集，割边。3-5 无向简单图，已知点集和边集求邻接矩阵。因此，在本章学习过程中希望大家要清楚地知道：1一个无向图是一个有序的二元组，记作 G，其中 V称为顶点集，其元素称为顶点或结点；其中 E 称为边集，其元素称为无向边，简称为边。一个
2、有向图是一个有序的二元组，记作 G，其中 V称为顶点集，其元素称为顶点或结点；其中 E 称为边集，其元素称为有向边，简称为边。用图形表示无向图和有向图时，用小圆圈表示顶点，用顶点之间的连线表示无向边，用有方向的连线表示有向边。在无向图中，与结点相关联的边的条数，称为该结点的度数，记作 deg(V)，用 (G)表示最大度，用 (G)表示最小度。在有向图中，对于任何结点，出度就是以其为始点的边的条数，入度就是以其为终点的边的条数，出度与入度之和称为该结点的度数。如果图 G 与图 H 互为补图，则它们的顶点集相同，且它们的边集的并集等于其完全图的边集。2 握手定理：在图中，结点度数总和边数2。在有向
3、图中，结点出度总和结点入度总和边数。3弱连通图：一个简单有向图略去边的方向后是连通图，则称其为弱连通图。单向连通图：简单有向图中，任何结点偶对中，至少从一个结点到另一个结点是可达的，则称其为单向连通图。强连通图：简单有向图中，任何结点偶对中，两结点互相可达，则称其为强连通图。注意：强连通图一定是单向连通图和弱连通图，单向连通图一定是弱连通图。反之不成立。弱分图（极大弱连通子图）：如果简单有向图的一个子图是弱连通的，并且没有比其更大的子图是弱连通的，则这个子图是极大弱连通子图。单向分图（极大单向连通子图）：如果简单有向图的一个子图是单向连通的，并且没有比其更大的子图是单向连通的，则这个子图是极大
4、单向连通子图。2 强分图（极大强连通子图）：如果简单有向图的一个子图是强连通的，并且没有比其更大的子图是强连通的，则这个子图是极大强连通子图。4 在无向连通图中，若存在某点集，使图删除了该点集中的结点后就不连通了，并且删除了该点集的任何真子集后依然连通，则称该点集为点割集，若点割集中只有一个结点，则称该结点为割点。在无向连通图中，若存在某边集，使图删除了该边集中的边后就不连通了，并且删除了该边集的任何真子集后依然连通，则称该边集为边割集，若边割集中只有一条边，则称该边为割边。5 用 n 阶方阵表示 n 阶简单图，方阵的行和列依次表示各结点。若某两个结点相邻，则方阵对应位置表示为 1，若某两个结
5、点不相邻，则方阵对应位置表示为 0，称方阵为该图的邻接矩阵。图的邻接矩阵是不唯一的，与结点标定的次序有关。当给定的简单图是无向图时，邻接矩阵是对称的；当给定的简单图是有向图时，邻接矩阵不一定对称。二、常考知识点分析 常考知识点 1：已知点集和边集画图，求结点的度数，画补图。（历年考核次数：4次，本课程共考过 6 次；重要程度：）（2008 年 7 月试卷第 18 题）设图 G=，V=v1，v2，v3，v4，v5，E=(v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)，试(1)画出 G 的图形表示；(2)求出每个结点的度数；(3)画出图
6、 G 的补图的图形 解题过程 （1）关系图 先根据 G 的结点集画出图中的 5 个结点，这里的结点按逆时针排列，也可以按顺时针排列。再根据边集，在邻接的结点间将边画出。（2）在图示中观察每个结点连接的边数，计算出各结点的度数。deg(v1)=2 deg(v2)=3 deg(v3)=4 deg(v4)=3 v1 v2 v3 v4 v5 论包括图的基本概念图的连通性与连通度图的矩阵表示等经常涉及到的题型有已知点集和边集画图求结点的度数画补图握手定理计算题强分图连通单向分图连通弱分图连通的判断求点割集割点边割集割边无向简单图已知点集和边集元素称为顶点或结点其中称为边集其元素称为无向边简称为边一个有向
7、图是一个有序的二元组记作其中称为顶点集其元素称为顶点或结点其中称为边集其元素称为有向边简称为边用图形表示无向图和有向图时用小圆圈表示顶点用顶用表示最大度用表示最小度在有向图中对于任何结点出度就是以其为始点的边的条数入度就是以其为终点的边的条数出度与入度之和称为该结点的度数如果图与图互为补图则它们的顶点集相同且它们的边集的并集等于其完全图的边 3 deg(v5)=2 （3）补图 补图的结点集与原图的结点集相等，补图的边集是那些由结点集确定的完全图中去掉原图中的边所留下的边组成的。补图的边数完全图的边数原图的边数。又因为 5 个结点的完全图的边数为5(51)102条。所以 1073 条。易错点：同
8、学们画图时不要漏掉点集中的每一个点，边集中的每一条边。画补图时容易把原图中的某个结点漏掉不画。提示：画图时，结点的位置应按一定规律排列，不能杂乱无章。（2009 年 7 月试卷第 18 题）设 G 是一个 n 阶无向简单图，n 是大于等于 2 的奇数证明 G 与G中的奇数度顶点个数相等(G是 G 的补图)解题过程 证明：因为握手定理：结点度数之和等于边数的 2 倍，所以图 G 的结点度数总和一定是偶数。又因为 n 是奇数，图 G 有奇数个结点，所以 n 阶完全图每个顶点度数为偶数。因此，奇数奇数偶数，若 G 中顶点 v 的度数为奇数，则在补图G中 v 的度数一定也是奇数，所以 G 与G中的奇数
9、度顶点个数相等 易错点：同样是补图的知识，由于是证明题就略比计算题较难理解，同学们要熟练应用补图的知识。提示：补图与原图的结点集相等，补图与原图的边数之和等于其结点的完全图的边数。常考知识点 2：握手定理计算题。（历年考核次数：2 次，本课程共考过 6 次；重要程度：）（2008 年 9 月试卷第 2 题）设图 G，v V，则下列结论成立的是()Adeg(v)=2 E B deg(v)=E CEvVv2)deg(DEvVv)deg(v1 v2 v3 v4 v5 论包括图的基本概念图的连通性与连通度图的矩阵表示等经常涉及到的题型有已知点集和边集画图求结点的度数画补图握手定理计算题强分图连通单向分
10、图连通弱分图连通的判断求点割集割点边割集割边无向简单图已知点集和边集元素称为顶点或结点其中称为边集其元素称为无向边简称为边一个有向图是一个有序的二元组记作其中称为顶点集其元素称为顶点或结点其中称为边集其元素称为有向边简称为边用图形表示无向图和有向图时用小圆圈表示顶点用顶用表示最大度用表示最小度在有向图中对于任何结点出度就是以其为始点的边的条数入度就是以其为终点的边的条数出度与入度之和称为该结点的度数如果图与图互为补图则它们的顶点集相同且它们的边集的并集等于其完全图的边 4 解题过程 C 选项 A，不对 因为没有连加符号，不能表示所有度数之和。选项 B，不对 不但没有连加符号，而且边数E也没有乘
11、以 2。选项 C，正确 有连加符号，还有边数E乘以 2。表示所有的度数之和等于边数的 2 倍。选项 D，不对 没有将边数E乘以 2。易错点：学生容易忘记将边数乘以 2 倍，容易忘记表示所有度数之和的连加符号。提示：不论图中有奇数个结点或者偶数个结点，图的度数之和都是偶数。（2009 年 10 月试卷第 8 题）设 G 是一个图，结点集合为V，边集合为 E，则 G 的结点度数之和为 解题过程 2|E|（或“边数的两倍”）根据握手定理，在图中，所有结点的度数之和等于边数的2 倍。易错点：学生容易忘记将边数乘以 2 倍，容易忘记表示所有度数之和的连加符号。提示：不论图中有奇数个结点或者偶数个结点，图
12、的度数之和都是偶数。常考知识点 3：强分图（连通）、单向分图（连通）、弱分图（连通）的判断。（历年考核次数：1，本课程共考过 6 次；重要程度：）（2009 年 1 月试卷第 2 题）设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是()图一 A（a）是强连通的 B（b）是强连通的 C（c）是强连通的 D（d）是强连通的 解题过程 D 选项 A，不对 （a）图存在一点（左下角点）不可达其它点，所以不是强连通图。但图存论包括图的基本概念图的连通性与连通度图的矩阵表示等经常涉及到的题型有已知点集和边集画图求结点的度数画补图握手定理计算题强分图连通单向分图连通弱分图连通的判断求点割
13、集割点边割集割边无向简单图已知点集和边集元素称为顶点或结点其中称为边集其元素称为无向边简称为边一个有向图是一个有序的二元组记作其中称为顶点集其元素称为顶点或结点其中称为边集其元素称为有向边简称为边用图形表示无向图和有向图时用小圆圈表示顶点用顶用表示最大度用表示最小度在有向图中对于任何结点出度就是以其为始点的边的条数入度就是以其为终点的边的条数出度与入度之和称为该结点的度数如果图与图互为补图则它们的顶点集相同且它们的边集的并集等于其完全图的边 5 在一点（左上角点）可达其它各点，所以是单向连通图，也是弱连通图。选项 B，不对（b）图存在一点（右上角点）不可达其它点，所以不是强连通图。但图存在一点
14、（右下角点）可达其它各点，所以是单向连通图，也是弱连通图。选项 C，不对（c）图存在两点（右上和左下角点）不可达其它点，所以不是强连通图。但图略去边的方向后，是连通图，所以是弱连通图。选项 D，正确（d）图中任何两结点互相可达，所以是强连通图，当然也是单向连通图和弱连通图。易错点：同学们要完全理解弱连通图、单向连通图、强连通图的概念，不能将它们混淆。提示：强连通图一定是单向连通图和弱连通图；单向连通图一定是弱连通图。反之不成立。（练习题）判断下图是哪类连通图。（3）解题过程 （1）存在 V1点，可达其它各点 V2、V3、V4，所以是单向连通图。但图中 V3点不可达其它点，所以不是强连通图。（2
15、）略去边的方向后，不是连通图，所以不是任何连通图。（3）存在 V1点，可达其它各点 V2、V3、V4。存在 V2点，可达其它各点 V1、V3、V4。存在 V3点，可达其它各点 V1、V2、V4。存在 V4点，可达其它各点 V1、V2、V3。因此，任何两结点都可达，所以是强连通图。易错点：同学们要完全理解弱连通图、单向连通图、强连通图的概念，不能将它们混淆。提示：强连通图一定是单向连通图和弱连通图；单向连通图一定是弱连通图。反之不成立。V1 V2 V3 V4 V1 V2 V3 V4 V1 V2 V3 V4 论包括图的基本概念图的连通性与连通度图的矩阵表示等经常涉及到的题型有已知点集和边集画图求结
16、点的度数画补图握手定理计算题强分图连通单向分图连通弱分图连通的判断求点割集割点边割集割边无向简单图已知点集和边集元素称为顶点或结点其中称为边集其元素称为无向边简称为边一个有向图是一个有序的二元组记作其中称为顶点集其元素称为顶点或结点其中称为边集其元素称为有向边简称为边用图形表示无向图和有向图时用小圆圈表示顶点用顶用表示最大度用表示最小度在有向图中对于任何结点出度就是以其为始点的边的条数入度就是以其为终点的边的条数出度与入度之和称为该结点的度数如果图与图互为补图则它们的顶点集相同且它们的边集的并集等于其完全图的边 6 常考知识点 4：求点割集，割点，边割集，割边。（历年考核次数：4 次，本课程共
17、考过 6 次；重要程度：）（2008 年 9 月试卷第 4 题）如图一所示，以下说法正确的是 ()Ae 是割点 Ba,e是点割集 Cb,e是点割集 Dd是点割集 图一 解题过程 A 选项 A，正确 去掉点 e 和其连接的边后，图就不连通了。选项 B，不对 虽然去掉点 a、点 e 和其连接的边后，图就不连通了。但是单单去掉点 e 和其连接的边后也可以不连通，所以不应该包括点 a。选项 C，不对 虽然去掉点 b、点 e 和其连接的边后，图就不连通了。但是单单去掉点 e 和其连接的边后也可以不连通，所以不应该包括点 b。选项 D，不对 去掉点 d 和其连接的边后，图依然连通。易错点：同学们要准确地确
18、定点割集里的结点，不能含有多余的结点。提示：点割集里只有一个结点时，这个结点才是割点。（2009 年 7 月试卷第 4 题）如图一所示，以下说法正确的是()A(a,e)是割边 B(a,e)是边割集 C(a,e),(b,c)是边割集 D(d,e)是边割集 图一 解题过程 D 选项 A，不对 去掉边（a，e）后，图依然连通。而且（a，e）是集合。论包括图的基本概念图的连通性与连通度图的矩阵表示等经常涉及到的题型有已知点集和边集画图求结点的度数画补图握手定理计算题强分图连通单向分图连通弱分图连通的判断求点割集割点边割集割边无向简单图已知点集和边集元素称为顶点或结点其中称为边集其元素称为无向边简称为边
19、一个有向图是一个有序的二元组记作其中称为顶点集其元素称为顶点或结点其中称为边集其元素称为有向边简称为边用图形表示无向图和有向图时用小圆圈表示顶点用顶用表示最大度用表示最小度在有向图中对于任何结点出度就是以其为始点的边的条数入度就是以其为终点的边的条数出度与入度之和称为该结点的度数如果图与图互为补图则它们的顶点集相同且它们的边集的并集等于其完全图的边 7 选项 B，不对 去掉边（a，e）后，图依然连通。选项 C，不对 去掉边（a，e），（b，c）后，图依然连通。选项 D，正确 去掉边（d，e）后，图就不连通了。易错点：同学们要准确地确定边割集里的边，不能含有多余的边。提示：边割集里只有一条边时，
20、这条边才是割边。常考知识点 5：无向简单图，已知点集和边集求邻接矩阵。（历年考核次数：6次，本课程共考过6 次；重要程度：）（2008 年 7 月试卷第 5 题）已知图 G 的邻接矩阵为 ，则 G 有（）A5 点，8 边 B6 点，7 边 C6 点，8 边 D5 点，7 边 解题过程 D 选项 A，不对 因为无向图的邻接矩阵的上三角矩阵数字之和为7，所以边数为 7。选项 B，不对 因为邻接矩阵是5 5 方阵，所以图的结点数为5 个。选项 C，不对 因为邻接矩阵是5 5 方阵，所以图的结点数为5 个。因为无向图的邻接矩阵的上三角矩阵数字之和为7，所以边数为 7。选项 D，正确 易错点：有向图的邻
21、接矩阵里所有的数字之和等于边数。而因为无向图忽略了方向，所以无向图的邻接矩阵的上三角矩阵数字之和或者下三角矩阵数字之和才是边数。不要混淆。提示：n 个结点的邻接矩阵为 n n 矩阵，即 n 行 n 列矩阵。（2010 年 1 月试卷第 17 题）设 G=，V=v1，v2，v3，v4，E=(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，试写出其邻接矩阵。论包括图的基本概念图的连通性与连通度图的矩阵表示等经常涉及到的题型有已知点集和边集画图求结点的度数画补图握手定理计算题强分图连通单向分图连通弱分图连通的判断求点割集割点边割集割边无向简单图已知点集和边集元素称为顶点或结点其中称为边
22、集其元素称为无向边简称为边一个有向图是一个有序的二元组记作其中称为顶点集其元素称为顶点或结点其中称为边集其元素称为有向边简称为边用图形表示无向图和有向图时用小圆圈表示顶点用顶用表示最大度用表示最小度在有向图中对于任何结点出度就是以其为始点的边的条数入度就是以其为终点的边的条数出度与入度之和称为该结点的度数如果图与图互为补图则它们的顶点集相同且它们的边集的并集等于其完全图的边 8 解题过程 图 G 有 4 个结点，则 G 的邻接矩阵为 4 4 矩阵，按结点的序号排序，根据结点间的邻接关系，确定邻接矩阵中的对应数值。边（v1，v3）对应的位置为 1，边（v2，v3）对应的位置为 1，边（v2，v4
23、）对应的位置为 1，边（v3，v4）对应的位置为 1。又因为是无向图，所以边没有方向，因此在（v3，v1）（v3，v2），（v 4，v2），（v4，v3）的位置也是 1。其余的位置由于没有边，因此为 0。邻接矩阵：0110101111000100 易错点：同学们不要弄错邻接矩阵中的行列关系。提示：n 个结点的邻接矩阵为 n n 矩阵，即 n 行 n 列矩阵。无向图的邻接矩阵是对称矩阵。三、模拟练习 练习 1：（2008 年 9 月试卷第 18 题）设 G=，V=v1，v2，v3，v4，v5，E=(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)，试（
24、1）给出 G 的图形表示；（2）求出每个结点的度数；（3）画出其补图的图形 解析：（1）根据结点集画出 5 个结点。再根据边集，在邻接的结点间将边画出。（2）在图中观察每个结点连接的边数，计算结点的度数。结点 v1，v2，v3，v4，v5的度数依次为 1，2，4，3，2。（3）补图的结点集与原图相同。边集就是完全图的边去掉原图的边所剩下的边。练习 2：（2010 年 1 月试卷第 17 题）设 G=，V=v1，v2，v3，v4，E=(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，试 v1 V2 V3 V4 v1 V2 V3 V4 论包括图的基本概念图的连通性与连通度图的矩阵表示
25、等经常涉及到的题型有已知点集和边集画图求结点的度数画补图握手定理计算题强分图连通单向分图连通弱分图连通的判断求点割集割点边割集割边无向简单图已知点集和边集元素称为顶点或结点其中称为边集其元素称为无向边简称为边一个有向图是一个有序的二元组记作其中称为顶点集其元素称为顶点或结点其中称为边集其元素称为有向边简称为边用图形表示无向图和有向图时用小圆圈表示顶点用顶用表示最大度用表示最小度在有向图中对于任何结点出度就是以其为始点的边的条数入度就是以其为终点的边的条数出度与入度之和称为该结点的度数如果图与图互为补图则它们的顶点集相同且它们的边集的并集等于其完全图的边 9（1）给出 G 的图形表示；（2）求出
26、每个结点的度数；（3）画出其补图的图形 解析：（1）根据结点集画出 4 个结点。再根据边集，在邻接的结点间将边画出。（2）在图中观察每个结点连接的边数，计算结点的度数。结点 v1，v2，v3，v4的度数依次为 1，2，3，2。（3）补图的结点集与原图相同。边集就是完全图的边去掉原图的边所剩下的边。练习 3：设无向图 G 有 10 条边，3 度与 4 度结点各 2 个，其余结点的度数均为 2，问 G 中有几个结点？解析：根据握手定理，图中所有结点的度数之和等于边数的2 倍。因为有 10 条边，所以图中所有结点的度数之和为10 220 度。因为 3 度的结点有 2 个，4 度的结点有 2 个，所以
27、剩余 203 24 26 度。又因为其余的结点度数为 2，所以 6 23 个。所以 3 度的结点有 2 个，4 度的结点有 2 个，2 度的结点有 3 个，共 7 个结点。练习 4：设无向图中有 6 条边，3 度与 5 度结点各 1 个，其余的都是 2 度结点，问该图中有几个结点？解析：根据握手定理，图中所有结点的度数之和等于边数的2 倍。因为有 6 条边，所以图中所有结点的度数之和为6 212 度。因为 3 度的结点有 1 个，5 度的结点有 1 个，所以剩余 123 15 14 度。又因为其余的结点度数为 2，所以 4 22 个。所以 3 度的结点有 1 个，5 度的结点有 1 个，2 度
28、的结点有 2 个，共 4 个结点。论包括图的基本概念图的连通性与连通度图的矩阵表示等经常涉及到的题型有已知点集和边集画图求结点的度数画补图握手定理计算题强分图连通单向分图连通弱分图连通的判断求点割集割点边割集割边无向简单图已知点集和边集元素称为顶点或结点其中称为边集其元素称为无向边简称为边一个有向图是一个有序的二元组记作其中称为顶点集其元素称为顶点或结点其中称为边集其元素称为有向边简称为边用图形表示无向图和有向图时用小圆圈表示顶点用顶用表示最大度用表示最小度在有向图中对于任何结点出度就是以其为始点的边的条数入度就是以其为终点的边的条数出度与入度之和称为该结点的度数如果图与图互为补图则它们的顶点
29、集相同且它们的边集的并集等于其完全图的边 10 练习 5：找出图中的强分图、单向分图与弱分图。解析：结点 v1、v2与 v 4 构成的子图中，结点 之间是相互连通的，并且没有包含其更大的强连通 子图，所以是强分图。结点 v1、v2、v3与 v4构成的子图中，任何结点 偶对中，至少从一个结点到另一个结点是可达的，并 且没有包含其更大的单向连通图，所以是单向分图。强分图和单向分图也是弱分图。练习 6：找出图中的强分图、单向分图与弱分图。解析：图中结点 v1，v2，v3，v4导出的子图是强分图。结点 v1，v2，v3，v4，v 5导出的子图是单向分图。强分图和单向分图也是弱分图。练习 7：（2009
30、 年 10 月试卷第 4 题）图 G 如图一所示，以下说法正确的是()A(a,d)是割边 B(a,d)是边割集 C(a,d),(b,d)是边割集 D(b,d)是边割集 V1 V2 V3 V4 V5 V1 V2 V4 V1 V2 V3 V4 V1 V2 V3 V4 V5 论包括图的基本概念图的连通性与连通度图的矩阵表示等经常涉及到的题型有已知点集和边集画图求结点的度数画补图握手定理计算题强分图连通单向分图连通弱分图连通的判断求点割集割点边割集割边无向简单图已知点集和边集元素称为顶点或结点其中称为边集其元素称为无向边简称为边一个有向图是一个有序的二元组记作其中称为顶点集其元素称为顶点或结点其中称为
31、边集其元素称为有向边简称为边用图形表示无向图和有向图时用小圆圈表示顶点用顶用表示最大度用表示最小度在有向图中对于任何结点出度就是以其为始点的边的条数入度就是以其为终点的边的条数出度与入度之和称为该结点的度数如果图与图互为补图则它们的顶点集相同且它们的边集的并集等于其完全图的边 11 图一 解题过程 C 选项 A，不对 去掉边（a，d）后，图依然连通。而且（a，d）是集合。选项 B，不对 去掉边（a，d）后，图依然连通。选项 C，正确 去掉边（a，d）和（b，d）后，图就不连通了。选项 D，不对 去掉边（b，d）后，图依然连通。练习 8：（2010 年 1 月试卷第 4 题）图 G 如图一所示，
32、以下说法正确的是()Aa 是割点 Bb,c是点割集 Cb,d是点割集 Dc是点割集 图一 解题过程 B 选项 A，不对 去掉点 a 和其连接的边后，图依然连通。选项 B，正确 去掉点 b、点 c 和其连接的边后，图就不连通了。选项 C，不对 去掉点 b、点 d 和其连接的边后，图依然连通。选项 D，不对 去掉点 c 和其连接的边后，图依然连通。练习 9：（2009 年 1 月试卷第 3 题）设图 G 的邻接矩阵为 论包括图的基本概念图的连通性与连通度图的矩阵表示等经常涉及到的题型有已知点集和边集画图求结点的度数画补图握手定理计算题强分图连通单向分图连通弱分图连通的判断求点割集割点边割集割边无向
33、简单图已知点集和边集元素称为顶点或结点其中称为边集其元素称为无向边简称为边一个有向图是一个有序的二元组记作其中称为顶点集其元素称为顶点或结点其中称为边集其元素称为有向边简称为边用图形表示无向图和有向图时用小圆圈表示顶点用顶用表示最大度用表示最小度在有向图中对于任何结点出度就是以其为始点的边的条数入度就是以其为终点的边的条数出度与入度之和称为该结点的度数如果图与图互为补图则它们的顶点集相同且它们的边集的并集等于其完全图的边 12 0101010010000011100100110 则 G 的边数为()A6 B5 C4 D3 证明过程 B 选项 A，不对 因为无向图的邻接矩阵的上三角矩阵数字之和为
34、5，所以边数为 5。选项 B，正确 因为无向图的邻接矩阵的上三角矩阵数字之和为5，所以边数为 5。选项 C，不对 因为无向图的邻接矩阵的上三角矩阵数字之和为5，所以边数为 5。选项 D，不对 因为无向图的邻接矩阵的上三角矩阵数字之和为5，所以边数为 5。练习 10：（2009 年 1 月试卷第 18 题）图 G=，其中 V=a,b,c,d,e，E=(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(c,d),(d,e)，试（1）画出 G 的图形；（2）写出 G 的邻接矩阵；解题过程（1）先根据 G 的结点集画出图中的5 个结 点，再根据边集，在邻接的结点间将边画出。（2）
35、图中有 5 个结点，则 G 的邻接矩阵为 5 5 矩阵，按结点的序号排序，根据结点间的邻 接关系，确定邻接矩阵中的对应数值。a b c d e c a b d a b c d e e 0111110110110011100110110论包括图的基本概念图的连通性与连通度图的矩阵表示等经常涉及到的题型有已知点集和边集画图求结点的度数画补图握手定理计算题强分图连通单向分图连通弱分图连通的判断求点割集割点边割集割边无向简单图已知点集和边集元素称为顶点或结点其中称为边集其元素称为无向边简称为边一个有向图是一个有序的二元组记作其中称为顶点集其元素称为顶点或结点其中称为边集其元素称为有向边简称为边用图形表示无向图和有向图时用小圆圈表示顶点用顶用表示最大度用表示最小度在有向图中对于任何结点出度就是以其为始点的边的条数入度就是以其为终点的边的条数出度与入度之和称为该结点的度数如果图与图互为补图则它们的顶点集相同且它们的边集的并集等于其完全图的边