图论及其应用(20)

电子科技大学研究生试题《图论及其应用》(参考答案)考试时间：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 ）AC DA B CD6．下列图中，不是偶图的是（ 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 13图G由上面两式可得：n 1=n 2+2n 3+…+(k -1)n k七．证明：(8分) 设G 是具有二分类(X,Y)的偶图，证明(1)G 不含奇圈；（2）若|X |≠|Y |，则G 是非哈密尔顿图。

图论及其应用班级：图论1班学院：软件学院学号：2014110993姓名：张娇图论从诞生至今已近300年，但很多问题一直没有很好地解决。

随着计算机科学的发展，图论又重新成为了人们研究讨论的热点，图形是一种描述和解决问题直观有效的手段，这里给出图论在现实生活中的一些应用。

虽然最早的图论问题追溯1736年(哥尼斯堡七桥间题)，而且在19世纪关于图论的许多重要结论已得出。

但是直到20世纪20年代图论才引起广大学者的注意并得以广泛接受和传播。

图论即形象地用一些点以及点与点之间的连线构成的图或网络来表示具体问题。

利用图与网络的特点来解决系统中的问题，比用线性规划等其他模型来求解往往要简单、有效得多。

图论就是研究图和网络模型特点、性质和方法的理论。

图论在许多领域,诸如物理、化学、运筹学、计算机科学、信息论、控制论、网络理论、社会科学以及经济管理等各方面都有广泛的应用,它已经广泛地应用于实际生活、生产和科学研究中。

下面对最大流问题进行探究。

最大流问题主要探究最大流问题的Ford-Fulkerson解法。

可是说这是一种方法，而不是算法，因为它包含具有不同运行时间的几种实现。

该方法依赖于三种重要思想：残留网络，增广路径和割。

在介绍着三种概念之前，我们先简单介绍下Ford-Fulkerson方法的基本思想。

首先需要了解的是Ford-Fulkerson是一种迭代的方法。

开始时，对所有的u,v属于V，f(u,v)=0(这里f(u,v)代表u到v的边当前流量)，即初始状态时流的值为0。

在每次迭代中，可以通过寻找一个“增广路径”来增加流值。

增广路径可以看做是从源点s到汇点t之间的一条路径，沿该路径可以压入更多的流，从而增加流的值。

反复进行这一过程，直到增广路径都被找出为止。

举个例子来说明下，如图所示，每条红线就代表了一条增广路径，当前s到t的流量为3。

当然这并不是该网络的最大流，根据寻找增广路径的算法我们其实还可以继续寻找增广路径，最终的最大流网络如下图所示，最大流为4。

图和子图 图和简单图图 G = (V, E)V ---顶点集，ν---顶点数12ε E ---边集， ε---边数例。

左图中， V={a, b,......,f}, E={p,q, ae, af,......,ce, cf} 注意， 左图仅仅是图G 的几何实现（代表）， 它们有无穷多个。

真正的 图G 是上面所给出式子，它与顶点的位置、边的形状等无关。

不过今后对两者将经常不加以区别。

称 边 ad 与顶点 a (及d) 相关联。

也称 顶点 b(及 f) 与边 bf 相关联。

称顶点a 与e 相邻。

称有公共端点的一些边彼此相邻，例如p 与af 。

环（loop ，selfloop ）：如边 l 。

棱（link ）：如边ae 。

重边：如边p 及边q 。

简单图：（simple graph ）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。

一条边的端点：它的两个顶点。

记号：νε()(),()().G V G G E G ==。

习题1.1.1 若G 为简单图，则εν≤⎛⎝ ⎫⎭⎪2 。

1.1.2 n ( ≥ 4 )个人中，若每4人中一定有一人认识其他3人，则一定有一 人认识其他n-1人。

同构在下图中， 图G 恒等于图H , 记为 G = H ⇔ VG)=V(H), E(G)=E(H)。

图G 同构于图F ⇔ V(G)与V(F), E(G)与E(F)之间 各 存在一一对应关系，且这二对应关系保持关联关系。

记为 G ≅F。

注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。

de f G = (V , E )yz w cG =(V , E )w cyz H =(V ’, E ’)’a ’c ’y ’e ’z ’F =(V ’’, E ’’)注 判定两个图是否同构是NP-hard 问题。

完全图(complete graph) Kn空图（empty g.） ⇔ E = ∅ 。

V’ ( ⊆ V) 为独立集 ⇔ V’中任二顶点都互不相邻。

图论及其应用习题答案图论及其应用习题答案图论是数学的一个分支，研究的是图的性质和图之间的关系。

图是由节点和边组成的，节点表示对象，边表示对象之间的关系。

图论在计算机科学、电子工程、物理学等领域有着广泛的应用。

下面是一些图论习题的解答，希望对读者有所帮助。

1. 问题：给定一个无向图G，求图中的最大连通子图的节点数。

解答：最大连通子图的节点数等于图中的连通分量个数。

连通分量是指在图中，任意两个节点之间存在路径相连。

