图论及其算法是什么

A. 简介图论算法

图论101

图论是数学的一个非常广泛的分支，非常适用于现实世界中的问题。 最初，图论是"发明"来解决现实问题的，此后，它像所有其他数学分支一样，被抽象数学家所劫持。

在本教程和后续教程中，我们将介绍一些图论算法及其在python中的实现。 现在，回到主题。

简而言之，图是一组顶点/节点和边。 如果您对" set"不满意，请用collection代替。

在上图中，顶点/节点将是人物。

顶点是图的基本单位。 它几乎可以代表任何实体，通常以圆圈表示。

在上图中，连接人的线是边。

顶点之间的线或连接称为边。 它可以表示顶点之间的任何类型的关系。

边上具有方向的图称为有向图。 它可以用来显示与前辈（从父母到孩子的箭头）或祖先（从孩子到父母的箭头）的关系。

边上没有方向的边的图称为无向图。 它可用于显示双向道路。

边上带有数字的图形，代表交易成本，旅途公平，城市之间的距离等。它可以具有任何类型的边。

没有循环的无向图是一棵树。 在这里，循环意味着只有一种方法可以通过跟随给定其他节点的边缘来到达节点。

一棵树的所有节点都通过一条边连接到其他某个节点，并且有N个节点的N-1个边。

表示图形的方法有很多，最常见的两种是：

假设图中有N个节点。 我们可以使用具有N行和N列的矩阵来表示它，其中该矩阵的行和列将代表一个节点，并且其中的条目代表有向边（有或没有权重）。

它们形成代表行的节点到代表列的节点。 通常，0或无穷大用于表示节点之间没有边缘。 在Python中，邻接矩阵可以表示为：

类似地，对于N个节点的图，我们可以使用邻接表来表示该图，其中节点的所有边都保留在元组列表（节点，权重）中。 在python中，它可以表示为：

我使用嵌套字典（这就是我所说的）和带集合的字典（如果节点没有权重的边）来表示图。

在下一篇文章中，我将使用不同的方法发布精心设计的图类的Python代码，我们将使用该代码来实现图算法。

