基本概念

顶点 (Vertex or Node)

构成

点集 (Vertex set)

。
边(Edge)

构成

边集 (Edge set)
- 常记作
- 有向边 (Directed edge)
  
  或
  
  弧 (Arc)
  
  ：
  $\to v u → v 。设 e = u → v e=u \to v e = u → v ，则此时 u u u 称为 e e e 的起点 (Tail) ， v v v 称为 e e e 的终点 (Head) ，并称 u u u 是 v v v 的直接前驱， v v v 是 u u u 的直接后继。$
- 无向边 (Undirected edge)
  
  或
  
  边 (Edge)
  
  ：
图 (Graph)

是一个二元组$G=(V(G), E(G)) $ ，其中

(

G

)

V(G)

$V (G)$

是非空

点集 (Vertex set)

，

(

G

)

E(G)

$E (G)$

是

边集 (Edge set)

。
- 常记作
  
  =
  
  (
  
  V
  
  ,
  
  E
  
  )
  
  G=(V,E)
  
  $G = (V, E)$
  
  。
- 图
  
  G
  
  $G$
  
  的点数
  
  V
  
  (
  
  G
  
  )
  
  ∣
  
  |V(G)|
  
  $∣ V (G) ∣$
  
  也被称作图
  
  G
  
  $G$
  
  的
  
  阶 (Order)
  
  。
- 当
  
  ,
  
  E
  
  V,E
  
  $V, E$
  
  都是有限集合时，称
  
  G
  
  $G$
  
  为
  
  有限图
  
  ；当
  
  V
  
  $V$
  
  或
  
  E
  
  $E$
  
  是无限集合时，称
  
  G
  
  $G$
  
  为
  
  无限图
  
  。
- 有向图 (Directed graph)
  
  ：
  
  E
  
  $E$
  
  中均为有向边。
  
  无向图 (Undirected graph)
  
  ：
  
  E
  
  $E$
  
  中均为无向边。
  
  混合图 (Mixed graph)
  
  ：
  
  E
  
  $E$
  
  中既有有向边也有无向边。
- 赋权图
  
  ：每条边都有权值。其中边权全是正的为
  
  正权图
  
  。
- 稀疏图 (Sparse graph)
  
  ：边很多，**稠密图 (Dense graph)**刚好相反。这个一般用于讨论时间复杂度为
  
  (
  
  ∣
  
  V
  
  ∣
  
  2
  
  )
  
  O(|V|^2)
  
  $O (∣ V ∣^{2})$
  
  的算法与
  
  (
  
  ∣
  
  E
  
  ∣
  
  )
  
  O(|E|)
  
  $O (∣ E ∣)$
  
  的算法的效率差异（稀疏图优先选择后者）。
- 自环 (Loop)
  
  ：
  
  e
  
  =
  
  (
  
  u
  
  ,
  
  v
  
  )
  
  ∈
  
  E
  
  ,
  
  且
  
  u
  
  =
  
  v
  
  \exists e=(u,v)\in E,且u=v
  
  $\exists e = (u, v) \in E, 且 u = v$
  
  ，则
  
  e
  
  $e$
  
  称作自环。
  
  重边 (Multiple edge)
  
  ：若
  
  E
  
  $E$
  
  中存在两个完全相同的边，则它们被称作（一组）重边。
- 简单图 (Simple graph)
  
  ：若一个图中没有自环和重边，它被称为简单图。否则为
  
  多重图 (Multigraph)
  
  。
- 补图：对于无向图
- 反图
图中的点
- 对于两顶点
  
  u
  
  $u$
  
  和
  
  v
  
  $v$
  
  ，若存在边
  
  u
  
  ,
  
  v
  
  )
  
  (u,v)
  
  $(u, v)$
  
  ，则称
  
  u
  
  $u$
  
  和
  
  v
  
  $v$
  
  是
  
  相邻的 (Adjacent)
  
  。
  
  一个顶点
  
  ∈
  
  V
  
  v\in V
  
  $v \in V$
  
  的**邻域 (Neighborhood)**是所有与之相邻的顶点所构成的集合，记作
  
  (
  
  v
  
  )
  
  N(v)
  
  $N (v)$
  
  。
  
  一个点集
  
  S
  
  $S$
  
  的邻域是所有与
  
  S
  
  $S$
  
  中至少一个点相邻的点所构成的集合，记作
  
  (
  
  S
  
  )
  
  N(S)
  
  $N (S)$
  
  ，即
  
  (
  
  S
  
  )
  
  =
  
  ⋃
  
  v
  
  ∈
  
  S
  
  N
  
  (
  
  v
  
  )
  
  N(S)=\bigcup_{v\in S} N(v)
  
  $N (S) = ⋃_{v \in S} N (v)$
  
  。
