本文阅读 3 分钟
首页 知识库 正文

无向图

  1. 回路或环:第一个顶点和最后一个顶点相同的路径。
  2. 简单回路或简单环:除第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路
  3. 连通:顶点v至v’ 之间有路径存在
  4. 连通图:无向图图 G 的任意两点之间都是连通的,则称G是连通图。
  5. 连通分量:极大连通子图,子图中包含的顶点个数极大
  6. 所有顶点度的和必须为偶数

有向图:

  1. 回路或环:第一个顶点和最后一个顶点相同的路径。
  2. 简单回路或简单环:除第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路。
  3. 连通:顶点v至v’之间有路径存在
  4. 强连通图:有向图G的任意两点之间都是连通的,则称G是强连通图。各个顶点间均可达。
  5. 强连通分量:极大连通子图
  6. 有向图顶点的度是顶点的入度与出度之和。邻接矩阵中第V行中的1的个数是V的出度
  7. 生成树:极小连通子图。包含图的所有n个结点,但只含图的n-1条边。在生成树中添加一条边之后,必定会形成回路或环。
  8. 完全图:有 n(n-1)/2 条边的无向图。其中n是结点个数。必定是连通图。
  9. 有向完全图:有n(n-1)条边的有向图。其中n是结点个数。每两个顶点之间都有两条方向相反的边连接的图。
  10. 一个无向图 G=(V,E) 是连通的,那么边的数目大于等于顶点的数目减一:|E|>=|V|-1,而反之不成立。如果 G=(V,E) 是有向图,那么它是强连通图的必要条件是边的数目大于等于顶点的数目:|E|>=|V|,而反之不成立。没有回路的无向图是连通的当且仅当它是树,即等价于:|E|=|V|-1。
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

图遍历与回溯
« 上一篇 01-21
图的存储形式
下一篇 » 01-21

发表评论

惪特博客
  • 文章总数:
    18085 篇
  • 评论总数:
    52233 条
  • 标签总数:
    8183 个
  • 总浏览量:
    15793191 次
  • 最后更新:
    4小时前

最多点赞

随便看看

标签TAG