写点什么

图的基本定义和概念(二)

作者:乔乔
  • 2022 年 7 月 21 日
  • 本文字数:687 字

    阅读完需:约 2 分钟

完全图

对于一个具有 n 个顶点,e 条边的无向图,若边的总条数为 n*(n-1)/2,则称该图为完全图。

有向完全图

对于一个具有 n 个顶点,e 条边或弧的有向图,若边的总条数为 n*(n-1),则称该图为有向完全图。

有时图的边或弧具有与它相关的数,这种与图的边或弧相关的数称作权。

这些权可以表示从一个个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。

子图

可以理解为被包涵的一部分,一个大图里的一部分。

路径

在一个图中若从任一顶点 v 出发,沿着边能达到另一顶点 v',则称这两顶点间存在路径。两顶点间不重重复边的条数称为路径的长度。

简单路径

在用一个顶点序列表示一条路径时,若序列中没有相同的顶点重复出现,则称其为简单路径。除了第一个顶点和最后一个顶点之外,其余顶点均不相同的回路称为简单回路。

无向连通图

在无向图 G 中,如果从顶点 v 到顶点 v'有路径,则称 v 和 v'是连通的。如果对于无向图中任意两个顶片点 vi 和 vj(vi、vj ∈V),都是连通的,则称 G 是连通图。


连通分量

无向图的极大连通子图。

有向连通图

在有向图 G 中,如果对于每一对顶点(vi,vj)(vi,vj ∈V)(vi≠vj),从 vi 到 vj 和从 vj 到 vi 都存在路径,则称 G 是强连通图。有向图 G 中的极大的强连通子图称为有向图的强连通分量,如图 7.5(1)所示。 图 7.5(2)为非强连通图与其三个强连通分量。


生成树

一个连通图的极小连通子图,称为其生成树。它含有图中的全部顶点 N,但只有足以构成一棵树的 N-1 条边。下图为生成树。图中共有 10 个顶点,所以生成树中有 9 条边。


一棵有 N 个顶点的生成树,有且仅有 N-1 条边。如果一个图有 N 个顶点和小于 N-1 条边,则该图为非连通图。


如果它有多于 n-1 条边,则图中一定有环。但有 n-1 条边的图不一定都是生成树。



发布于: 刚刚阅读数: 3
用户头像

乔乔

关注

平安喜乐,一切顺遂 2022.07.01 加入

一个热爱技术,热爱生活的人

评论

发布
暂无评论
图的基本定义和概念(二)_7月日更_乔乔_InfoQ写作社区