- 度 (Degree)
  
  ：与一个顶点
  
  v
  
  $v$
  
  关联的边的条数，记作
  
  (
  
  v
  
  )
  
  d(v)
  
  $d (v)$
  
  。
  - 无向简单图，有
    
    (
    
    v
    
    )
    
    =
    
    ∣
    
    N
    
    (
    
    v
    
    )
    
    ∣
    
    d(v)=|N(v)|
    
    $d (v) = ∣ N (v) ∣$
    
    。
  - 握手定理（图论基本定理）：对于任何无向图
    
    (
    
    V
    
    ,
    
    E
    
    )
    
    G(V,E)
    
    $G (V, E)$
    
    ，有
    
    v
    
    ∈
    
    V
    
    d
    
    (
    
    v
    
    )
    
    =
    
    2
    
    ∣
    
    E
    
    ∣
    
    \sum_{v\in V}d(v)=2|E|
    
    $\sum_{v \in V} d (v) = 2 ∣ E ∣$
    
    。
    
    推论：在任意图中，度数为奇数的点必然有偶数个。
  - 孤立点 (Isolated vertex)
    
    ：
    
    (
    
    v
    
    )
    
    =
    
    0
    
    d(v)=0
    
    $d (v) = 0$
    
    叶节点 (Leaf vertex)
    
    /
    
    悬挂点 (Pendant vertex)
    
    ：
    
    (
    
    v
    
    )
    
    =
    
    1
    
    d(v)=1
    
    $d (v) = 1$
    
    偶点 (Even vertex)
    
    ：
    
    ∣
    
    d
    
    (
    
    v
    
    )
    
    2\mid d(v)
    
    $2 ∣ d (v)$
    
    奇点 (Odd vertex)
    
    ：
    
    ∤
    
    d
    
    (
    
    v
    
    )
    
    2\nmid d(v)
    
    $2 ∤ d (v)$
    
    ，其中一张图中奇点必有偶数个。
  - 对于一张图，所有节点的度数的最小值称为
    
    最小度 (Minimum degree)
    
    ，记作
    
    (
    
    G
    
    )
    
    \delta(G)
    
    $δ (G)$
    
    ，最大值称为
    
    最大度 (Maximum degree)
    
    ，记作
    
    (
    
    G
    
    )
    
    \Delta(G)
    
    $Δ (G)$
    
    。
  - 对于有向图，以一个顶点为起点的边的条数称为该顶点的
    
    出度 (Out-degree)
    
    ，记作
    
    +
    
    (
    
    v
    
    )
    
    d^+(v)
    
    $d^{+} (v)$
    
    或
    
    u
    
    t
    
    (
    
    v
    
    )
    
    out(v)
    
    $o u t (v)$
    
    。以一个顶点为终点的边的条数称为该节点的
    
    入度 (In-degree)
    
    ，记作
    
    −
    
    (
    
    v
    
    )
    
    d^-(v)
    
    $d^{-} (v)$
    
    或
    
    n
    
    (
    
    v
    
    )
    
    in(v)
    
    $i n (v)$
    
    。对于任何有向图，有：
    
    v
    
    ∈
    
    V
    
    d
    
    +
    
    (
    
    v
    
    )
    
    =
    
    ∑
    
    v
    
    ∈
    
    V
    
    d
    
    −
    
    (
    
    v
    
    )
    
    =
    
    ∣
    
    E
    
    ∣
    
    \sum_{v \in V} d^+(v)=\sum_{v \in V} d^-(v)=|E|
    
    $\sum_{v \in V} d^{+} (v) = \sum_{v \in V} d^{-} (v) = ∣ E ∣$
  - 对于无向图，每个顶点的度数都是一个固定的常数的称为
    
    k – 正则图 (-Regular Graph)
    
    。
路径：将若干个点连接起来的边的集合。边的数量被称作这条途径的

长度

，如果边是带权的，长度通常指路径上的边权之和。
- 简单路径 (Simple path)
  
  ：路径连接的点两两不同。
- 回路 (Circuit)
  
  ：路径头尾相接。
- 简单回路/简单环 (Simple circuit)
  
  ：路径中仅头尾相接。
子图：对于图

G

$G$

，

H

=

(

V

′

,

E

′

)

,

V

′

∈

V

,

E

′

∈

E

\exists H=(V’,E’),V’\in V,E’\in E

$\exists H = (V^{'}, E^{'}), V^{'} \in V, E^{'} \in E$

，则称

H

$H$

是

G

$G$

的

子图 (Subgraph)

，记作

⊆

G

H \subseteq G

$H \subseteq G$

。
连通性：存在一条

u

$u$

到

v

$v$

的路径则

,

v

u,v

$u, v$

