图
无向图
- 回路或环:第一个顶点和最后一个顶点相同的路径。
- 简单回路或简单环:除第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路
- 连通:顶点v至v’ 之间有路径存在
- 连通图:无向图图 G 的任意两点之间都是连通的,则称G是连通图。
- 连通分量:极大连通子图,子图中包含的顶点个数极大
- 所有顶点度的和必须为偶数
有向图:
- 回路或环:第一个顶点和最后一个顶点相同的路径。
- 简单回路或简单环:除第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路。
- 连通:顶点v至v’之间有路径存在
- 强连通图:有向图G的任意两点之间都是连通的,则称G是强连通图。各个顶点间均可达。
- 强连通分量:极大连通子图
- 有向图顶点的度是顶点的入度与出度之和。邻接矩阵中第V行中的1的个数是V的出度
- 生成树:极小连通子图。包含图的所有n个结点,但只含图的n-1条边。在生成树中添加一条边之后,必定会形成回路或环。
- 完全图:有 n(n-1)/2 条边的无向图。其中n是结点个数。必定是连通图。
- 有向完全图:有n(n-1)条边的有向图。其中n是结点个数。每两个顶点之间都有两条方向相反的边连接的图。
- 一个无向图 G=(V,E) 是连通的,那么边的数目大于等于顶点的数目减一:|E|>=|V|-1,而反之不成立。如果 G=(V,E) 是有向图,那么它是强连通图的必要条件是边的数目大于等于顶点的数目:|E|>=|V|,而反之不成立。没有回路的无向图是连通的当且仅当它是树,即等价于:|E|=|V|-1。
解压密码: detechn或detechn.com
免责声明
本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。
本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。
本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。