ciaoly
离散数学 —— 图论

access_time
brush 1982个字
whatshot 26 ℃

离散数学 —— 图论

相关概念

  • 无序积

A, B 为任意集合, 称集合 A\ \&\ B = \{(a, b)|a ∈ A, b ∈ B\}AB 的无序积, (a, b) 称 为无序对

  • 笛卡尔积

A, B 为任意集合, 称集合 A \times B=\{(a,b)|a∈A∧b∈B\}AB 的笛卡尔积, <a, b> 为有序对

图的定义

一个图 (Graph) 是一个序偶 < V, E >,记为 G =< V, E >,其中: V = {v_1, v_2, · · · , v_n} 是有限非空集合,v_i 称为结点 (node),V 称为结点集。 E 是有限集合,称为边集。E 中的每个元素都有 V 中的结点对与之对应,称之为边 (edge)。

说人话呢就是,一个图由一系列结点和结点对应的边构成,其中“边”描述了结点间的相互关系。

若边 e 与无序结点对 (u, v) 相对应, 则称 e无向边(undirected edge), 记为 e = (u, v) = (v, u), 这时称 u, v 是边 e 的两个端点. 若边 e 与有序结点对 < u, v > 相对应,则称 e有向边(directed edge)(或弧), 记为 e =< u, v > , 这时称 ue 的始点 (或弧尾), ve 的终点 (或弧头), 统称为 e 的端点.

子图

设有图 G =< V, E > 和图 G_1 =< V_1, E_1 >.

  • V_1 \subseteq V, E_1 \subseteq E,则称 G_1G子图(subgraph),记为 G_1 \subseteq G.
  • G_1 \subseteq G,且 G_1 \neq G(即 V_1 \subset VE_1 \subset E),则称 G_1G真子图(proper subgraph),记为 G_1 \subset G.
  • V_1 = V, E_1 \subseteq E,则称 G_1G生成子图(spanning subgraph).

可见生成图包含所有的结点

  • V_2 \subseteq VV_2 \neq \emptyset,以 V_2 为结点集,以两个端点均在 V_2 中的边的全体为边集的 G 的子图,称为 V_2 导出的 G 的子图,简称 V_2导出子图(induced subgraph).

多重图、线图和简单图

  • 平行边
    • 在有向图中,两结点间 (包括结点自身间) 若有同始点和同终点的几条边,则这几条边称为平行边;
    • 在无向图中,两结点间 (包括结点自身间) 若有几条边,则这几条边称为平行边。两结点 a、b 间相互平行的边的条数称为边 (a, b) 或 的重数。

含有平行边的图称为多重图(multi graph);非多重图称为线图(line graph);无环的线图称为简单图(simple graph)。

完全图和补图

G =< V, E > 为一个具有 n 个结点的无向简单图,如果 G任意两个结点间都有边相连,则称 G 为无向完全图,简称 G 为完全图,记为 K_n。 设 G =< V, E > 为一个具有 n 个结点的有向简单图,如果 G任意两个结点间都有两条方向相反的有向边相连,则称 G 为有向完全图,在不发生误解的情况下,也记为 K_n

  • 完全图的性质

    1. 完全图的邻接矩阵除主对角线上的元素为 0 外,其余元素均为 1;
    2. 无向完全图 K_n 的边数为 C^2_n =\frac{n(n − 1)}{2};
    3. 有向完全图 K_n 的边数为 P^2_n = n(n − 1).

补图

G =< V, E > 为简单图,G =< V, E_1 > 为完全图,则称G_1 =< V, E_1 − E >G的补图(complement of graph),记为\bar{G}

  • 补图的性质
    1. 补图 \bar{G} 就是从完全图中删除图 G 中的边;
    2. G 和它的补图 \bar{G} 有相同的结点,两个结点在 \bar{G} 里相邻,当且仅当它们在 G 里不相邻.

若设简单图 G 的邻接矩阵 A = (a_{ij})n\times n,则它的补图 G 的邻接矩阵 A = (a_{ij})n\times n为:

