2025年离散数学形成性考核作业

离散数学图论部分综合练习辅导本次活动是本学期的第二次活动(

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，故有 82=4条边

2．设图 G＝，则下列结论成立的是 ( )．A．deg(V)=2E B．deg(V)=EC． ∑v ∈Vdeg(v)=2|E| D． ∑v ∈Vdeg(v)=|E|对的答案：Ccabedf该题重要是检查大家对握手定理掌握的状况

复习握手定理：定理 3

1 设 G 是一种图，其结点集合为 V，边集合为 E，