我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，统计连通分量的个数。

2. 问题：给定一个有向图G，判断是否存在从节点A到节点B的路径。

解答：我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，查找从节点A到节点B的路径。

如果能够找到一条路径，则存在从节点A到节点B的路径；否则，不存在。

3. 问题：给定一个有向图G，判断是否存在环。

解答：我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，同时记录遍历过程中的访问状态。

如果在搜索过程中遇到已经访问过的节点，则存在环；否则，不存在。

4. 问题：给定一个加权无向图G，求图中的最小生成树。

解答：最小生成树是指在无向图中，选择一部分边，使得这些边连接了图中的所有节点，并且总权重最小。

我们可以使用Prim算法或Kruskal算法来求解最小生成树。

5. 问题：给定一个有向图G，求图中的拓扑排序。

解答：拓扑排序是指将有向图中的节点线性排序，使得对于任意一条有向边(u, v)，节点u在排序中出现在节点v之前。

我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，同时记录节点的访问顺序，得到拓扑排序。

6. 问题：给定一个加权有向图G和两个节点A、B，求从节点A到节点B的最短路径。

解答：我们可以使用Dijkstra算法或Bellman-Ford算法来求解从节点A到节点B的最短路径。

这些算法会根据边的权重来计算最短路径。

电子科技大学研究生试题《图论及其应用》(参考答案)考试时间：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 )ABC5.下列图中，是可平面图的图的是(B )6. 下列图中，不是偶图的是(B )7. 下列图中，存在完美匹配的图是(B )三. 作图(6分)1. 画出一个有欧拉闭迹和哈密尔顿圈的图；2. 画出一个有欧拉闭迹但没有哈密尔顿圈的图;3. 画出一个没有欧拉闭迹但有哈密尔顿圈的图;四. (10分)求下图的最小生成树，并求其最小生成树的权值之和。

解：由克鲁斯克尔算法的其一最小生成树如下图：权和为：20.五. (8分)求下图G 的色多项式P k (G).解：用公式P k (G e) P k (G) P 「(G?eh 可得G 的色多项式：P k (G) (k )5 3(k )4 侏)3、k(k 1)2(k 2)(k 3)。

六. (10分)一棵树有n 图个顶点的度数为2, n a 个顶点的度数为3,…，m 个顶点的度数为k ，而其余顶点的度数为1,求1度顶点的个数。

解：设该树有n 1个1度顶点，树的边数为 m.一方面：2m=n+2n 2+…+kn k另一方面： m= m+n 2+…+n k -1 解:由上面两式可得：n 1=门2+2皿+…+(k-1)n k七证明：(8分)设G是具有二分类(X,Y)的偶图，证明(1)G不含奇圈；(2) 若|X |工| Y |，则G是非哈密尔顿图。

图论的基本概念和应用图论是数学中的一个重要分支，研究的是图的性质和图之间的关系。

图论在计算机科学、网络科学、运筹学等领域有着广泛的应用。

本文将介绍图论的基本概念和一些常见的应用。

图的定义图是由节点（顶点）和边组成的一种数据结构。

节点表示对象，边表示对象之间的关系。

图可以分为有向图和无向图两种类型。

有向图有向图中，边是有方向的，表示从一个节点到另一个节点的关系。

如果从节点A到节点B存在一条边，那么我们称节点A指向节点B。

无向图无向图中，边是没有方向的，表示两个节点之间的关系。

如果两个节点之间存在一条边，那么我们称这两个节点是相邻的。

图的表示方法图可以用多种方式进行表示，常见的有邻接矩阵和邻接表两种方法。

邻接矩阵邻接矩阵是一个二维数组，其中行和列分别表示图中的节点，数组元素表示节点之间是否存在边。

如果节点i和节点j之间存在边，则邻接矩阵中第i行第j列的元素为1，否则为0。

邻接表邻接表是一种链表的形式，其中每个节点都有一个链表，链表中存储了与该节点相邻的节点。

邻接表更加节省空间，适用于稀疏图。

图的遍历图的遍历是指从图中的某个节点出发，按照一定规则依次访问图中的所有节点。

常见的图遍历算法有深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）深度优先搜索是一种递归的遍历算法，从起始节点开始，沿着一条路径尽可能深入地访问图中的节点，直到无法继续深入为止，然后回溯到上一个节点，继续访问其他未被访问过的节点。

广度优先搜索（BFS）广度优先搜索是一种非递归的遍历算法，从起始节点开始，按照距离起始节点的距离逐层访问图中的节点。

首先访问起始节点，然后访问与起始节点相邻的所有节点，再访问与这些相邻节点相邻的所有未被访问过的节点，以此类推。

图的应用图论在许多领域都有着广泛的应用，下面介绍几个常见的应用场景。

社交网络分析社交网络是一个典型的图结构，其中节点表示用户，边表示用户之间的关系。

通过对社交网络进行图论分析，可以研究用户之间的关系、社区发现、信息传播等问题。