图论中常见术语介绍

图的常见术语

有向图

图中的节点与节点之间的边是有方向的。如下图两个顶点v2—>v1,反之v1—>v2不行。 有向图

无向图

图中的节点之间是边是无向的。若v1能到v2,一定v2能到v1 无向图

联通

若从顶点i到顶点j有路径相连(直接相连,或者拐了几个弯相连),称之为i与j联通。

子图

子图中的m个节点和n条边,在原图中M节点和N条边的子集。(m∈M,n∈N)

连通图

定义:如果图中任意两点都是连通的,那么图被称作连通图。

连通分量

一个图中若有子图是连通图,则这个子图称之为连通分量。若图本身就是连通图,那么它连通分量就是自己。

权值

节点之间的边上面的数值,如下图的3、4、5。生活在常表示节点之间的距离等等。。。 权

最小生成树

一个含有n个节点的连通图的极小联通子图。也就是权值相加最小的联通子图。在无向图中边E一定等于顶点N-1。如下面的两幅图片中,子图1是最小生成树,子图2不是。 最小生成树

坚持原创技术分享,您的支持将鼓励我继续创作!
  • 本文作者: 带带蓝蜗牛
  • 本文链接: 249.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!