深度优先遍历
一、实验目的
了解深度优先遍历的基本概念以及实现方式。
二、实验内容
1、设计一个算法来对图的进行深度优先遍历；
2、用C语言编程来实现此算法。用下面的实例来调试程序：
三、使用环境
Xcode编译器
四、编程思路
深度优先遍历图的方法是，从邻接矩阵出发：访问顶点v；依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；构造一个遍历辅助矩阵visited[]进行比较若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止，并将顶点信息存储在数组Q[]里面。反复搜索可以通过使用函数的嵌套来实现。
五、调试过程
1.程序代码：
//为方便调试，程序清晰直观删除了邻接矩阵的构造函数，
//并且修改了main()函数，只保留了DFS函数
#include
#define N 4 //定义顶点数
int a[N][N]=
{
{0,1,1,1}
,{1,0,0,0}
,{1,0,0,1}
,{1,0,0,1}
}; //邻接矩阵由之前程序函给出
int visited[N]={0}; //遍历比较的辅助矩阵，初始化为0矩阵int Q[N]; //用来存储各个顶点的信息
static int last=-1;
void DFS(int G[][N], int s)
{
visited[s] = 1;
Q[++last]=s;
for (int i=0;i { if (G[s][i]==1) { if(visited[i] == 0) DFS(G,i); //函数嵌套，完成一次搜索，指向下一个顶点 } } } int main() { DFS(a,0); printf("深度优先搜索为\n"); for (int i=0;i printf("%d ",Q[i]+1); return 0; }2．运行窗口： 输出结果为各顶点按深度优先遍历的排序。 第三章 1.证明： 必要性： v 是连通图G 的割边， 则 ， 至少有两个连通 分支。设其中一个连通分支顶点集合为V1,另外连通分支顶点集合为V2,即V1与V2构成V 的划分。 对于任意的u ∈V1, v ∈V2，如果割边e 不在某一条（u ，v ）路上，那么，该路也是连接G-e 中的u 与v 的路，这与u,v 处于G-v 的不同分支矛盾。 “充分性” 若e 不是图G 的割边，那么G-v 连通，因此在G-v 中存在u,v 路，当然也是G 中一条没有经过边e 的u,v 路。矛盾。 7.证明： v 是单图G 的割点，则G-v 至少两个连通分支。现任取 , 如果x,y 在G-v 的同一分支中，令u 是与x,y 处于不同分支的点，那么，通过u ，可说明，x 与y 在G-v 的补图中连通。若x,y 在G-v 的不同分支中，则它们在G-v 的补图中邻接。所以，若v 是G 的割点，则v 不是其补图的割点。 9.连通图G 的一个子图B 称为是G 的一个块，如果(1), 它本身是块；(2), 若没有真包含B 的G 的块存在。 又由于对于阶数至少是3的 ()()G e G ωω-> 图G是块当且仅当G无环并且任意两点都位于同一圈上。根据题意，对于阶数至少是3的图G，由于G没有偶圈，所以G的每个块的点可以在奇圈上，如果不在奇圈上，则块只能是K2，否则如果不是K2的话，该子图将存在割点，该子图就不是块。得证。 16.（1） （2） （3） 第四章3. （1）既是欧拉闭迹又是哈密尔顿圈 （2） （3） （4） 7.由于图没有奇度顶点，所以是欧拉图，又定理1可得，图G的边集可以划分为圈C1，C2，。。。。Cm，所以E（G）可以表示成C1，C2.。。Cm的并。 10.若图不是二连通，则存在割点，由于哈密尔顿图不存在割点，因而G是非哈密尔顿图。 若G是具有二分类（X,Y）的偶图，且|X|不等于|Y|，设X中所有点为x1，x2.。。。。xm，Y中的所有点为y1，y2.。。。。yn，若存在哈密尔顿图，则在哈密尔顿圈中必然存在X中的点与Y中的点相互交替出现，但是|X|不等于|Y|，则必然出现某两个点同属于|X|或者|Y|，但是G是偶图，属于同一集合的这样的两个点不可以相连，所以存在哈密尔顿圈矛盾，因而不存在哈密尔顿圈。 12. 证明：在G之外加上一个新点v,把它和G的其余各点连接得图G1 目录 第一章图的基本概念 (2) 二路和连通性 (4) 第二章树 (4) 第三章图的连通度 (6) 第四章欧拉图与哈密尔顿图 (8) 一，欧拉图 (8) 二．哈密尔顿图 (10) 第五章匹配与因子分解 (14) 一．匹配 (14) 二．偶图的覆盖于匹配 (15) 三．因子分解 (16) 第六章平面图 (20) 二．对偶图 (24) 三．平面图的判定 (25) 四．平面性算法 (28) 第七章图的着色 (34) 一．边着色 (34) 二．顶点着色 (35) 第九章 有向图 (40) 二 有向树 (41) 第一章 图的基本概念 1. 点集与边集均为有限集合的图称为有限图。 2. 只有一个顶点而无边的图称为平凡图。 3. 边集为空的图称为空图。 4. 既没有环也没有重边的图称为简单图。 5. 其他所有的图都称为复合图。 6. 具有二分类（X, Y ）的偶图（或二部图）：是指该图的点集可以分解为两个（非空）子 集 X 和 Y ，使得每条边的一个端点在 X 中，另一个端点在Y 中。 7. 完全偶图：是指具有二分类（X, Y ）的简单偶图，其中 X 的每个顶点与 Y 的每个顶点 相连，若 |X|=m ，|Y|=n ，则这样的偶图记为 Km,n 8. 定理1 若n 阶图G 是自补的（即 ），则 n = 0, 1（mod 4） 9. 图G 的顶点的最小度。 10. 图G 的顶点的最大度。 11. k-正则图: 每个点的度均为 k 的简单图。 例如,完全图和完全偶图Kn,n 均是正则图。 12. 推论1 任意图中，奇点的个数为偶数。 ()G δ()G ? 13. 14.频序列：定理4 一个简单图G的n个点的度数不能互不相同。 15.定理5 一个n阶图G相和它的补图有相同的频序列。 16. 17. 18.对称差：G1△G2 = (G1∪G2) - (G1∩G2) = (G1-G2)∪(G2-G1) 19.定义：联图在不相交的G1和G2的并图G1+G2中，把G1的每个顶点和G2的每个 顶点连接起来所得到的图称为G1和G2的联图，记为G1∨G2 20.积图：积图设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u = (u1,u2)和v = (v1,v2)，当(u1 = v1和u2 adj v2) 或(u2 = v2 和u1 adj v1) 时就把u 和v 连接起来所得到的图G称为G1和G2积图。记为G = G1×G2 设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u = (u1,u2)和v = (v1,v2)，当(u1 adj v1) 或(u1= v1 和u2 adj v2) 时就把u 和v 连接起来所得到的图G称为G1和G2的合成图。记为G=G1[G2]。 电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k ?2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。 图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3． 下列图中，是欧拉图的是（ D ） 4． 下列图中，不是哈密尔顿图的是（B ） 5． 下列图中，是可平面图的图的是（B ） A C D A B C D 6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。 解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8分)求下图G 的色多项式P k (G). 解：用公式 (G P k -G 的色多项式： )3)(3)()(45-++=k k k G P k 。 六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。 解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 v v 1 3 图G #include 离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2018年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是15． 2．设给定图G (如右由图所示)，则图G 的点割集是 {f}． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点度数之和等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且等于出度． 5．设G= 《图论及其应用》大作业 指导老师郝荣霞 知行1503 徐鹏宇 15291200 2.1.9证明：若G是森林且恰有2k个奇点，则在G中有k条边不重的路P1,P2......P K,使得E(G)=E(P1) E(P2) ...... E(P K)。 证明： 对奇点数k使用数学归纳法。 ①当k=1时，G是森林，且有且只有2个奇点 ?G只能为一颗树，且G的所有奇度顶点为两个1度顶点 ?G是一条路 ?满足题设 ②假设当k=t时，结论成立。接下来考虑k=t + 1时的情况。 在G中一个分支中取两个叶子点u与v，令P是连接该两个顶点的唯一路。 由于P上除u，v以外的点均被P经过两次，即G-P后除u，v以外的点奇偶性不变。 ?则G–P是有2t个奇度顶点的森林 ?由归纳假设知，G–P可以分解为t条边不重合的路之并，即E(G-P)=E(P1) E(P2) ...... E(P t)。 ?则G可分解为t+1条边不重合的路之并，即E(G)=E(P1) E(P2) ...... E(P t) E(P)。 ?即证。 2.4.4证明：若e 是K n 的边，则τ（K n -e ）=（n-2）n n-3 证明： 由定理2.9：τ（K n ）=n n-2 由于τ（K n -e ）=τ（K n ）-τ（含有e 的生成树棵树） 现在需要求含有e 的生成树棵树， τ（含有e 的生成树棵树）=)1(2 1n 1-n 2-n n n ）（=2n n-3 τ（K n -e ）=τ（K n ）-τ（含有e 的生成树棵树）=（n-2）n n-3 3.2.4证明：不是块的连通图至少有两个块，其中每个恰有一个割点。 证明： 设G 为不是块的连通图，由于G 连通且不是块 ?G 有割点 ①当G 只有1个割点v 时，延割点分开，G1，G2内无割点，且连通，由块的定义知?G1,G2是块，且分别含一个割点v 。 ②当G 含有2个及2个以上割点时，取相距距离最远的两个割点u 和v ，此时分G 为三部分G1,G2,G3 。 由于u ，v 是相距最远的两割点?G1和G3不含割点。 又由于G 连通，G1,G3为G 的一部分?故G1,G3连通。 ?G1，G3内无割点，且连通。 ?G1，G3是块，且分别含割点u ，v 。 ?即证 一．实验目的 熟悉图的存储结构，掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法，并能运用图的深度优先搜索遍历一个图，对其输出。 二．实验原理 深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有与v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 图的邻接表的存储表示： #define MAX_VERTEX_NUM 20 #define MAXNAME 10 typedef char VertexType[MAXNAME]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 三．实验内容 编写LocateVex函数，Create函数，print函数，main函数，输入要构造的图的相关信息，得到其邻接表并输出显示。 四。实验步骤 1）结构体定义,预定义，全局变量定义。 #include"stdio.h" #include"stdlib.h" #include"string.h" #define FALSE 0 #define TRUE 1 #define MAX 20 typedef int Boolean; #define MAX_VERTEX_NUM 20 《运筹学》试题样卷（一） 一、判断题（共计10分，每小题1分，对的打√，错的打X ） 1. 无孤立点的图一定是连通图。 2. 对于线性规划的原问题和其对偶问题，若其中一个有最优解， 另一个也一定有最优解。 3. 如果一个线性规划问题有可行解，那么它必有最优解。 4．对偶问题的对偶问题一定是原问题。 5．用单纯形法求解标准形式（求最小值）的线性规划问题时，与0 >j σ对应的变量 都可以被选作换入变量。 6．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷 多个最优解。 7. 度为0的点称为悬挂点。 8. 表上作业法实质上就是求解运输问题的单纯形法。 9. 一个图G 是树的充分必要条件是边数最少的无孤立点的图。 二、建立下面问题的线性规划模型（8分） 某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日；春夏季4000人日。如劳动力本身用不了时可外出打工，春秋季收入为25元 / 人日，秋冬季收入为20元 / 人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春夏季为50人日，年净收入900元 / 每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入2元 / 每只鸡。农场现有鸡舍允许最多养1500只鸡，牛栏允许最多养200头。三种作物每年需要的人工及收入情况如下表所示： 试决定该农场的经营方案，使年净收入为最大。 三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中54,x x 为 (1)写出原线性规划问题；（4分） (2)写出原问题的对偶问题；（3分） (3)直接由上表写出对偶问题的最优解。（1分） 四、用单纯形法解下列线性规划问题（16分） 3212max x x x Z +-= s. t. 3 x 1 + x 2 + x 3 ≤ 60 x 1- x 2 +2 x 3 ≤ 10 x 1+ x 2- x 3 ≤ 20 x 1 , x 2 , x 3 ≥0 五、求解下面运输问题。 （18分） 某公司从三个产地A 1、A 2、A 3 将物品运往四个销地B 1、B 2、B 3、B 4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示： 问：应如何调运，可使得总运输费最小? 六、灵敏度分析（共8分） 线性规划max z = 10x 1 + 6x 2 + 4x 3 s.t. x 1 + x 2 + x 3 ≤ 100 10x 1 +4 x 2 + 5 x 3 ≤ 600 2x 1 +2 x 2 + 6 x 3 ≤ 300 x 1 , x 2 , x 3 ≥ 0 离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝ 图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( ) ． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f 课本习题一： ● 。 证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对"v i v j ? E ((a)),有f (v i v j,),=,u i,u j,?,E,((b)) (1￡ i ￡ 10, 1￡j ￡ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 ● 5.证明：四个顶点的非同构简单图有11个。 证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： m=2： m=3： m=4： (a) v 23 4 (b) m=5： m=6： 因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 ● 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1）不是图序列。 证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列； （6,6,5,4,3,3,1）是图序列 非负整数组12121(,,,),,2n n n i i d d d d d d d m π==≥≥≥=∑L L 是图序列的充要条件是： ? 11 12312(1,1,,1,,,)d d n d d d d d π++=---L L 是图序列 （5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 ● 12.证明：若δ≥2，则G 包含圈。 证明：下面仅对连通图的下的条件下进行证明，不连通的情形可以通过分成若干个连通的情形来证明。设V (G )={V 1，V 2,V 3,?V n },对于G 中的路V 1，V 2,V 3,?V n 若V k 与V 1邻接，则构成一个圈。若V i1，V i2,V i3,?V in 是一条路，由于δ≥2，因此，对于V in ，存在V ik 与之邻接，则V ik ，,?V in V ik 构成一个圈。 ● 17.证明：若G 不连通，则G ?连通。 证明：对于任意的u,v ∈(G ?),若u 与v 属于G 的不同连通分支，显然u 与v 在G ?中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点， 则u 与w ，v 与w 分别在G ?中连通，因此，u 与v 在G ?中连通。 ● 18.证明：若e ∈E(G),则w (G )≤w (G ?e )≤w (G )+1. 证明：若e 为G 的割边，则w (G ?e )= w (G )+1，若e 为G 的非割边，则w (G ?e )=w (G )， 组合数学部分 第1章 排列与组合 例1： 1)、求小于10000的含1的正整数的个数； 2、)求小于10000的含0的正整数的个数； 解：1)、小于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个 2)、“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含的规定，要特别留神。不含0的1位数有19个，2位数有29个，3位数有39个，4位数有49个 不含0小于10000的正整数有() ()73801919999954321=--=+++个含0小于10000的正整数9999－7380=2619个。 例2： 从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？ 解：将[1,300]分成3类： A={i|i ≡1(mod 3)}={1,4,7,…,298}, B={i|i ≡2(mod 3)}={2,5,8,…,299}, C={i|i ≡0(mod 3)}={3,6,9,…,300}. 要满足条件，有四种解法： 1)、3个数同属于A; 2)、3个数同属于B ； 3)、3个数同属于C; 4)、A,B,C 各取一数；故共有3C(100,3)+1003=485100+1000000=1485100。 例3：（Cayley 定理：过n 个有标志顶点的数的数目等于2-n n ） 1）、写出右图所对应的序列； 2）、写出序列22314所对应的序列； 解： 1）、按照叶子节点从小到大的顺序依次去掉节点（包含与此叶子 节点相连接的线），而与这个去掉的叶子节点相邻的另外一个点值则记入序列。如上图所示，先去掉最小的叶子节点②，与其相邻的点为⑤，然后去掉叶子节点③，与其相邻的点为①，直到只剩下两个节点相邻为止，则最终序列为51155.。 2）、首先依据给定序列写出（序列长度+2）个递增序列，即1234567，再将给出序列按从小到大顺序依次排列并插入递增序列得到：7。我们再将给出序列22314写在第一行，插入后的递增序列写在第二行。如下图第一行所示： ??→????? ??--②⑤67112223344522314??→???? ? ??--②⑥11223344672314 ??→????? ??--③②11233447314??→???? ? ??--①③11344714 第四章 3(1).有欧拉闭迹和H圈 (2).有欧拉闭迹但没有H圈 (3).有H圈无欧拉闭迹 (4).无欧拉闭迹且没有H圈 4：证：若G不是H图，由chvatal定理知，G度弱于某个图，故： = 这与题目已知条件相矛盾，故G是H图。 8：证：不失一般性，设G是连通图，是G的2k个奇点，连接，得到，则得到图，则是欧拉图，设C是中 的欧拉闭迹，删除C中的，即可得到k条边不重复的迹，使得 . 10(1)若G不是二连通图，那么G不连通或者有割点u，则w，故G是 非H图。 (2). 若G是具有二分类的偶图，且，若假设则，故 G是非H图。 11：设R是G中的H路，则对于每个真子集S，有w，又： w w，故w. 12：设u是G外一点，将u和G中的每个点连接得到图，则G的度序列为 ，故有题意知，不存在小于的正整数m，使得 ，故由Chvatal定理知，图是H图，则G有 H路。 15：(1)由图的闭包定义可知，构作一个图的闭包，可以通过不断在度和大于等于n的非邻接顶点加边得到。故图的闭包算法如下： 第一步：令； 第二步：在中求顶点，使得： 第三步：如果,则转到第四步；否则，停止，则可得到G 的闭包。 第四步：令，转到第二步。 复杂性分析：由其算法我们可得出其总运算量为： 故该算法能够在多项式时间内被解决，故该算法是一个好算法。 (2).设计算法如下： 第一步：在闭包构造中，将加入的边依次加入次序记为 ，在中任意取出一个H圈，令k=N; 第二步：若不在中，令；否则转到第三步。 第三步：设，令；求中两个相邻点u和v使得， u，v依序排列在上，且有：，令： 第四步：若k=1，转到第五步；否则，令k=k-1,转第二步； 第五步：停止。为G的H圈。 算法的复杂性分析：因为该算法进行了N次循环，每次循环中找到满足要求的邻接顶点u和v至多需要n-3次判断，所以总的运算量：N(n-3)。是一个好算法。 第五章 1：(1)证：k方体有2k个顶点，每个顶点可以用长度为k的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。 若划分k方体的2k个顶点，把坐标之和为偶数的顶点归入X，否则归入Y。显然，X中顶点互不邻接，Y中顶点也如此。所以k方体是偶图。又k方体的每个顶点度数为k,所以k方体是k正则偶图。所以由推论可知：k方体存在完美匹配。 (2).解K 2n 的任意一个顶点有2n-1中不同的方法被匹配。所以K 2n 的不同完美匹 配个数等于(2n-1)K 2n-2,如此推下去，可以归纳出K 2n 的不同完美匹配个数为： (2n-1)!!。同理，K n, n 的不同完美匹配个数为：(n)!。 2：若不然，设M 1与M 2 是树T的两个不同的完美匹配，那么M 1 ΔM 2 ≠Φ,且T[M 1 ΔM 2 ] 每个顶点度数为2，即它存在圈，于是推出T中有圈，矛盾。故一棵树中最多只有一个完美匹配。 7：解：设 作如下四条路： 故其四个生成圈如下： 1 2017年图论课程练习题 一．填空题 1.图1中顶点a 到顶点b 的距离d (a ,b )= 。 a b 9 图1 1 2.已知图G 的邻接矩阵0 11011 01001 1010001011001 0A = ，则G 中长度为2的途径总条数为 。 3.图2中最小生成树T 的权值W (T )= 。 4.图3的最优欧拉环游的权值为 。 12 图 2 2 图3 5.树叶带权分别为1,2,4,5,6,8的最优二元树权值为 。 二．单项选择 1．关于图的度序列，下列说法正确的是( ) (A) 对任意一个非负整数序列来说，它都是某图的度序列； (B) 若非负整数序列12(,,,)n d d d π= 满足1n i i d =∑为偶数，则它一定是图序 列； (C) 若图G 度弱于图H ，则图G 的边数小于等于图H 的边数； (D) 如果图G 的顶点总度数大于或等于图H 的顶点总度数，则图G 度优 于图H 。 2．关于图的割点与割边，下列说法正确的是（ ） (A) 有割边的图一定有割点； (B) 有割点的图一定有割边； (C) 有割边的简单图一定有割点； (D) 割边不在图的任一圈中。 3.设()k G ，()G λ，()G δ分别表示图G 的点连通度，边连通度和最小度。下面说法错误的是( ) 3 (A) 存在图G ，使得()k G =()G δ=()G λ； (B) 存在图G ，使得()()()k G G G λδ<<； (C) 设G 是n 阶简单图，若()2n G δ ≥ ，则G 连通，且()()G G λδ=； (D) 图G 是k 连通的，则G 的连通度为k 。 4.关于哈密尔顿图，下列命题错误的是( ) (A) 彼得森图是非哈密尔顿图； (B) 若图G 的闭包是哈密尔顿图，则其闭包一定是完全图； (C) 若图G 的阶数至少为3且闭包是完全图，则图G 是哈密尔顿图； (D) 设G 是三阶以上简单图，若G 中任意两个不邻接点u 与v ，满足 ()()d u d v n +≥，则G 是哈密尔顿图。 5.下列说法错误的是( ) (A) 有完美匹配的三正则图一定没有割边； (B) 没有割边的三正则图一定存在完美匹配； (C) 任意一个具有哈密尔顿圈的三正则图可以1因子分解； (D) 完全图21n K +是n 个哈密尔顿圈的和。 三、 设无向图G 有10条边，3度与4度顶点各2个，其余顶点度数均小于3，问G 中至少有几个顶点？在最少顶点数的情况下，写出G 的度序列，该度序列是一个图序列吗？。 *问题描述： 建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 1、邻接矩阵表示法: 设G=(V,E)是一个图，其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵： 1，若(Vi,Vj)∈E 或 若图中每个顶点只含一个编号i(1≤i≤vnum)，则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下： type adjmatrix=array[1..vnum,1..vnum]of adj; 利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相联，并容易求得各个顶点的度。 对于无向图，顶点Vi的度是邻接矩阵中第i行元素之和，即 n n D(Vi)＝∑A[i,j]（或∑A[i,j]） j=1 i=1 对于有向图，顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和，顶点Vi 的入度ID(Vi)为第i列元素之和。即 n n OD(Vi)＝∑A[i,j]，OD(Vi)＝∑A[j,i]） j=1j=1 用邻接矩阵也可以表示带权图，只要令 Wij, 若 图论第二次作业Newly compiled on November 23, 2020 图论第二次作业 一、 第四章 （1）画一个有Euler 闭迹和Hamilton 圈的图； （2）画一个有Euler 闭迹但没有Hamilton 圈的图； （3）画一个有Hamilton 圈但没有Euler 闭迹的图； （4）画一个既没有Euler 闭迹也没有Hamilton 圈的图； 解：（1）一个有Euler 闭迹和Hamilton 圈的图形如下： （2）一个有Euler 闭迹但没有Hamilton 圈的图形如下： （3）一个有Hamilton 圈但没有Euler 闭迹的图形如下： （4）一个既没有Euler 闭迹也没有Hamilton 圈的图形如下： 证明：若G 没有奇点，则存在边不重的圈C 1,C 1,···,C m ,使得 )()()()(21m C E C E C E G E ???=。 证明：将G 中孤立点除去后的图记为1G ，则1G 也没有奇点，且2)(1≥G δ，则1G 含圈1C ，在去掉)(11C E G -的孤立点后，得图2G ，显然2G 仍无奇度点，且2)(2≥G δ，从而2G 含圈2C ，如此重复下去，直到圈m C ，且)(m m C E G -全为孤立点为止，于是得到)()()()(21m C E C E C E G E ???=。 证明：若 （1）G 不是二连通图，或者 （2）G 是具有二分类),(Y X 的偶图，这里Y X ≠， 则G 是非Hamilton 图。 证明：（1）因为G 不是二连通图，则G 不连通或者存在割点v ，有2)(≥-v G w ，由相关定理得：若G 是Hamilton 图，则对于v(G)的任意非空顶点集S ，有：S S G w ≤-)(，则该定理得逆否命题也成立，所以可得：若G 不是二连通图，则G 是非Hamilton 图。 （2）因为G 是具有二分类),(Y X 的偶图，又因为Y X ≠，在这里假设Y X ≤，则有X Y X G w >=-)(，也就是说：对于v(G)的非空顶点集S ，有：S S G w >-)(成立，则可以得出G 是非Hamilton 图。 设G 是有度序列),,,(21n d d d ???的非平凡简单图，这里n d d d ≤???≤≤21，证明：若不存在小于2 )1(+n 的正整数m ，使得m d m <且m n d m n -<+-1，则G 有Hamliton 路。 证明：在G 之外加上一个新点v ，把它和G 的其余各点连接，得图G 1： 一、判断题（共计10分，每小题1分，对的打√，错的打X） 1.无孤立点的图一定是连通图。 2.对于线性规划的原问题和其对偶问题，若其中一个有最优解， 另一个也一定有最优解。 3.如果一个线性规划问题有可行解，那么它必有最优解。 4．对偶问题的对偶问题一定是原问题。 5．用单纯形法求解标准形式（求最小值）的线性规划问题时，与 > j σ 对应的变量都可以被选作换入变量。 6．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷 多个最优解。 7. 度为0的点称为悬挂点。 8. 表上作业法实质上就是求解运输问题的单纯形法。 9. 一个图G 是树的充分必要条件是边数最少的无孤立点的图。 二、建立下面问题的线性规划模型（8分） 某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日；春夏季4000人日。如劳动力本身用不了时可外出打工，春秋季收入为25元/ 人日，秋冬季收入为20元/ 人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。 养奶牛时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春夏季为50人日，年净收入900元 / 每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入2元 / 每只鸡。农场现有鸡舍允许最多养1500只 三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中5 4 ,x x 为松弛变量，问题的约束为?形式（共8分） (1)写出原线性规划问题；（4分） (2)写出原问题的对偶问题；（3分） (3)直接由上表写出对偶问题的最优解。（1分） 四、用单纯形法解下列线性规划问题（16分） 3212max x x x Z +-= s. t. 3 x 1 + x 2 + x 3 ≤ 60 x 1- x 2 +2 x 3 ≤ 10 x 1+ x 2- x 3 ≤ 20 x 1, x 2 , x 3 ≥0 五、求解下面运输问题。 （18分） 某公司从三个产地A 1、A 2、A 3 将物品运往四个销地B 1、B 2、B 3、B 4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示： 六、灵敏度分析（共8分） 线性规划max z = 10x 1 + 6x 2 + 4x 3 s.t. x 1 + x 2 + x 3 ≤ 100 10x 1 +4 x 2 + 5 x 3 ≤ 600 2x 1 +2 x 2 + 6 x 3 ≤ 300 x 1 , x 2 , x 3 ≥ 0 的最优单纯形表如下： 08信安专业离散数学期中考试试题 1.设A, B, C, D为4个集合. 已知A?B且C?D.证明: A∪C?B∪D; A∩C?B∩D . (15分) 2.化简以下公式: A∪((B―A)―B) (10分) 3.设R是非空集合A上的二元关系.证明:R∪R-1是包含R的 最小的对称的二元关系. (15分) 4.设A={1,2,…,20},R={ 期中考试试题解答 1.证明: ?x, x∈A∪C x∈A∩C ?x∈A∨x∈C ?x∈A∧x∈C ?x∈B∨x∈D (A?B,C?D) ?x∈B∧x∈D (A?B,C?D) ?x∈B∪D ?x∈B∩D ∴A∪C?B∪D ∴A∩C?B∩D 2.解: A∪((B―A)―B) =A∪((B∩∽A)∩∽B) =A∪(∽A∩(B∩∽B)) =A∪(∽A∩φ) =A∪ф =A . 3.证明:首先证R∪R-1是对称关系. ? 2015电子科技大学 图论考试复习题 关于图论中的图，以下叙述不正确的是 A ．图中点表示研究对象，边或有向边表示研究对象之间的特定关系。 B ．图论中的图，画边时长短曲直无所谓。 C ．图中的边表示研究对象，点表示研究对象之间的特定关系。 D ．图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系。 一个图中最长的边一定不包含在最优生成树内。 下面哪个图形不与完全二分图K 3,3同构？ A ． B ． C ． D ． 有10条边的5顶单图必与K 5同构。 完全二分图K m ,n 的边数是 A ．m B ．n C ．m +n D ．mn 无向完全图K n 的边数为 A ．n B ．n 2 C ．n (n -1) D ．n (n -1)/2 若一个无向图有5个顶点，如果它的补图是连通图，那么这个无向图最多有 条边。 对于两个图，如果顶点数目相等，边数相等，次数相等的顶点数目也相等，则这两个图同构。 有15个顶的单图的边数最多是 A ．105 B ．210 C ．21 D ．45 图G 如右，则dacbeb A ．是G 中的一条道路 B ．是G 中的一条道路但不是行迹 C ．是G 中的一条行迹但不是轨道 D ．不是G 的一条道路 图G 如右，则befcdef A ．是G 的一个圈 B ．是G 的一条道路但不是行迹 C ．是G 的一条行迹但不是轨道 D ．是G 的一条轨道但不是圈 v1 36 7 图G如右图所示，则ω (G)= A．1 B．2 C．7 D．8 下列图形中与其补图同构的是 A．B．C．D． 求下图中顶u0到其余各顶点的最短轨长度。 u0v1=8，u0v2=1，u0v3=4，u0v4=2，u0v5=7，v1v2=7，v1v3=2，v1v6=4，v2v4=2，v2v7=3，v3v5=3，v3v6=6，v4v5=5，v4v7=1， v5v 6 =4，v 5 v7=3，v6v7=6， 请画出6阶3正则图。 请画出4个顶，3条边的所有非同构的无向简单图。 设图G={V(G)，E(G)}其中V ={ a1, a2, a3, a4, a5}，E(G)={(a1, a2)，(a2, a4)，(a3, a1)，(a4, a5)，(a5, a2)}，试给出G的图形表示并画出其补图的图形。 一个图的生成子图必是唯一的。 不同构的有2条边，4个顶的无向简单图的个数为 A．1 B．2 C．3 D．4 画出5个具有5个结点5条边的非同构的无向连通简单图。 u0到v1的最短轨长度为6，u0到v2的最短轨长度为1，u0 到v3的最短轨长度为4，u0到v4的最短轨长度为2，u0到v5的最短轨长度为6 ，u0到v6的最短轨长度为9，u0到v7的最短轨长度为3。图论作业(1)
图论期末考试整理复习资料
电子科技大学研究生试题《图论及其应用》(参考答案)
连通图深度优先遍历
电大离散数学作业答案(图论部分)
图论大作业
图的深度优先遍历实验报告
运筹学期末试题
离散数学图论部分经典试题及答案
电子科技大学-图论第一次作业
图论与组合数学期末复习题含答案
图论第二次作业
电子科技大学2017年图论期末试卷
邻接矩阵表示图深度广度优先遍历
图论第二次作业
运筹学期末试题
集合论图论 期中考试试题及答案
2015电子科技大学_图论期末考试复习题
相关主题
文本预览