\bar{a_{ij}} = \left \{ \begin{aligned} 1 − a_{ij} &, i\neq j \\ 0 \ &, i = j \end{aligned} \right. ,(i, j = 1, 2, 3, · · · , n)

补图描述了结点间互斥的关系

度数、边数与结点数

度的定义

G =< V, E > 中以结点 v \in V 为端点的次数之和称为结点 v 的度数或度,记为deg(v)。显然,有环时则需计算两次。 有向图 G =< V, E > 中以结点 v 为始点的次数称为 v 的出度,记为 deg^+(v) ; 以结点 v 为终点的次数称为 v 的入度,记为 deg^−(v)。显然,deg(v) = deg^+(v) + deg^−(v)

在计算无向图的度时,入度和出度的符号是一样的。

度数为 1 的结点称为悬挂结点,以悬挂结点为端点的边称为悬挂边。

握手定理(选择题计算)

  • 无向图所有结点的度数之和等于边的两倍
    • 推论:度数为奇数的结点个数为偶数
  • 有向图各结点的出度和等于入度和等于边数

图的表示法

  • 邻接矩阵法

设图 G =< V,E >,其中 V = {v_1,v_2,··· ,v_n}, 并假定结点已经有了从 v_1v_n 的次序, 则 n 阶 方阵 A_G = (a_{ij})_{n\times n} 称为 G 的邻接矩阵 (adjacency matrix),其中

a_{ij} = \left \{ \begin{aligned} 1 &, <v_i,v_j> \in E\ \ or\ \ (v_i,v_j) \in E , \\ 0 &, others \end{aligned} \right.

不加约定的,邻接矩阵只能表示“线图”。

图的连通

通路和回路定义

给定图 G =< V,E > 中结点和边相继交错出现的序列

\Gamma = v_0e_1v_1e_2v_2···e_kv_k
  1. \Gamma 中边 e_i 的两端点是 v_{i−1}v_i(有向图时 v_{i−1}v_i 分别是 e_i 的始点和终点), i = 1,2,··· ,k则称 \Gamma 为结点 v_0 到结点 v_k 的通路。v_0v_k 分别称为此通路的始点和终点,统称为通路的端点。通路中边的数目 k 称为此通路的长度。当 v_0 = v_k 时,此通路称为回路
  2. 若通路中的所有边互不相同,则称此通路为简单通路, 否则称为复杂通路;若回路中的所有边互不相同,则称此回路为简单回路, 否则称为复杂回路
  3. 若通路中的所有结点互不相同,所有边也互不相同,则称此通路为基本通路或者初级通路; 若回路中除 v_0 = v_k 外的所有结点互不相同, 所有边也互不相同,则称此回路为基本回路或者初级回路。

通路数量的计算 (下文的基础)

G =< V,E > 为线图,V = {v_1,v_2,··· ,v_n}A = (a_{ij})_{n\times n}G 的邻接矩阵, A^m = (a^{(m)}_{ij} )_{n\times n},给定一个通路长度m ,(其中,A^m 为矩阵 Am次幂(矩阵乘法))则:

  1. a^{(m)}_{ij} 为从结点 v_i 到结点 v_j 长度为 m 的通路数目;
  2. a^{(m)}_{ii} 为结点 v_i 到自身的长度为 m 的回路数目;
  3. \sum_{i=1}^n\sum_{j=1}^na^{(m)}_{ij}G 中长度为 m 的通路(含回路)总数.
  4. \sum_{i=1}^n a^{(m)}_{ii}G 中长度为 m 的回路总数.

计算长度不大于 m 的通路数

设矩阵 B_m = (b_{ij})_{n\times n} = A+A_2 +···+A_m(m\geq 1), 则 b_{ij} 表示结点 v_iv_j 长度不大于 m 的通路数目,而 \sum^n_{i=1}\sum^n_{j=1}b_{ij} 则可表示图中长度不大于 m 的通路总数, \sum^n_{i=1}bii 则可表示图中所有长度不大于 m 的回路总数。

连通性的计算与判断

可达关系判定-引理

  • 在一个具有 n 个结点的图中,如果从结点 v_i 到结点 v_j(v_i \neq v_j) 存在一条通路,则从 v_iv_j 存在一条长度不大于 n−1通路/基本通路.

  • 在一个具有 n 个结点的图中,如果存在经过结点 v_i 回路,则存在一条经过 v_i 的长度不大于 n回路/基本回路

说人话就是,在一个图中,最多存在 n-1 个通路或者 n 个回路

可达性关系判定

G =< V,E > 为线图,V = {v_1,v_2,··· ,v_n},A = (a_{ij})_{n\times n}G 的邻接矩阵,

A^m = (a^{(m)}_{ij} )_{n\times n}, m = 1,2,··· ,n \\ B^n = (b^{(n)}_{ij} )_{n\times n} = A+A_2+A_3+···+A_n

则有当 v_i \neq v_j 时,如果 b^{(n)} > 0 ,则从 v_iv_j可达,否则不可达.

可达性矩阵及其简化求法

G =< V,E > 是一个线图,其中 V = {v_1,v_2,··· ,v_n},并假定结点已经有了从 v_1v_n 的次序,称 n 阶方阵 P = (p_{ij})_{n\times n} 为图 G 的 可达性矩阵(accessibility matrix),其中

p_{ij} = \left \{ \begin{aligned} 1 &, v_i to v_j accessable \\ 0 &, Others \end{aligned} \right.

由于计算可达性矩阵时需要进行多次乘加法运算,但是可达性矩阵最终是个布尔矩阵,因此可以考虑使用布尔运算进行简化:

G =< V,E > 为线图,A, P 分别是 G 的邻接矩阵和可达性矩阵,则有 P = A\land A^2 \land A^3 \land ···\land A^n, 这里,A^i 表示做矩阵布尔乘法的 i 次幂.

节点间距离与计算

如果 v_iv_j 可达,则称长度最短的通路为从 v_iv_j 的短程线,从 v_iv_j 的短程线的长度称为从 v_iv_j 的距离(distance),记为 d(v_i,v_j)。如果 v_iv_j 不可达,则通常记为 d(v_i,v_j) = \infty

  • 性质

    1. d(v_i,v_j) \geq 0
    2. d(v_i,v_i) = 0
    3. d(v_i,v_k) +d(v_k,vj) \geq d(v_i,v_j)
    4. 无向图满足 d(v_i,v_j) = d(v_j,v_i),而有向图不行
  • 计算

G =< V,E > 为线图,V = {v_1,v_2,··· ,v_n}, A = (a_{ij})_{n\times n}G 的邻接矩阵, A^m = (a^{(m)}_{ij} )_{n\times n}, m = 1,2,··· ,n

d(v_i, v_j) = \left \{ \begin{aligned} \infty &, \ a^{(m)}_{ij} = 0 \\ k &, \ k = min\{m|\ a^{(m)}_{ij} \neq 0\} ,(m = 1,2,3,··· ,n) \end{aligned} \right.

显然,这里也可以使用邻接矩阵的布尔积幂来判定

总结

以上内容说人话呢就是,利用“通路数量的计算”方法,如果要判断两节点间“可达性”,则只需要铁憨憨地将“路径长度”从 0 算到 n-1 (回路的话是 n),只要能算出来至少一条路径,就说明它可达;而计算"距离"则只需要严格的从 0 开始算到 n-1 即可,第一次算出的非0结果即为最短距离

有向图的连通性

若无向图 G 中的任何两个结点都是可达的,则称 G 是连通图,否则称 G 是非连通图或分离图。

  • 性质
    1. 无向完全图 K_n(n \geq 1) 都是连通图;
    2. 多于一个结点的零图都是非连通图;
    3. 非平凡无向线图 G 是连通图当且仅当它的可达性矩阵 P 的所有元素均为 1

无向图的连通性

#如无特别声明,该文章均为 ciaoly 原创,转载请遵循 署名-非商业性使用 4.0 国际(CC BY-NC 4.0) 协议,即转载请注明文章来源。
#最后编辑时间为: 2019 年 10 月 12 日


create 添加新评论


account_circle
email
language
textsms





关于 DreamCat

主题名称:DreamCat | 版本:X2.6.220211

主题开发:HanFengA7 | TeddyNight | Dev-Leo | CornWorld | WhiteBearcn | DFFZMXJ

Designed by HanFengA7 Power by Typecho

Copyright © 2015-2022 by LychApe All rights reserved!

加我的QQ
加我的微博
加我的支付宝
加我的微信