图论的起源
德国的哥尼斯堡城有一条普雷格尔河,河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。
为了寻找答案，1736年欧拉将这个问题抽象或图所示图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形,最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。
图的基本概念
图：图论中的图是由点和点与点之间的线所组成的。通常，我们把点与点之间不带箭头的线叫做边，带箭头的线叫做弧。
无向图：如果一个图是由点和边所构成的，那么，称为无向图，记作G=(V, E)，其中V表示图G的点集合，E表示图G的边集合。连接点vi,vj的边记作[vi, vj],或者[vj, vi]。
有向图：如果一个图是由点和弧所构成的，那么称为它为有向图，记作D=(V, A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi, vj)。
连通图：
强连通和弱连通的概念只在有向图中存在
强连通图：在有向图中, 若对于每一对顶点v1和v2, 都存在一条从v1到v2和从v2到v1的路径,则称此图是强连通图。
弱连通图：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。
生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n – 1条边
最小生成树：一个连通图的生成树可能有多个。边的权值之和最小的生成树是最小生成树
完全图：
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/206373.html原文链接：https://javaforall.net
