图的定义和基本术语

发布于:2023-01-22 ⋅ 阅读:(9) ⋅ 点赞:(0) ⋅ 评论:(0)

1、无向完全图

在无向图中,如果任意两个顶点之间都存在边,则称该图为 无向完全图

在这里插入图片描述

如果顶点为n的话每个点可与其它n-1个点相连共有n*(n-1),但是每条线均被计算了2次(比如从A到B和从B连到A是一样的),再除以2即可n*(n-1)/2,所以无向完全图中边的计算公式为 n*(n-1)/2

2、有向完全图

在有向图中,如果任意两个顶点之间都存在 方向互为相反 的两条弧,则称该图为 有向完全图
注意,有向完全图一定是强连通图,但是强连通图不一定是有向完全图!
在这里插入图片描述

如果顶点为n的话每个点可与其它n-1个点相连共有n*(n-1),每条线均被计算了1次(比如从A到B和从B连到A是不一样的),所以有向完全图中边的计算公式为 n*(n-1)

3、无向图和有向图的度

(1)、顶点v的度是指和v相关联的边的数目!所以在无向图中与顶点v相关联的边的总数目叫做顶点v的度!
            
       在无向图中所有顶点的度之和是 2|E|(|E|是无向图中边数的总和),可以随便画个无向图就可以得出一般性的结论!
 
(2)、但是在有向图中因为有从顶点v到达另一个顶点的边,也有从一个顶点到达该顶点v的边,所以对于顶点v就有出边和入边,因此对于顶点v出边的和的个数叫做出度,入边的和个数是叫做入度!所以一个有向图中顶点v的度数和是出度+入度!
    
       在有向图中所有顶点的度之和是 2|E|(|E|是有向图中边数的总和),可以随便画个有向图图就可以得出一般性的结论!
       
       在有向图中所有顶点的出度之和等于入度之和 =  |E|,可以画个简单的有向图得出一般性的结论!

4、回路或者环

第一个顶点和最后一个顶点相同的路径称为回路或者环!

5、简单路径

序列中顶点不重复出现的路径称为简单路径!

6、简单回路、环

除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路称为简单回路或者环!

7、子图(有向图、无向图)

在这里插入图片描述

如果子图中包含原图中的所有顶点,那么这个子图就可以称为原图的生成子图!

在这里插入图片描述
在这里插入图片描述

8、连通、连通图、连通分量(无向图)

连通:在无向图中如果两个顶点之间可以到达,则是连通的

连通图:在无向图中如果一个图中任意两点之间都是可以到达的,连通的,则说明该图是连通的,否则是非连通的

连通分量:所谓连通分量,就是无向图中的极大连通子图(子图必须连通,并且包含尽可能多的顶点和边)

极大连通子图:
1.连通图只有一个极大连通子图,就是它本身。(是唯一的)
2.非连通图有多个极大连通子图。(非连通图的极大连通子图叫做连通分量,每个分量都是一个连通图)
3.称为极大是因为如果此时加入任何一个不在图的点集中的点都会导致它不再连通。
在这里插入图片描述

无向图中连通图的常见考点

在这里插入图片描述
对于连通图,最少的情况是 n - 1条边(将n个结点依次相连,或者下面的情况);
在这里插入图片描述
最多的情况是完全无向图,有n*(n-1)/2条边

对于非连通图,最多的情况是将n个结点排除一个,剩余的任意两个顶点之间都存在边,也即剩余的结点构成一个完全无向图,此时对于非连通图来说是存在边最多的情况!如果排除在外的那一个结点与任意一个结点连接,那么此时由非连通图变成连通图!

在这里插入图片描述

9、强连通图和强连通分量(有向图)

在有向图中,如果任意两个顶点之间都有路径存在(即vi到vj有路径,也从vj到vi存在路径),则称为强连通图
有向图中的极大强连通子图叫做有向图的强连通图分量(子图必须强连通,同时保留尽可能多的边)
在这里插入图片描述

有向图中连通图的常见考点

在这里插入图片描述
在这里插入图片描述

10、生成树

树--------------------------不存在回路,且是连通的无向图!
在这里插入图片描述
极小连通子图中要求边尽可能的少,但是要保持连通!
注意:有 n - 1条边的图不一定是生成树!
在这里插入图片描述
在这里插入图片描述

生成树中的常见考点

在这里插入图片描述

11、有向树

注意,树是一个连通图(上面的图中),各个顶点是连通的,但是有向树并不是一个强连通图!
在这里插入图片描述