图的概念

约 788 个字预计阅读时间 3 分钟

图相关概念¶

图是一个二元组 $G=(V,E)$

$V$ 表示点集(Vertex set),即点的集合， $E$ 表示边集(Edge set)，即边的集合

常用 $|V|,|E|$ 表示点集内元素数量，边集内元素数量

稠密图¶

$|E|\approx|V|^2$

稀疏图¶

$|E|\approx |V|$

有向图(Directed graph)¶

边有方向，即可以从a点到b点，但不能从b点到a点

例如你欠我的钱和我欠你的钱是万万不能混淆的。

无向图(Undirected graph)¶

边无方向，即可以从a点到b点，又可以从b点到a点

边权(Edge weight)¶

边被赋予的一个数，表示通过该边，会变化多少

例子¶

你开车从a地到b地，汽油减少10L，点a到点b的边的边权为10

通常减少为正数，增加为负数

假如中途有加油站，你开车从a地到b地，汽油增加10L，点a到点b的边的边权为-10

自环(Loop)¶

对 $E$ 中的边 $e=(u,v)$ ,若 $u=v$ ，则e被称为自环

重边(Multiple edge)¶

若 $E$ 中存在两个顶点完全相同的元素 $e_1,e_2$ ，则它们被称作重边

注意¶

在无向图中 $(u,v)$ 和 $(v,u)$ 算一组重边

而在有向图中 $(u,v)$ 和 $(v,u)$ 不为重边

简单图(Simple graph)¶

若一个图中没有自环和重边，它被称为简单图

在题目中，如果没有特殊说明，可以不是简单图，需要处理一下

下面3个概念帮助理解环，不需要记忆

途径¶

将若干个点连接起来的边的集合 $W$

迹¶

对于一条途径 $W$ ， $e_1,e_2,...,e_k$ 两两互不相同

回路¶

对于一个迹 $W$ ，起点和终点是同一个点

环(Cycle)(又称简单回路(Simple circuit))¶

对于一个回路 $W$ ，起点和终点是点序列中唯一重复出现的点对

无环图(Acyclic graph)¶

不存在环的图

度数(Degree)¶

与点 $a$ 相连的边的数量，称之为度

以点 $a$ 为起点的边的数量，称之为点 $a$ 的出度(Out-degree)

以点 $a$ 为终点的边的数量，称之为点 $a$ 的入度(In-degree)

反图(Transpose Graph)¶

点集一样，边集反向，仅对于有向图有反图概念

完全图(Complete graph)¶

对无向图和有向图定义不一样

无向完全图¶

任意不同两点间均有边

有向完全图¶

任意不同两点间都有两条方向不同的边

星图/菊花图(Star graph)¶

若无向简单图满足，存在一个点v的度数 $=|G|-1$ ，其余点之间没有边相连

这个图常用来卡图论算法

链(Chain/Path Graph)¶

无向简单图的所有边恰好构成一条简单路径

这个图常用来卡图论算法

菊花图和链结合一下也能用来卡图论算法

树(Tree)¶

无向连通图不含环

森林(Forest)¶

多棵树组成的图

子图(Subgraph)¶

对一张图 $G=(V,E)$ ，若存在另一张图 $H=(V',E')$ ，

满足 $V'$ 是 $V$ 的子集且 $E'$ 是 $E$ 的子集，则称H是G的子图