一、图的简介

• $G=(V,E)$ 包含节点（Vertex）集合 $V$（非空）、边（Edge）集合 $E$

1. 图的类型

1. 简单图 Simple Graph
   • 边集合是无序对组成的集合，无序对中的两个元素是不同的（Distinct）
   • 由集合的元素唯一性，边集合中不存在两个相同的无序对
   • 总结：简单图是无向图，不含环，两节点之间最多只存在一条边
2. 多图 Multi-Graph
   • 存在一个从 $E$ 到 $\set{\set{u,v}|u,v\in V,u\neq v}$ 的函数 $f$，若 $f(e_1)=f(e_2)$，则边 $e_1,e_2$ 称为并行边（Multiple/Parallel Edges ）
   • 总结：多图是无向图，不含环，两节点之间可以存在多条边
3. 伪图 Pseudo-Graph
   • 存在一个从 $E$ 到 $\set{\set{u,v}|u,v\in V}$ 的函数 $f$，若 $f(e)=\set{u,u}$，则边 $e$ 称为环（Loops）
   • 总结：伪图是无向图，可以含有环，两节点之间可以存在多条边
4. 有向图 Directed Graph
   • 边集合是有序对组成的集合，有序对中的两个元素可以相同
   • 总结：有向图，可以含有环，两节点之间最多只存在一条边
5. 有向多图 Directed Multi-Graph
   • 存在一个从 $E$ 到 $\set{(u,v)|u,v\in V,u\neq v}$ 的函数 $f$，若 $f(e_1)=f(e_2)$，则边 $e_1,e_2$ 称为并行边（Multiple/Parallel Edges ）
   • 总结：有向多图，可以含有环，两节点之间可以存在多条边

2. 无向图的术语

1. 基本术语

   • 两节点 $u,v$ 称为邻居（Adjacent/Neighbors），若这两节点之间存在边 $e=\set{u,v}$
   • 称边 $e=\set{u,v}$ 关联于（incident with）节点 $u,v$
   • 称节点 $u,v$ 为边 $e=\set{u,v}$ 的端点（Endpoint）

2. 节点的度 Degree

   • 节点 $v$ 的度（Degree）是与之相连的边的数量（例外：一个环贡献 2 个度），记作 $deg(v)$
   • 度为 0 的节点称为孤立节点（Isolated Vertex），度为 1 的节点称为悬挂节点（Pendant Vertex）

3. 握手定律 The Handshaking Theorem

   • 设 $G$ 是具有 $m$ 条边和 $n$ 个节点 $v_1,v_2,…,v_n$ 的图，则 $\sum_{i=1}^n deg(v_i)=2m$
   • 总结：所有节点的度之和是偶数

   示例：

   

3. 有向图的术语

1. 基本术语

   对于有向边 $(u,v)$：

   • $u$ is adjacent to $v$， $v$ is adjacent from $v$
   • $v$ 称为出发节点（Initial Vertex）， $v$ 称为到达节点（Terminal/End Vertex）
   • 对于环，出发节点和到达节点是同一个

2. 入度和出度

   • 节点 $v$ 的入度（in-degree）是以它为到达节点的边数，记作 $deg^-(v)$
   • 节点 $v$ 的出度（out-degree）是以它为出发节点的边数，记作 $deg^+(v)$
   • 一个环为节点贡献一个入度、一个出度

3. 定理

   • $\sum_{i=1}^n deg^-(v_i)=\sum_{i=1}^n deg^+(v_i)=|E|$

4. 简单图的特例

1. 完全图 Complete Graph

   • $n$ 阶完全图记作 $K_n$
   • 完全图是每一对节点之间都存在边的简单图
   • $n$ 阶完全图的边数 $|E|=C(n,2)=\frac{n(n-1)}{2}$