连通 (Connected)。
- 无向图
  - 图中任意两个顶点均连通的称
    
    连通图 (Connected graph)
    
    。
  - 若
    
    H
    
    $H$
    
    是
    
    G
    
    $G$
    
    的一个连通子图，则
    
    H
    
    $H$
    
    是
    
    G
    
    $G$
    
    的一个
    
    连通块/连通分量 (Connected component)
    
    。
    
    若不存在
    
    F
    
    $F$
    
    使
    
    ⊊
    
    F
    
    ⊆
    
    G
    
    H\subsetneq F\subseteq G
    
    $H ⊊ F \subseteq G$
    
    则
    
    H
    
    $H$
    
    是
    
    G
    
    $G$
    
    的一个极大连通子图。
- 有向图
  - 有向图的节点两两互相可达，则称这张图是
    
    强连通的 (Strongly connected)
    
    。
  - 张有向图的边替换为无向边后可以得到一张连通图，则称原来这张有向图是
    
    弱连通的 (Weakly connected)
    
    。
  - 同无向图，有
    
    弱连通分量 (Weakly connected component)
    
    、极大弱连通子图、
    
    强连通分量 (Strongly Connected component)
    
    、极大强连通子图。
割
- 强连通图
  $V^{\prime} \subseteq V V ′ ⊆ V 且 G [ V \ V ′ ] G\left[V \backslash V^{\prime}\right] G [ V \ V ′ ] 不是连通图, 则 V ′ V^{\prime} V ′ 是图 G G G 的一个点割集 (Vertex cut/Separating set) 。大小为一的点割集又被称作割点 (Cut vertex)$
- 强连通图
  $\geq k+1 ∣ V ∣ ≥ k + 1 且 G G G 不存在大小为 k − 1 k-1 k − 1 的点割集, 则称图 G G G 是** k k k -点连通的 ( k (k ( k -vertex-connected)** ，而使得上式成立的最大的 k k k 被称作图 G G G 的点连通度 (Vertex connectivity) ，记作 κ ( G ) \kappa(G) κ ( G ) 。对于非完全图，点连通度即为最小点割集的大小, 而完图 K n K_{n} K n 的点连通度为 n − 1 n-1 n − 1 。$
- 对于图
  $\in V u , v ∈ V 满足 u ≠ v , u u \neq v, u u  = v , u 和 v v v 不相邻, u u u 可达 v v v , 若 V ′ ⊆ V , V^{\prime} \subseteq V_{\text {, }} V ′ ⊆ V , u , v ∉ V ′ u, v \notin V^{\prime} u , v ∈ / V ′ , 且在 G [ V \ V ′ ] G\left[V \backslash V^{\prime}\right] G [ V \ V ′ ] 中 u u u 和 v v v 不连通, 则 V ′ V^{\prime} V ′ 被称作 u u u 到 v v v 的点割集。 u u u 到 v v v 的最小点割集的大小被称作 u u u 到 v v v 的局部点连通度 (Local connectivity), 记作 κ ( u , v ) \kappa(u, v) κ ( u , v ) 。$
- 对于连通图
  $E^{\prime} \subseteq E E ′ ⊆ E 且 G ′ = ( V , E \ E ′ ) G^{\prime}=\left(V, E \backslash E^{\prime}\right) G ′ = ( V , E \ E ′ ) (即从 G G G 中删去 E ′ E^{\prime} E ′ 中的边) 不是连通图, 则 E ′ E^{\prime} E ′ 是图 G G G 的一个边割集(Edge cut) 。大小为一的边割集又被称作桥 (Bridge) 。$
- 对于连通图
  $\lambda(G) λ ( G ) 。 (对于任何图, 边连通度即为最小边割集的大小。)$
- 对于图
  $\in V u , v ∈ V 满足 u ≠ v , u u \neq v, u u  = v , u 可达 v v v , 若 E ′ ⊆ E E^{\prime} \subseteq E E ′ ⊆ E , 且在 G ′ = ( V , E \ E ′ ) G^{\prime}=\left(V, E \backslash E^{\prime}\right) G ′ = ( V , E \ E ′ ) 中 u u u 和 v v v 不连通, 则 E ′ E^{\prime} E ′ 被称作 u u u 到 v v v 的边割集。 u u u 到 v v v 的最小边割集的大小被称作 u u u 到 v v v 的局部边连通度 (Local edge-connectivity), 记作 λ ( u , v ) \lambda(u, v) λ ( u , v ) 。$
- 点双连通 (Biconnected)
  
  ：没有割点的强连通图是点双连通的。对于两个点，如果无论删去哪个点（只能删去一个，且不能删自己）都不能使它们不连通。
  - 点双连通没有传递性
- 边双连通 (2-edge-connected)
  
  ：没有桥的强连通图是边双连通的。对于两个点，无论删去哪条边（只能删去一条）都不能使它们不连通。
  - 边双连通有传递性

原文链接：https://blog.csdn.net/default012/article/details/121425431

基本概念

你可能也喜欢