完全图、连通图、非连通图、连通分量、强连通图、生成树的概念

对于n个结点的图来说：

无向完全图：有n（n-1）/2 条边，如下：4个顶点有6条边

连通图：无向图中，任意两个顶点是连通的（一个顶点不必与另一个顶点直接相连，可以通过其它顶点到达即可）最少有n-1条边；如下：4个顶点最少需要3条边才能够连通

完全图、连通图、非连通图、连通分量、强连通图、生成树的概念

非连通图，即边数少于n-1条，最多有（n-1）*(n-2)/2条，如下：5个结点，非连通，最多有6条边

完全图、连通图、非连通图、连通分量、强连通图、生成树的概念

连通分量：无向图中（区别于有向图）的极大连通子图，极大即要求拥有连通子图的所有边，例如，如果A1中少了a-d这条边就不是极大连通子图了

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bPb3bINB-1659012648961)(../typ-img/image-20220728203945406.png)]

强连通图：从a到b和从b到a都有路径。最少有n条边，假若少了A-D的路径，则A可以到D，但是D到不了A，就不满足条件。

完全图、连通图、非连通图、连通分量、强连通图、生成树的概念

强连通分量：有向图中的极大强连通子图，对比无向图中连通分量

生成树：包含图中全部顶点的一个极小连通子图（生成树不唯一）。若去除一条边，则生成树会变成非连通图；若多加上一条边，则会形成回路

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NQSYvvNk-1659012648962)(../typ-img/image-20220728204539370.png)]

注意：极大连通子图要求连通子图包含所有边，极小连通子图要求使图保存连通的前提下使边数最少。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4Wl7L39J-1659012648963)(../typ-img/image-20220728201520617.png)]

简单路径：顶点不重复出现的路径称为简单路径

区分：无向图关于连通图和连通分量，有向图关于强连通图和强连通分量

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://www.net2asp.com/4dc0e73435.html