*计算机学院*第十章一、基本概念无序对、结点、边、阶、无向图、有向图、邻接点、邻接边、环、孤立结点、零图、平凡图、(n，m)图、简单图、广义图（伪图）、多重图、平行边、赋权图、无权图、结点的度数、出度、入度、正则图、k度正则图、子图、真子图、生成子图、平凡子图、删点子图、删边子图、点诱导子图、边诱导子图、完全图、补图、二部图、完全二部图、图的同构*计算机学院*道路、道路的长度、零道路、简单道路、回路、基本道路、圈、距离、连通图、非连通图、图的支、点割集、基本割集、割点、边割集、基本边割集、割边、连通度、边连通度、可达的、单向连通图、强连通图、弱连通图、强分图、单向分图、弱分图、邻接矩阵、单位矩阵、可达性矩阵*计算机学院*二、基本要求1、熟练掌握图论基本（握手）定理及推论2、熟练掌握邻接矩阵、可达性矩阵的计算方法3、熟练掌握强分图的计算方法4、熟练掌握利用邻接矩阵计算图中道路和回路数目的方法第十一、十二、十三章一、基本概念树、树叶、枝点、生成树、树枝、树补边、最小生成树、有向树、根树、（有序树、子树、二叉树、完全二叉树、最优二叉树）、平面图、面、对偶图、欧拉道路、欧拉图、哈密顿道路、哈密顿圈、哈密顿图*计算机学院*二、基本要求1、熟练掌握树的六个等价命题2、熟练掌握利用Kruskal算法求最小生成树3、熟练掌握判定平面图的三个必要条件4、熟练掌握判定欧拉图和欧拉道路的充分必要条件5、熟练掌握判定哈密顿图和哈密顿道路的几个充分和必要条件设G是一个（n，n+1）的无向图，证明G中存在顶点u，d（u）≥3。证明：反正法，假设,则G的总点度上限为max(Σ(d(u))≤2n，根据握手定理，图边的上限为max(m)≤2n/2=n。与题设m=n+1，矛盾。因此，G中存在顶点u，d（u）≥3。*计算机学院**计算机学院*G2中一共有多少条长度为2的道路？G2中长度为2的通路（含回路）总数为11，其中5条为回路。G2中长度为3的通路（含回路）总数为16，其中3条为回路。v1v3v2v4G2*计算机学院*利用可达性矩阵求右图的所有强分图。解该图的邻接和可达性矩阵为v4v2v5v3v1采用Warshall算法来求可达性矩阵P*计算机学院*P⊙PT这说明，v1在一个强分图中，v2在一个强分图中，v3,v4和v5在一个强分图中，因此该图的所有强分图分别为结点子集{v1},{v2}，{v3,v4,v5}导出的子图。v4v2v5v3v1*计算机学院*证明当每个结点的度数大于等于3时，不存在有7条边的连通简单平面图。证明:(反证法)设图的边数m=7由题意，d(Vi)≥3，Vi为结点则由握手定理，则∴结点的个数不超过4个，而结点个数为4的完全图的边数为6,故应有环或平行边，不是简单连通平面图。*计算机学院*证明：具有6个结点、12条边的简单连通平面图，它的面的度数都是3。证：由欧拉公式，n-m+f=2∴6-12+f=2f=8即面数为8，∵对每个面，其度数≥3∴总面度≥3×8=24∵总面度=2×m=24∴每个面的度数为3*有6个村庄Vi，i=l，2，…，6欲修建道路使村村可通。现已有修建
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
如下带权无向图所示，其中边
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示道路，边上的数字表示修建该道路所需费用，问应选择修建哪些道路可使得任二个村庄之间是可通的且总修建费用最低?要求写出求解过程，画出符合要求的最低费用的道路网络图并计算其费用。*计算机学院**计算机学院*费用=18*计算机学院*设图G是具有6个顶结点、12条边的无向简单图,证明图G是哈密顿图。证明：已知一个图是哈密顿图的充分条件是：图中任意不同两点的度数之和大于等于n。（反证法）假设图G中存在两个结点v1,v2,其度数之和不大于等于6,即d(v1)+d(v2)≤5。*计算机学院*而删去这两个点后,至多删去图G中的5条边。由于图G是具有6个顶点,12条边的无向简单图,删去顶点v1,v2后,得到的子图为:具有4个结点,至少7条边的无向简单图,但这样的无向简单图不存在(4阶无向简单图最多有6条边),由此证明图G中任意不同两点的度数之和大于等于6,图G是哈密顿图。
浙公网安备 33021202002483