(本文翻译自sleepingFish的文章《Graph Theory Algorithms "Simplified"》，参考：https://medium.com/better-programming/graph-theory-algorithms-simplified-9a6868cc222)

B. 图论的基本概念有哪些

图论基本概念
重要定义：
有向图：每条边都是有向边的图。
无向图：每条边都是无向边的图。
混合图：既有有向边又有无向边的图。
自回路：一条边的两端重合。
重数：两顶点间若有几条边，称这些边为平行边，两顶点a,b间平行边的条数成为（a,b）的重数。
多重图：含有平行边的图。
简单图：不含平行边和自回路的图。
注意！一条无向边可以用一对方向相反的有向边代替，因此一个无向图可以用这种方法转化为一个有向图。
定向图：如果对无向图G的每条无向边指定一个方向由此得到的有向图D。称为的G定向图.
底图：如果把一个有向图的每一条有向边的方向都去掉，得无向图G称为的D底图。
逆图：把一个有向图D的每条边都反向由此得到的图称为D的逆图。
赋权图：每条边都赋上了值。
出度：与顶点相连的边数称为该定点的度数，以该定点为始边的边数为出度。 入度：以该定点为终边的边数为入度。
特殊！度数为零的定点称为孤立点。度数为一的点为悬挂点。
无向完全图：在阶无向图中如果任何两点都有一条边关连则称此图是无向完全图。Kn
完全有向图：在阶有向图中如果任意两点都有方向相反的有向边相连则称此图为完全有向图。
竟赛图：阶图中如果其底图是无向完全图，则程此有向完全图是竟塞图。
注意！n阶有向完全图的边数为n的平方；无向完全图的边数为n(n-1)/2。
下面介召图两种操作：①删边：删去图中的某一条边但仍保留边的端点。
②删点：删去图中某一点以及与这点相连的所有边。
子图：删去一条边或一点剩下的图。
生成子图：只删边不删点。
主子图：图中删去一点所得的子图称的主子图。
补图：设为阶间单无向图，在中添加一些边后，可使成为阶完全图；由这些添加边和的个顶点构成的图称为的补图。
重要定理：
定理5.1.1 设图G是具有n个顶点m条边的有向图，其中点集V={v,v,….,v}
deg+(vi)=deg-(vi)=m
定理5.1.2 设图G是具有n个顶点m条边的无向图，其中点集V={v,v,v,……,v}
deg(vi)=2m
推论 在无向图中，度数为积数的顶点个数为偶数。
通路和富权图的最短通路
1通路和回路
基本概念：
通路的长度：通路中边的条数。
回路：如果通路中始点与终点相同。
简单通路：如果通路中各边都不相同。
基本通路：如果通路中各顶点都不相同。显然（基本通路一定是简单通路，但简单通路不一定是基本通路）
可达：在图G中如果存在一条v到d通路则称从v到d是可达。
连通：在无向图中如果任意两点是可达的，否则是不连通的。
强连通：在有向图中如果任意两点是互可达的。
单向连通：在有向图中如果存在任意两点的通路。
弱连通：在有向图中如果其底图是连通的。
权：在图的点或边上表明某种信息的数。
赋权图：含有权的图。
赋权图的最短通路问题的算法：先求出到某一点的最短通路，然后利用这个结果再去确定到另一点的最短通路，如此继续下去，直到找到到的最短通路为止。
指标：设V是图的点集，T是V的子集，且T含有z但不含a，则称T为目标集。在目标集T中任取一个点t，由a到t但不通过目标集T中其它点所有通路中，个边权和的最小者称为点t关与T的指标记作DT(t)。
图和矩阵
住意两个的区别：A·A 中元素的意义：当且仅当a 和a 都是1时，a a =1而a 和a 都为1意味着图G中有边(v ,v )和(v ,v )。于是可得如下结论：从顶点v 和v 引出的边，如果共同终止于一些顶点，则这些终止顶点的数目就是b 的值；特别对于b ，其值就是v 的出度。

A ·A中元素的意义：当且仅当a 和a 都为1时，a a =1，这意味着图中有边(v ,v )和(v ,v )。于是的得如下结论：从某些点引出的边，如果同时终止于v 和v ，则这样的顶点数就是的值。特别对于b ，其值就是的v 入度。

幂A 中元素的意义：当m=1时，a 中的元素=1，说明存在一条边(v ,v )，或者说从v 到v 存在一条长度为一的通路。

A 中元素a 表示从v 到v 的长度为m的所有通路的数目。
欧拉图
主要定义：
如果图中存在一条通过图中个边一次且仅一次的回路，则称此回路为欧拉回路，具有欧拉回路的图称为欧拉图。

如果图中存在一条通过图中各边一次且仅一次的通路，则称此回路为欧拉通路，具有欧拉通路的图称为半欧拉图。

主要定理：一个无向连通图是欧拉图的充要条件是图中各点的度数为偶数。

一个无向连通图是半欧拉图的充要条件是图中至多有两个奇数度点。

设图G是有向连通图，图G是欧拉图的充要条件是图中每个顶点的入度和出度相等。

设图G是有向连通图，图G是半欧拉图的充要条件是至多有两个顶点，其中一个顶点入度比它的出度大1，另一个顶点入度比它的出度少1；而其他顶点的入度和出度相等。
哈密顿图
主要定义：如果图G中存在一条通过图G中各个顶点一次且仅一次的回路，则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图。

如果图G中存在一条通过图G中各个顶点一次且仅一次的回路，则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图。
主要定理：设图G是哈密顿图，如果从G中删去个p顶点得到图G’，则图G’的连通分支数小于等于p。

设图G是具有n个顶点的无向简单图，如果G中任意两个不同顶点的度数之和大于等于n-1，则具有哈密顿通路，即G是半哈密顿图。

设图G是具有n个顶点的无向简单图，如果G中任意两个不同顶点的度数之和大于等于n，则G具有哈密顿回路，即G是哈密顿图。

C. 求解：图论中常见的最短路径算法有几种都是什么

主要是有三种、、

第一种是最直接的贪心dijkstra算法、、可以利用堆数据结构进行优化、、缺点就是不能求有负权的最短路与判断负环、、

第二种是bellman-ford算法、、根据松弛操作的性质是可以来判断负环的、、时间复杂度是O(nm)的、、

第三种是SPFA算法、、把他单独拿出来作为一种算法并不是非常好的、、他的实质应该是上面的bellman-ford算法的队列优化时间复杂度更低、O(KE)、K的值约等于2、、

D. 图论算法的介绍

图论算法在计算机科学中扮演着很重要的角色，它提供了对很多问题都有效的一种简单而系统的建模方式。很多问题都可以转化为图论问题，然后用图论的基本算法加以解决。遗传算法是解优化问题的有效算法，而并行遗传算法是遗传算法研究中的一个重要方向，受到了研究人员的高度重视。

E. 图论算法的教材

我想很多学习图论的人都知道J.A. Bondy和U.S.R. Murty着的《Graph Theory with Application》(Elsevier,1976)是图论教材中的经典，时至今日，仍不失为初学者较好的入门书。还记得兰州交通大学的张忠辅教授说过，国内第一届图论学会就是把大家集中起来学习邦迪的《Graph Theory with Application》，由此可见这本书对国内图论届的影响是如此之大。吴望名等人将其译成中文版本《图论及其应用》（北京：科学出版社，1984），1988年张克民等人编写了该书的参考答案《图论及其应用习题解答》（清华大学出版社，1988）。
在2008年J.A. Bondy和U.S.R. Murty出了新书《Graph Theory》(GTM 244, Springer, 2008), 大家可不妨将其看成是《Graph Theory with Application》的第二版，这本书在内容上做了重新调整，毕竟在第一版出版后的近30年里涌现出了很多新的结果，所以《Graph Theory》在内容上加进了一些新的结果，这本书我只是读了其中的几章，觉得写的非常棒，建议大家能够读读，这里也值得一提的是将第一版最后提出的50个问题进行了更新，并补充了一些新的问题。总之，我个人认为，《Graph Theory》的确是一部很优秀的图论教材。
中国科学技术大学出版社出版的《图论及其算法》，融有向图和无向图为一整体，系统地阐述了图论的基本概念、理论、方法及其算法，内容包括图的基本概念、Euler图与Hamilton图、图论算法、树及其应用、平面图、独立集与匹配、网络流和Petri网。 书中附有大量例题和习题，而且大部分习题有详细解答。 该书选材精炼全面，内容处理恰当且有新意，立论严谨，叙述条理清晰，语言流畅。 该书可用作高校计算机、电子、信息、管理、数学等专业本科生必修课教材，也可供相关专业的研究人员、教师及图论工作者参考。