10秋作业4(04任务)：图论部分概念及性

图论基础知识的名词解释图论是数学的一个分支，研究图的属性和关系。

图是由节点和节点之间的边组成的抽象模型，被广泛应用于计算机科学、网络分析、医学和社会科学等领域。

下面，我们将解释一些图论中常用的基础概念和术语。

1. 图 (Graph)图是图论研究的基本对象，由一组节点和连接这些节点的边组成。

节点也被称为顶点 (Vertex)，边则是节点之间的连接线。

图可以分为有向图 (Directed Graph) 和无向图 (Undirected Graph) 两种类型。

在有向图中，边有方向，从一个节点指向另一个节点；而在无向图中，边没有方向，节点之间的关系是双向的。

2. 顶点度数 (Degree of a Vertex)顶点度数指的是一个顶点与其他顶点相邻的边的数量。

在无向图中，顶点度数即与该顶点相连的边的数量；在有向图中，则分为入度 (In-degree) 和出度 (Out-degree)。

入度表示指向该节点的边的数量，而出度表示从该节点出发的边的数量。

3. 路径 (Path)路径指的是通过边连接的一系列节点，形成的顺序序列。

路径的长度是指路径上边的数量。

最短路径 (Shortest Path) 是指连接两个节点的最短长度的路径。

最短路径算法被广泛应用于计算机网络中的路由选择和地图导航系统中的路径规划。

4. 连通图 (Connected Graph)连通图是指图中的任意两个节点之间都存在路径的图。

如果一个图不是连通图，那么它可以被分割为多个连通分量 (Connected Component)。

连通图在社交网络分析和传感器网络等领域中具有重要的应用。

5. 完全图 (Complete Graph)完全图是指任意两个节点之间都存在边的图。

在完全图中，每对节点之间都有一条边相连。

n个节点的完全图有n(n-1)/2条边。

完全图经常用于描述需要互相交流的问题，如计算机网络中的通信。

6. 树 (Tree)树是一种无环连通图，其中任意两个节点之间有且仅有一条路径相连。

离散数学作业5离散数学图论部分形成性考核书面作业（参考答案）本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。

并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 ．解 设G 有x 条边，则由握手定理，112233442x ⨯+⨯+⨯+⨯=，15x =答 152．设给定图G (如右由图所示)，则图G 的点割集是 ．答 {f }、{c ,e }3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 等于边数的两倍．答 的度数之和4．无向图G 存在欧拉回路，当且仅当G 连通且 ． 答 G 的结点度数都是偶数5．设G=<V ，E >是具有n 个结点的简单图，若在G中每一对结点度数之和大于等于，则在G中存在一条汉密尔顿路．答n-16．若图G=<V, E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为．答W≤ |S|7．设完全图Kn 有n个结点(n≥2)，m条边，当时，Kn中存在欧拉回路．答n为奇数8．结点数v与边数e满足关系的无向连通图就是树．答e=v-19．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去条边后使之变成树．答 410．设正则5叉树的树叶数为17，则分支数为i = ．答4（定理5.2.1：(m-1)i=t-1）二、判断说明题（判断下列各题，并说明理由．）1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．解错误．只有当G是连通图且其结点度数均为偶数时，图G才存在一条欧拉回路．2．如下图所示的图G存在一条欧拉回路．解错误．因为图G有两个奇数度（3度）结点，所以不存在欧拉回路．3．如下图所示的图G不是欧拉图而是汉密尔顿图．图G解正确．图G有4个3度结点a，b，d，f，所以图G2不是欧拉图．图G2有汉密尔顿回路abefgdca，所以图G2是汉密尔顿图．4．设G是一个有7个结点16条边的连通简单图，则G为平面图．解错误．由定理4.3.3知，若G有v个结点e条边，且v≥3，则e≤3v-6．但本题中，16≤3×7-6不成立．5．设G是一个连通平面图，且有6个结点11条边，则G有7个面．解正确．由欧拉定理，连通平面图G的结点数为v，边数为e，面数为r，则v-e+r=2．于是有r=2-v+e=2-6+11=7．三、计算题1．设G=<V，E>，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试(1) 给出G的图形表示；(2) 写出其邻接矩阵；(3) 求出每个结点的度数；(4) 画出其补图的图形．解（1）G的图形为：（2）图G的邻接矩阵为：0010000110110110110100110A ⎛⎫⎪⎪ ⎪= ⎪⎪ ⎪⎝⎭（3）图G 的每个结点的度数为：1deg()1v =，2deg()2v =，3deg()4v =，4deg()3v =，5deg()2v =． （4）图G 的补图为：2．图G =<V , E >，其中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，试（1）画出G 的图形； （2）写出G 的邻接矩阵； （3）求出G 权最小的生成树及其权值． 解 （1）G 的图形如左下图：（2）G 的邻接矩阵为：0110110011100110110111110A ⎛⎫⎪⎪ ⎪= ⎪⎪ ⎪⎝⎭（3）图G 有5个结点，其生成树有4条边，用Kruskal 算法求其权最小的生成树T：第1步，取具最小权1的边(a,c)；第2步，取剩余边中具最小权1的边(c,e)；第3步，取剩余边中不与前2条边构成回路的具最小权2的边(a,b)；第4步，取剩余边中不与前3条边构成回路的具最小权3的边(b,d)．所求最小生成树T如右下图，其权为()11237W T=+++=．3．已知带权图G如右图所示．(1) 求图G的最小生成树；(2)计算该生成树的权值．解（1）图G有6个结点，其生成树有5条边，用Kruskal算法求其权最小的生成树T：第1步，取具最小权1的边；第2步，取剩余边中具最小权2的边；第3步，取剩余边中不与前2条边构成回路的具最小权3的边；第4步，取剩余边中不与前3条边构成回路的具最小权5的边；第5步，取剩余边中不与前4条边构成回路的具最小权7的边．所求最小生成树T如右图．（2）该最小生成树的权为()1235718W T=++++=．4．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．解所求最优二叉树T如下图：所求最优二叉树T 的权为：()(23)55473172311131w T =+⨯+⨯+⨯+⨯+⨯=四、证明题1．设G 是一个n 阶无向简单图，n 是大于等于3的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等．证明 设,G V E =<>，,G V E '=<>．则E '是由n 阶无向完全图n K 的边删去E 所得到的．所以对于任意结点u V ∈，u 在G 和G 中的度数之和等于u 在n K 中的度数．由于n 是大于等于3的奇数，从而n K 的每个结点都是偶数度的（ 1 (2)n -≥度），于是若u V ∈在G 中是奇数度结点，则它在G 中也是奇数度结点．故图G 与它的补图G 中的奇数度结点个数相等．2．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2k条边才能使其成为欧拉图．证明 由定理3.1.2知，k 必为偶数．要使这k 个奇数度结点变成偶数度结点，从而使图G 变成欧拉图，可在每两个奇数度结点间添加一条边．故在图G 中至少要添加2k条边才能使其成为欧拉图．。