连通图,什么是连通图。

  • 内容
  • 相关

【连通图】在百科里,所谓连通图就是指连通的一种概念以图示的方式展现,在无向图G里,如果从顶点到另外一个顶点有线相连,则两个顶点就是连通的,在有向图G里,两个顶点相连的路径所有的边都必须同向。如果图里随便两个顶点都是连通的,那么这个图就可以称作连通图。

连通图可以分为强连通图、单向连通图、弱连通图和初级通路。

强连通图:有向图 G=(V,E) 中,若对于V中任意两个不同的顶点 x和 y,都存在从x到 y以及从 y到 x的路径,则称 G是强连通图。相应地有强连通分量的概念。强连通图只有一个强连通分量,即是其自身;非强连通的有向图有多个强连分量。

单向连通图:设G=<V,E>是有向图,如果u->v意味着图G至多包含一条从u到v的简单路径,则图G为单连通图。

弱连通图:将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向图是弱连通图。

初级通路:通路中所有的顶点互不相同。初级通路必为简单通路,但反之不真。

本文标签:

版权声明:若无特殊注明,本文皆为《安三》原创,转载请保留文章出处。『鹦鹉搜索』

百度收录:百度已收录『查看详情』

本文链接:连通图,什么是连通图。 - https://www.15qq.cn/spe_seo/957.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注

允许邮件通知