离散数学图论部分综合练习辅导本次活动是本学期的第二次活动(.11.18)，重要是针对第二单元图论的重点学习内容进行辅导，方式是通过讲解某些经典的综合练习题目，协助大家深入理解和掌握图论的基本概念和措施。图论作为离散数学的一部分，重要简介图论的基本概念、理论与措施。教学内容重要有图的基本概念与结论、图的连通性与连通度、图的矩阵表达、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等。本次综合练习重要是复习这一部分的重要概念与计算措施，与集合论同样，也安排了五种类型，有单项选择题、填空题，判断阐明题、计算题、证明题。这样的安排也是为了让同学们熟悉期末考试的题型，可以很好地完毕这一部分重要内容的学习。下面分别讲解。一、单项选择题1．设图 G 的邻接矩阵为则 G 的边数为( )．A．5 B．6 C．3 D．4对的答案：D上学期的作业中，有的同学选择答案 B。重要是对邻接矩阵的概念理解不到位。我们复习定义： 定义 设 G=是一种简单图，其中 V={v1，v2，…， vn}，则 n 阶方阵A（G）=（aij）称为 G 的邻接矩阵．其中各元素aij=¿{1 vi v与 j相邻¿¿¿¿而当给定的简单图是无向图时，邻接矩阵为对称的．即当结点 vi与 vj相邻时，结点 vj与 vi也相邻，因此连接结点 vi与 vj的一条边在邻接矩阵的第 i 行第 j 列处和第 j 行第 i 列处各有一种 1，题中给出的邻接矩阵中共有 8 个 1，故有 82=4条边。2．设图 G＝，则下列结论成立的是 ( )．A．deg(V)=2E B．deg(V)=EC． ∑v ∈Vdeg(v)=2|E| D． ∑v ∈Vdeg(v)=|E|对的答案：Ccabedf该题重要是检查大家对握手定理掌握的状况。复习握手定理：定理 3.1.1 设 G 是一种图，其结点集合为 V，边集合为 E，则∑v ∈Vdeg(v)=2|E|3．图 G 如右图所示，如下说法对的的是 ( ) ．A．{(a, d)}是割边B．{(a, d)}是边割集C．{(d, e)}是边割集D．{(a, d) ,(a, c)}是边割集对的答案：C上学期许多同学选择答案 A。重要是对割边、边割集的概念理解不到位。复习割边、边割集的定义： 定义 3.2.9 设无向图 G=为连通图，若有边集 E1E，使图 G 删除了 E1的所有边后，所得的子图是不连通图，而删除了 E1的任何真子集后，所得的子图是连通图，则称 E1 是 G 的一种边割集．若某个边构成一种边割集，则称该边为割边（或桥）假如答案 A 对的，即删除边(a,...
