图
对于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)]](https://aitechtogether.com/wp-content/uploads_new/2023/12/a41f6651-ef34-4d43-8a42-9eeeca7c6d72.webp)
强连通图：从a到b和从b到a都有路径。最少有n条边，假若少了A-D的路径，则A可以到D，但是D到不了A，就不满足条件。
强连通分量：有向图中的极大强连通子图，对比无向图中连通分量
生成树：包含图中全部顶点的一个极小连通子图（生成树不唯一）。若去除一条边，则生成树会变成非连通图；若多加上一条边，则会形成回路
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NQSYvvNk-1659012648962)(../typ-img/image-20220728204539370.png)]](https://aitechtogether.com/wp-content/uploads_new/2023/12/b1ff09dd-d4c4-4dba-9da3-71745d714240.webp)
注意：极大连通子图要求连通子图包含所有边，极小连通子图要求使图保存连通的前提下使边数最少。
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4Wl7L39J-1659012648963)(../typ-img/image-20220728201520617.png)]](https://aitechtogether.com/wp-content/uploads_new/2023/12/9ee31ec1-1a2b-400d-9456-7f4f5263f75b.webp)
简单路径：顶点不重复出现的路径称为简单路径
区分：无向图关于连通图和连通分量，有向图关于强连通图和强连通分量
文章出处登录后可见！
已经登录？立即刷新
