图论基础

敲这个笔记主要是为了复习。

---

• 图（graph） 可以看作二元组，$G=(V_G,E_G)$。$V_G$ 是图中所有 顶点（vertex） 的集合；$E_G$ 是图中所有 边（edge） 的集合。

• 如果 $G_1=(V_{G_1},E_{G_1})$ 满足 $V_{G_1}\subseteq V_G$，$E_{G_1}\subseteq E_G$，就说 $G_1$ 是 $G$ 的一个子图（sub-graph）。

• 图上两点间的简单路径记为 $\delta(u,v)$。如果 $\forall u,v\in V_G$，$\delta(u,v)$ 都存在，就说 $G$ 是一个连通图，此时说这个图是连通的。

• 图中连通的子图也称为连通块。

• 如果 $\forall u,v\in V_G$，$(u,v)\in E_G$，就说 $G$ 是一个完全图。

• 每个边可以有一定的权值，称为边权。节点也类似，称为点权。

图的边可以是有向的（有向图），也可以是无向的（无向图）。如果边 $(u,v)$ 只能从 $u$ 旅行到 $v$，而不能反过来，就说这是一条从 $u$ 到 $v$ 的有向边。

• 连接一个节点的边的总数称为这个节点的度。进入这个节点的边的总数称为入度；离开这个节点的边的总数称为出度。
• 如果从一个节点出发，走过不重复的边可以回到这个节点本身，就说这里有一个环。（不严格地说）
• 对于有向图，如果 $\forall u,v\in G$，$u\to v$ 和 $v\to u$ 的路径都存在，就称它是强连通的；否则就称它是弱连通的。

几个专有名词：

• 简单图：没有重边和自环的图。
• DAG：Directed Acyclic Graph，有向无环图。