《图论与网络优化》学习笔记(第1-5章)

这篇具有很好参考价值的文章主要介绍了《图论与网络优化》学习笔记(第1-5章)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

《图论与网络优化》学习笔记(第1-5章)

上课时间:2023年10月——2024年1月
上课地点:国防科技大学
授课老师:戴丽
教材:戴丽.《图论与网络优化》
注:部分笔记根据自己的理解进行改动,可能不是很严谨,但便于理解。

第一章 图论发展历史

1.1 图论的起源与发展

1736年,Euler研究并解决了konigsberg七桥问题(格林森堡七桥问题)。20世纪图论经历了一场爆炸性的发展,1936年第一本图论著作《有限图和无限图理论》诞生。

  • 电网络中的图论
  • 有机化学中的图论
  • 四色问题

1.2 图论的现状与应用

图论具有很高的实用价值,例如:地图导航、人物关系图、蛋白质网络图、无人机集群网络图等。

第二章 基本概念与运算

2.1 图的定义

图的组成:
:图 G G G 是一个有序的三元组,记作 G = < V ( G ) , E ( G ) , ψ ( G ) > G = <V(G), E(G), \psi(G)> G=<V(G),E(G),ψ(G)>
顶点集:表示为 V ( G ) V(G) V(G) ,顶点数表示为 ν ( G ) \nu(G) ν(G)
边集:表示为 E ( G ) E(G) E(G) ,边数表示为 ϵ ( G ) \epsilon(G) ϵ(G)
关联函数:表示为 ψ ( G ) = { u v ∣ u ∈ V ( G ) , v ∈ V ( G ) , u ≠ v } \psi(G) = \{uv | u \in V(G), v \in V(G), u \neq v\} ψ(G)={uvuV(G),vV(G),u=v} ,也就是顶点对表示的边集。

关联,端点,相邻:设 e e e 是图 G G G 中的边, u , v u,v u,v 为顶点,且 ψ ( e ) = u v \psi(e) = uv ψ(e)=uv ,则称 e e e u u u v v v 关联,称 u u u v v v e e e 的端点,称 u u u v v v 是相邻的。
邻域:图 G G G 中所有与顶点 ν \nu ν 相邻的顶点的集合称为 ν \nu ν 的邻域,记作 N ( ν ) N(\nu) N(ν)
:两个端点重合的边称为环。
连杆:两个端点不重合的边称为连杆。
k k k重边:连接同一对顶点的 k ( k ≥ 2 ) k(k\ge2) k(k2) 条边称为 k k k重边。
单边:若一对顶点之间只有一条边,该边称为单边。
简单图:既没有环,也没有重边的图,称为简单图。

:与顶点 v v v 关联的边的数目称为顶点的度,记作 d ( v ) d(v) d(v)
度序列:若 v 1 , v 2 , . . . , v ν v_1,v_2,...,v_\nu v1,v2,...,vν 为图的全部顶点,则 ( d ( v 1 ) , d ( v 2 ) , . . . , d ( v ν ) ) (d(v_1),d(v_2),...,d(v_\nu)) (d(v1),d(v2),...,d(vν)) 为图的度序列。
孤立点:度为 0 的顶点称为孤立点。
悬挂点:度为 1 的顶点称为悬挂点。
悬挂边:与悬挂点相关联的边称为悬挂边。
偶点:度为偶数的顶点称为偶点。
奇点:度为奇数的顶点称为奇点。
最大度:图 G G G 中顶点度的最大值,记作 Δ ( G ) \Delta(G) Δ(G)
最小度:图 G G G 中顶点度的最小值,记作 δ ( G ) \delta(G) δ(G)

定理1 握手引理 对于任意图 G G G ,均有 ∑ v ∈ V d ( V ) = 2 ϵ \textstyle\sum_{v\in V}d(V) = 2\epsilon vVd(V)=2ϵ 。(顶点的度数和等于边数的两倍)

图序列:简单图的度序列称为图序列。
同构:如果能够在两个图 G 1 G_1 G1 G 2 G_2 G2 的顶点集之间建立一一对应关系,并且每对顶点之间的边数对应相等,则称 G 1 G_1 G1 G 2 G_2 G2 是同构的,表示为 G 1 ≊ G 2 G_1 \approxeq G_2 G1G2

定理2 (给出一个顶点度的序列,判断能否构成图)
非负整数序列 ( d 1 , d 2 , . . . , d ν ) ( d 1 ≥ d 2 ≥ . . . , ≥ d ν ) (d_1,d_2,...,d_\nu)(d_1 \ge d_2 \ge ...,\ge d_\nu) (d1,d2,...,dν)(d1d2...,dν) 是图序列当且仅当 ∑ i = 1 ν d i \sum_{i=1}^{\nu}d_i i=1νdi 是偶数,并且对于一切整数 k ( 1 ≤ k ≤ ν − 1 ) k(1 \le k \le \nu -1) k(1kν1) ,有 ∑ i = 1 k d i ≤ k ( k − 1 ) + ∑ i = k + 1 ν m i n { k , d i } \sum_{i=1}^kd_i\le k(k-1)+\sum_{i=k+1}^{\nu}min\{k,d_i\} i=1kdik(k1)+i=k+1νmin{k,di}

2.2 子图和连通分支

子图相关概念:
子图:设 H H H G G G 是两个图,若 V ( H ) ⊆ V ( G ) V(H) \subseteq V(G) V(H)V(G) E ( H ) ⊆ E ( G ) E(H) \subseteq E(G) E(H)E(G) ,则称 H H H G G G 的子图,记作 H ⊆ G H \subseteq G HG
图的相等:两个图的顶点和边都对应相等,则称 H H H G G G 相等,记作 H = G H = G H=G
真子集:若 H ⊆ G H \subseteq G HG H ≠ G H \neq G H=G ,则称 H H H G G G 的真子图,记作 H ⊂ G H \subset G HG
支撑子图 / 生成子图:若图 H H H 包括了图 G G G 全部顶点和部分边,则称 H H H G G G 的支撑子图。
基础简单图:不含环且不含重边的图为基础简单图。
导出子图:由图 G G G 的部分顶点或部分边导出的子图。
顶点导出子图:取出图 G G G 的部分顶点,连接两端都与这些顶点相邻的边,生成顶点导出子图 H H H
边导出子图:取出图 G G G 的部分边,加入这些边相邻的顶点,生成边导出子图 H H H

连通分支相关概念:
途径:图 G G G 的途径是一个有限的非空序列 W = v 0 e 1 v 1 e 2 v 2 . . . e k v k W=v_0e_1v_1e_2v_2...e_kv_k W=v0e1v1e2v2...ekvk ,其中 v n v_n vn G G G 中的顶点, e n e_n en G G G 中的边,也可简化记为 W = v 0 v 1 v 2 . . . v k W=v_0v_1v_2...v_k W=v0v1v2...vk v 0 v_0 v0 称为 W W W起点 v k v_k vk 称为 W W W终点,其他的点称为内部点 k k k 称为 W W W
:如果途径 W W W 的边互不相同,则 W W W 称为迹。(允许经过同一顶点)
:如果途径 W W W 的顶点互不相同,则 W W W 称为链。(链必然也是迹)一个顶点也是一条链
闭途径:起点与终点重合的途径。
闭迹:起点与终点重合的迹。
:起点、内部点互不相同的闭迹称为圈,长为 k k k 的圈称为 k k k k k k 为奇数则为奇圈 k k k 为偶数则为偶圈
连通图:若图 G G G 中存在 ( u , v ) (u, v) (u,v) 链,则称顶点 u u u v v v 在图 G G G 中是连通的。图中所有顶点都互相连通的图称为连通图。
连通分支:依据连通性将顶点集 V V V 划分为 V 1 , V 2 . . . V ω V_1,V_2...V_\omega V1,V2...Vω ,导出子图 G [ V 1 ] , G [ V 2 ] . . . G [ V ω ] G[V_1],G[V_2]...G[V_\omega] G[V1],G[V2]...G[Vω] 称为 G G G 的连通分支。 ω ( G ) \omega(G) ω(G) 表示图 G G G 的连通分支数。
距离:顶点 u u u v v v 之间的最短链 ( u , v ) (u, v) (u,v) 的长为 u , v u, v u,v 之间的距离,记作 d ( u , v ) d(u, v) d(u,v)

2.3 重要图类

完全图:每对顶点都相邻的简单图为完全图,记作 K n K_n Kn
空图:边集为空的图。
平凡图:图中只有一个顶点的图。
非平凡图:不是平凡图的一切图。(顶点数大于1)

练习 证明:在任意6个人的聚会上,要么有3个人互相认识,要么有3个人互相不认识。

正则图:每个顶点的度都相等的图称为正则图。每个顶点的度都为 k k k 的正则图称为 k k k正则图
τ 1 \tau1 τ1法则(偶数正则图生成法则)
τ 2 \tau2 τ2法则(奇数正则图生成法则)

定理1 n n n k k k正则简单图存在的充要条件是 k ≤ n − 1 k \le n-1 kn1 n k nk nk 为偶数。

练习 证明: n n n k k k正则图一定存在,当且仅当对于任意的正整数 n n n ,若 n k nk nk 为偶数,且 n ≥ k + 1 n \ge k+1 nk+1

二部图:设图 G G G 的顶点集可以划分成两个子集 X X X Y Y Y ,使得 G G G 中每条边的一个端点在 X X X 中,另一个端点在 Y Y Y 中,则称 G G G 图为二部图,记作 G = ( X , Y , E ) G=(X,Y,E) G=(X,Y,E)
完全二部图:若 X X X 中每个顶点与 Y Y Y 中每个顶点之间都恰有一条边,且 ∣ X ∣ = m ≠ 0 |X|=m\neq 0 X=m=0 ∣ Y ∣ = n ≠ 0 |Y|=n\neq 0 Y=n=0 ,则称二部图 G G G 为完全二部图,记作 K m , n K_{m,n} Km,n

定理2 二部图的判断
G G G 是二部图,当且仅当 G G G 中不含奇圈。

2.4 有向图

有向图的组成:
有向图:有向图 D D D 是一个有序三元组,记作 ( V ( D ) , A ( D ) , ψ D ) (V(D),A(D),\psi_D) (V(D),A(D),ψD)
顶点集:记作 V ( D ) V(D) V(D) ,其元素为 D D D 的顶点。
弧集:记作 A ( D ) A(D) A(D) ,其元素为 D D D 的弧(即有向边)。
关联函数:表示弧 a a a 与有序顶点 ( u , v ) (u,v) (u,v) 对之间的关系,记作 ψ D ( a ) = ( u , v ) \psi_D(a)=(u,v) ψD(a)=(u,v) ,其中 u u u 称为 a a a 的尾, v v v 称为 a a a 的头。

基础图:将有向图 D D D 的弧的方向都去掉,称为是 D D D 的基础图。
定向图:给无向图 G G G 的边加上方向,称为是 G G G 的定向图。
入弧、出弧、入度、出度:以顶点 v v v 为头(指向 v v v )的弧称为入弧;以顶点 v v v 为尾(离开 v v v )的弧称为出弧。顶点 v v v 的入弧总数称为顶点 v v v 的入度,记作 d D − ( v ) d_D^-(v) dD(v) ;顶点 v v v 的出弧总数称为顶点 v v v 的出度,记作 d D + ( v ) d_D^+(v) dD+(v)

定理 对于任何有向图 D D D ,所有顶点的入度总和等于出度总和,即 ∑ v ∈ V d D − ( v ) = ∑ v ∈ V d D + ( v ) = ϵ ( D ) \displaystyle\sum_{v \in V}d_D^-(v)=\displaystyle\sum_{v \in V}d_D^+(v)=\epsilon(D) vVdD(v)=vVdD+(v)=ϵ(D)

回路相关概念:
有向途径:将途径概念中的图 G G G 替换为有向图 D D D ,边 e e e 替换为弧 a a a ,则 W W W 为有向途径。其中, v 0 v_0 v0 称为 W W W起点 v k v_k vk 称为 W W W终点 k k k 称为 W W W
有向闭途径:起点与终点相同的途径。
有向迹:弧互不相同的有向途径。
有向链 / 有向路:顶点互不相同的有向途径。
有向闭迹/回路:起点与终点重合的有向迹。

强连通概念:
强连通:若在 D D D 中既存在 ( u , v ) (u,v) (u,v) 路,又存在 ( v , u ) (v,u) (v,u) 路,则称 u u u v v v D D D 中是强连通的。(两点之间互相可到达)
强连通分支:由强连通关系确定顶点集 V ( D ) V(D) V(D) 的非空划分 V 1 , V 2 , . . . , V ω V_1,V_2,...,V_{\omega} V1,V2,...,Vω ,它们在 D D D 中所导出的顶点子图 D [ V 1 ] , D [ V 2 ] , . . . , D [ V ω ] D[V_1],D[V_2],...,D[V_{\omega}] D[V1],D[V2],...,D[Vω] 称为 D D D 的强连通分支。
强连通有向图:只有一个强连通分支的有向图称为强连通有向图。

2.5 矩阵表示

邻接矩阵 ν \nu ν 阶图 G G G 的邻接矩阵 A ( G ) = ( a i j ) A(G) = (a_{ij}) A(G)=(aij) 是一个 ν × ν \nu \times \nu ν×ν 矩阵,其中 a i j a_{ij} aij 等于第 i i i 个顶点与第 j j j 个顶点之间的边数。
有向图的邻接矩阵:在邻接矩阵的基础上, a i j a_{ij} aij 等于以第 i i i 个顶点为尾、以第 j j j 个顶点为头的弧数。

邻接矩阵的性质:
(1) A ( G ) A(G) A(G) 是一个以非负整数为元素的 ν \nu ν 阶对称矩阵,即 A T ( G ) = A ( G ) A^T(G) = A(G) AT(G)=A(G)
(2) G G G 中第 i i i 个顶点的度等于 2 a i i + ∑ j ≠ i a i j 2a_{ii} + \sum_{j\neq{i}}a_{ij} 2aii+j=iaij 。(对角线上为环)
(3)图 G G G 中多个连通分支的邻接矩阵可以表示为对角块的形式。

有向图邻接矩阵的性质:
(1) A ( D ) A(D) A(D) 是一个以非负整数为元素的 ν \nu ν 阶方阵,但不一定是对称的。
(2) D D D 中第 i i i 个顶点的出/入度等于第 i i i 行/列元素之和。
(3)有向图 D D D 中多个连通分支的邻接矩阵可以表示为对角块的形式。

定理 邻接矩阵的 r 次方 A r ( G ) / A r ( D ) A^r(G) / A^r(D) Ar(G)/Ar(D) 表示对应顶点之间长度为 r 的不同途径的个数。

Laplace拉普拉斯矩阵:设 G G G 为非空无环图, A ( G ) A(G) A(G) 为图 G G G 的邻接矩阵,对角矩阵 D ( G ) D(G) D(G) 的对角线上元素为对应顶点的度,则称 L ( G ) = D ( G ) − A ( G ) L(G) = D(G) - A(G) L(G)=D(G)A(G) 为图 G G G 的Laplace矩阵。

Laplace矩阵的性质:
(1)Laplace矩阵对角线上的值为顶点的度,非对角线上的值为对应顶点之间边数的负数。
(2)Laplace矩阵每行元素的和为 0 。
(3)Laplace矩阵的 0 特征值重数是图的连通分支个数 ω \omega ω 。(其特征值大于等于0,且一定包含0)

关联矩阵:设 G G G 是具有 ν \nu ν 个顶点和 ϵ \epsilon ϵ 条边的非空无环图, G G G 的关联矩阵 M ( G ) = ( m i j ) M(G) = (m_{ij}) M(G)=(mij) 是一个 ν × ϵ \nu \times \epsilon ν×ϵ 矩阵,其中 m i j m_{ij} mij 为 1 表示第 i i i 个顶点与第 j j j 条边关联,否则为 0。
有向图的关联矩阵:在关联矩阵的基础上, m i j m_{ij} mij 为 1 表示第 i i i 个顶点为第 j j j 条边的尾,为 -1 表示第 i i i 个顶点为第 j j j 条边的头,否则为 0。

关联矩阵的性质:
(1) M ( G ) M(G) M(G) 的每列恰好包含两个1。
(2) M ( G ) M(G) M(G) 中每行所包含的1的个数等于对应顶点的度。
(3)非空无环图 G G G 中多个连通分支的关联矩阵可以表示为对角块的形式。

有向图的关联矩阵的性质:
(1) M ( D ) M(D) M(D) 的每列恰好包含一个 1 和一个 -1,其他为 0。
(2) M ( D ) M(D) M(D) 中每行所包含的 1 的个数等于对应顶点的出度,所包含的 -1 的个数等于对应顶点的入度。
(3)非空无环有向图 D D D 中多个连通分支的关联矩阵可以表示为对角块的形式。

最短路径相关概念:
:若图中的每一条边 e e e 都对应于一个实数 W ( e ) W(e) W(e) ,则 W ( e ) W(e) W(e) 称为边 e e e 的权。
无向网络:带权的无向图称为无向网络。
有向网络:带权的有向图称为有向网络。
正权网络:若网络的每条边的权都为正数,则称为正权网络。
最短路:一条路上的所有边对应的实数之和 ∑ W ( e i ) \sum{W(e_i)} W(ei) 为路的权。对于顶点 v i v_i vi v j v_j vj ,在网络所有的 ( v i , v j ) (v_i, v_j) (vi,vj) 路中,权最小的路称为 ( v i , v j ) (v_i, v_j) (vi,vj) 之间的最短路。

Dijkstra算法:

《图论与网络优化》学习笔记(第1-5章),学习笔记,图论,网络,学习

2.6 运算

边的删除 G − F G - F GF 表示从图 G G G 中将边集 F F F 删除,若 F = { e } F = \{e\} F={e} 则可简写为 G − e G - e Ge 。(删除边操作后得到的必然是支撑子图)
边的添加 G + F G + F G+F 表示在图 G G G 中添加边集 F F F
顶点的删除 G − S G - S GS 表示从图 G G G 中删除顶点集 S S S 及与 S S S 中顶点关联的所有边后得到的图。
顶点的添加 G + S G + S G+S 表示在图 G G G 中添加顶点集 S S S
图的交 G 1 ∩ G 2 = ( V 1 ∩ V 2 , E 1 ∩ E 2 ) G_1 \cap G_2 = (V_1 \cap V_2, E_1 \cap E_2) G1G2=(V1V2,E1E2)
图的并 G 1 ∪ G 2 = ( V 1 ∪ V 2 , E 1 ∪ E 2 ) G_1 \cup G_2 = (V_1 \cup V_2, E_1 \cup E_2) G1G2=(V1V2,E1E2)
图的收缩:设 e = u v e = uv e=uv 是图 G G G 的一条连杆,在 G G G 中去掉 e e e ,把顶点 u u u v v v 合并为一个新顶点,将除 e e e 以外其他与顶点 u , v u, v u,v 关联的边都与新顶点关联,就完成了图的收缩,记作 G ⋅ e G \cdot e Ge
图的剖分:去掉边 e e e ,然后添加一个顶点,分别与原先 e e e 的两个端点连边,就完成了对边 e e e 的剖分。
笛卡尔积:设 G 1 G_1 G1 G 2 G_2 G2 分别为两个图,则它们的笛卡尔积表示为 G 1 × G 2 = ( V 1 × V 2 , E 1 × E 2 ) G_1 \times G_2 = (V_1 \times V_2, E_1 \times E_2) G1×G2=V1×V2E1×E2 。(笛卡尔积可用于生成 n n n立方体)

第三章 树及其算法

3.1 树和森林

:连通且不含圈的图称为树,通常用 T T T 表示树。
n阶树:含有 n n n个顶点的树。
森林:不含圈的图(无圈图),每个连通分支都是树。
支撑树:若图 G G G 的支撑子图 T T T 是树,则称 T T T G G G 的支撑树。

从图中获得支撑树的方法:
破圈法:将连通图 G G G 中的圈上的任意一条边删除,重复这个过程直到无圈,得到一个支撑树。
避圈法:从空图出发,每次添加一条确保无圈的边,重复这个过程直到加入所有顶点且连通,得到一个支撑树。

定理1 G G G 有支撑树当且仅当 G G G 连通

定理2 树的六个等价定义
T T T ν \nu ν 阶图,下列命题等价:

  1. T T T 是树;
  2. T T T 是无环图,且 T T T 的任何两个顶点间有唯一一条链;
  3. T T T 是无圈图,且有 ν − 1 \nu - 1 ν1 条边;
  4. T T T 是连通图,且有 ν − 1 \nu - 1 ν1 条边;
  5. T T T 是连通图,但 ∀ e ∈ E ( T ) \forall e \in E(T) eE(T) T − e T - e Te 是非连通图;
  6. T T T 是无圈图,但添加任何一条边后得到的图中将含有唯一的圈。
    (证明方式:1 ⇒ 2 ⇒ 3 ⇒ 4 ⇒ 5 ⇒ 6 ⇒ \Rightarrow 2 \Rightarrow 3 \Rightarrow 4 \Rightarrow 5 \Rightarrow 6 \Rightarrow 23456 1)

推论一:若树 T T T 的阶数 ν ≥ 2 \nu \ge 2 ν2,则 T T T 至少有两个悬挂点。

推论二:设 G G G ν \nu ν 个顶点, ϵ \epsilon ϵ 条边, ω \omega ω 个连通分支,则 G G G 是森林当且仅当 ϵ = ν − ω \epsilon = \nu - \omega ϵ=νω

常用的证明方法:反证法、数学归纳法、分类讨论法、极大极小值原则

3.2 支撑树的计数(给定一个图,判断其互不同构的支撑树的个数)

表示:在图 G G G 中,互不同构的支撑树的个数记作 τ ( G ) \tau(G) τ(G)

  1. 公式法(递推公式):

定理3 e e e G G G 的连杆,则 τ ( G ) = τ ( G − e ) + τ ( G ⋅ e ) \tau(G) = \tau(G - e) + \tau(G \cdot e) τ(G)=τ(Ge)+τ(Ge)
eg.:
《图论与网络优化》学习笔记(第1-5章),学习笔记,图论,网络,学习

  1. 矩阵-树定理:

定理4 G G G 为非空无环连通图,则 τ ( G ) = ∣ L i ( G ) ∣ \tau(G) = |L_i(G)| τ(G)=Li(G) ,其中 L i ( G ) L_i(G) Li(G) 表示删去Laplace矩阵 L ( G ) L(G) L(G) 的第 i i i 行和第 i i i 列后得到的矩阵。

  1. n n n 阶完全图的支撑树个数:

定理5 n n n 阶完全图 K n K_n Kn 的互不相同的支撑树个数 τ ( K n ) = n n − 2 \tau(K_n) = n^{n-2} τ(Kn)=nn2

3.3 树上点和边的性质

割边:图 G G G 中使 ω ( G − e ) > ω ( G ) \omega(G - e) > \omega(G) ω(Ge)>ω(G) 的边 e e e 称为 G G G 的割边。(使连通分支个数增加)

引理1(1) ∀ e ∈ E ( G ) \forall e \in E(G) eE(G) ,有 ω ( G ) ≤ ω ( G − e ) ≤ ω ( G ) + 1 \omega(G) \le \omega(G-e) \le \omega(G)+1 ω(G)ω(Ge)ω(G)+1
引理1(2) e e e G G G 的割边 ⇔ ω ( G − e ) = ω ( G ) + 1 \Leftrightarrow \omega(G-e) = \omega(G)+1 ω(Ge)=ω(G)+1

定理1 e ∈ E ( G ) e \in E(G) eE(G) 是图 G G G 的割边,当且仅当 e e e 不在 G G G 的任何圈上。

利用割边可以把树的等价定义第五条表述为: T T T 为树 ⇔ T \Leftrightarrow T T 的每条边都是割边的连通图。

边割:将顶点集 V ( G ) V(G) V(G) 划分为非空子集 S S S S ˉ \bar{S} Sˉ ,边割表示 S S S S ˉ \bar{S} Sˉ 之间所有的边,即 [ S , S ˉ ] = { u v ∈ E ( G ) ∣ u ∈ S , v ∈ S ˉ } [S, \bar{S}] = \{uv \in E(G) | u \in S, v \in \bar{S}\} [S,Sˉ]={uvE(G)uS,vSˉ}
极小边割 / 补圈 / 余圈:任意真子集都不再是边割的边割。
k-边割:含有 k k k 条边的边割。

定理2 G G G 为连通图,则: G G G 的边割 [ S , S ˉ ] [S, \bar{S}] [S,Sˉ] 是补圈 ⇔ G [ S ] \Leftrightarrow G[S] G[S] G [ S ˉ ] G[\bar{S}] G[Sˉ] 都连通。

推论1 G G G 的边割 [ S , S ˉ ] [S, \bar{S}] [S,Sˉ] 或者是补圈,或者是一些两两不交的补圈的并。

补树:设 G G G 是连通图, T T T G G G 的一个支撑树,则称补图 T ˉ ( G ) \bar{T}(G) Tˉ(G) G G G 的补树,记作 T ˉ \bar{T} Tˉ

定理3 T T T 是连通图 G G G 的支撑树, e ∈ E ( T ) e \in E(T) eE(T) ,则
(1)补树 T ˉ \bar{T} Tˉ 不含有任何极小边割;
(2) T ˉ + e \bar{T} + e Tˉ+e 中含有唯一的极小边割。

割点:把图 G G G 的边集 E E E 分为两个非空子集 E 1 E_1 E1 E 2 E_2 E2 ,使 G [ E 1 ] G[E_1] G[E1] G [ E 2 ] G[E_2] G[E2] 有唯一的公共顶点,则该点为图 G G G 的割点。

引理2(1) 若顶点 v v v 满足 ω ( G − v ) > ω ( G ) \omega(G-v) > \omega(G) ω(Gv)>ω(G) ,则 v v v G G G 的割点。
引理2(2) G G G 的割点 v v v 上无环,则 ω ( G − v ) > ω ( G ) \omega(G-v) > \omega(G) ω(Gv)>ω(G)

定理4 T T T 的顶点 v v v 是割点,当且仅当 d ( v ) > 1 d(v) > 1 d(v)>1

3.4 最小支撑树

最小支撑树:树上所有边权之和为树的权,在图 G G G 的所有支撑树中,权最小的支撑树称为最小支撑树。

最小支撑树的生成算法:
Prim算法(贪婪思想):从空集出发(顶点集和边集都为空),每次添加一条边,满足:(1)不构成圈;(2)与已存在的某条边相邻;(3)在未添加的边集中权尽可能小。
Kruskal算法(贪婪思想):从 ν \nu ν 阶空图出发(边集为空),每次添加一条边,满足:(1)不构成圈;(2)在未添加的边集中权尽可能小。(Kruskal算法过程中的图可以不连通)

定理1 G G G 是连通加权图,由Prim算法构造的支撑树一定是图 G G G 的最小支撑树。

定理2 G G G 是连通加权图,由Kruskal算法构造的支撑树一定是图 G G G 的最小支撑树。

3.5 二叉树与前缀码

:唯一一个入度为0的顶点。
叶子:出度为0的顶点。
根树 T T T 是一棵有向树,且只有一个顶点入度为0,其余顶点入度都为1。
n n n元树:树上所有顶点的出度的最大值,即 ∀ v ∈ V ( T ) , d + ( v ) ≤ n \forall v \in V(T), d^+(v) \le n vV(T),d+(v)n
经典 n n n元树:除叶子顶点外,每个顶点都有 n n n 个儿子的根树。
有序树:每个顶点的儿子们有序的根树。
括号列:由左括号“(”和右括号“)”组成的有限序列
好括号列:满足:(1)空列是好的;(2)若A与B是好括号列,则AB也是;(3)若A是好括号列,则(A)也是;(4)除了上述三种情况下的括号列,再无其它好括号列。

引理1 一个括号列是好括号列的充要条件是它由偶数个括号组成,其中一半是左括号,一半是右括号,且从左向右读这个括号列时,任何时刻读出的右括号个数不超过读出的左括号个数。

引理2 2 n 2n 2n 个括号组成的好括号列个数是 c ( n + 1 ) = 1 n + 1 C 2 n n c(n+1)=\frac{1}{n+1}C_{2n}^n c(n+1)=n+11C2nn ,这个 c ( n + 1 ) c(n+1) c(n+1) 叫做Catalan数。

定理3 n n n 阶有序二元树的个数是Catalan数 c ( n + 1 ) c(n+1) c(n+1)

前缀码:设有一个序列的集合,如果在这个集合中,任何序列都不是另一个序列的前缀,则称这个集合位前缀码。
Huffman树 / 最优二元树:以 v 0 v_0 v0 为根,以 v 1 , v 2 , . . . , v n v_1,v_2,...,v_n v1,v2,...,vn 为叶子的有序二元树中,称 ( v 0 , v i ) (v_0,v_i) (v0,vi) 链的长 l i l_i li 为叶子 v i v_i vi码长。若 v i v_i vi 代表的事物出现的频率为 p i p_i pi ,且 ∑ i = 1 n p i = 1 \sum_{i=1}^np_i=1 i=1npi=1 ,则称使 m ( T ) = ∑ i = 1 n p i l i m(T)=\displaystyle\sum_{i=1}^np_i l_i m(T)=i=1npili 达到最小的有序二元树 T T T带权 p 1 , p 2 , . . . , p n p_1,p_2,...,p_n p1,p2,...,pn 的Huffman树

Huffman树的构造算法

《图论与网络优化》学习笔记(第1-5章),学习笔记,图论,网络,学习《图论与网络优化》学习笔记(第1-5章),学习笔记,图论,网络,学习《图论与网络优化》学习笔记(第1-5章),学习笔记,图论,网络,学习

第四章 最大流及其算法

4.1 容量网络模型

容量网络:容量网络是一个加权有向网络,并且满足:(1)存在唯一一个入度为0的顶点,称为。(2)存在唯一一个出度为0的顶点,称为。(3)每条弧 ( v i , v j ) (v_i,v_j) (vi,vj) 上赋权 c i j c_{ij} cij 是一个非负数,称为弧 ( v i , v j ) (v_i,v_j) (vi,vj)容量
:设 D D D 是一个容量网络, c i j c_{ij} cij 表示弧 ( v i , v j ) (v_i,v_j) (vi,vj) 的容量, f f f 是定义在 D D D 的弧集上的一个函数,使每条弧 ( v i , v j ) (v_i,v_j) (vi,vj) 对应一个非负实数 f i j f_{ij} fij ,满足:(1)相容条件:每条弧上的流量小于其容量(2)守恒条件:每个顶点的流入量等于流出量,则称 f f f 为容量网络 D D D 的一个,称 f i j f_{ij} fij 为弧 ( v i , v j ) (v_i,v_j) (vi,vj) 上的流量
流入量 ∑ ( v i , v j ) ∈ E ( D ) f i j \sum_{(v_i,v_j)\in E(D)} f_{ij} (vi,vj)E(D)fij 称为流入顶点 v j v_j vj 的流入量。
流出量 ∑ ( v j , v i ) ∈ E ( D ) f i j \sum_{(v_j,v_i)\in E(D)} f_{ij} (vj,vi)E(D)fij 称为流入顶点 v j v_j vj 的流出量。
饱和弧、非饱和弧:流量等于容量的弧称为饱和弧,流量小于容量的弧称为非饱和弧。

定理1 在图 D D D 的任意一个流 f f f 中,源的流出量等于汇的流入量。

推论: 弧上的流量之和 = 所有顶点的流入量之和 = 所有顶点的流出量之和。

流值:源的流出量(或汇的流入量)为流 f f f 的流值,记作 v a l ( f ) val(f) val(f)
最大流:容量网络中流值最大的流称为最大流。
( S , S ˊ ) (S, \acute{S}) (S,Sˊ) 表示从 S S S 指向 S ˊ \acute{S} Sˊ 的弧的集合。
:设 D D D 是一个容量网络, S S S D D D 中的一个包含源的顶点子集,其与顶点集的补集为 S ˉ \bar{S} Sˉ ,且汇在 S ˉ \bar{S} Sˉ 中,则记 ( S , S ˉ ) (S, \bar{S}) (S,Sˉ) D D D 的一个截。(等价于一个有方向的边割)
截的容量:截 ( S , S ˉ ) (S, \bar{S}) (S,Sˉ) 中所有弧的容量之和,记作 c ( S , S ˉ ) c(S, \bar{S}) c(S,Sˉ)
截的流量:截 ( S , S ˉ ) (S, \bar{S}) (S,Sˉ) 中所有弧的流量之和,记作 c f ( S , S ˉ ) c_f(S, \bar{S}) cf(S,Sˉ)
最小截:容量达到最小的截。

定理2 任意流值不大于任何一个截的流量 v a l ( f ) ≤ c ( S , S ˉ ) val(f) \le c(S, \bar{S}) val(f)c(S,Sˉ)
可推出公式 c f ( S , S ˉ ) = c f ( S ˉ , S ) + v a l ( f ) ≤ c ( S , S ˉ ) c_f(S,\bar{S})=c_f(\bar{S},S) + val(f) \le c(S, \bar{S}) cf(S,Sˉ)=cf(Sˉ,S)+val(f)c(S,Sˉ) ,即截面 f f f 的流量 = = = 截面的反向流量 + + + 源的流出量 ≤ \le 截面的容量。

规律 流值与截流量相等,当且仅当(1)截 ( S , S ˉ ) (S, \bar{S}) (S,Sˉ) 上的流量与容量相等。(每条弧都饱和)(2)截 ( S ˉ , S ) (\bar{S}, S) (Sˉ,S) 上的流量为0。(每条弧都为0)

4.2 最大流算法

正向弧、反向弧:设 P P P 是容量网络中一条从源 v s v_s vs v t v_t vt 的路,则 P P P 中与规定方向一致的弧称为正向弧,否则称为反向弧。
f f f 饱和路、 f f f 非饱和路:设 P P P 是一条 ( v s , v j ) (v_s,v_j) (vs,vj) 路,如果同时满足:① 对 P P P 中每条正向弧 ( v i , v j ) (v_i,v_j) (vi,vj) f i j < c i j f_{ij}<c_{ij} fij<cij ;② 对 P P P 中每条反向弧 ( v i , v j ) (v_i,v_j) (vi,vj) f i j > 0 f_{ij}>0 fij>0 ,则称 ( v s , v j ) (v_s,v_j) (vs,vj) f f f 非饱和路,否则称为 f f f 饱和路。
f f f 可增路:从源到汇的 f f f 非饱和路 ( v s , v t ) (v_s,v_t) (vs,vt) 称为 f f f 可增路。

定理1 设容量网络 D D D 的源为 v s v_s vs 汇为 v t v_t vt f f f D D D 的一个流,则 f f f 为最大流当且仅当 D D D 中不存在 f f f 可增路。

最大流构造算法(标号法)
Step1:从任意一个流开始,查找 f f f 可增路。
Step2:如果不存在 f f f 可增路,则得到最大流,算法结束;如果查找到一条 f f f 可增路,跳转到下一步。
Step3:令 Δ = m i n { m i n { c i j − f i j ∣ ( v i , v j ) 为正向弧 } , m i n { f i j ∣ ( v i , v j ) 为反向弧 } } \Delta=min\{min\{c_{ij}-f_{ij}|(v_i,v_j)为正向弧\},min\{f_{ij}|(v_i,v_j)为反向弧\}\} Δ=min{min{cijfij(vi,vj)为正向弧},min{fij(vi,vj)为反向弧}} ,修改 f f f 可增路中所有正向弧的流量增加 Δ \Delta Δ ,同时所有反向弧的流量减少 Δ \Delta Δ ,跳转到上一步。

标号法的特点
(1)构造算法结束时获得最小截 ( S , S ˉ ) (S,\bar{S}) (S,Sˉ) ,其中 S S S 为最后一步获得标号的顶点集。
(2)对于整数容量网络,必然在有限步内构造出最大流;对于无理数容量网络,则不能再有限步内停止。

定理2 最大流最小截定理
在任何容量网络 D D D 中,最大流的流值等于最小截的容量。

4.3 最小费用最大流

费用:设容量网络 D D D f f f 是其上的一个流, f i j , c i j , b i j f_{ij},c_{ij},b_{ij} fij,cij,bij 分别为弧 ( v i , v j ) (v_i,v_j) (vi,vj) 上的流量、容量和单位费用,则流 f f f 的费用为 b ( f ) = ∑ ( v i v j ) ∈ E ( D ) f i j b i j b(f)=\displaystyle\sum_{(v_iv_j)\in E(D)}f_{ij}b_{ij} b(f)=(vivj)E(D)fijbij
最小费用最大流:在容量网络 D D D 的所有最大流中,寻找费用最小的流,这样的流称为最小费用最大流。

最小费用最大流构造算法
Step1:从容量网络 D D D 的任何一个最大流出发,
Step2:寻找某个圈,修改该圈上各弧的流量使流值保持不变且费用降低,
Step3:直到网络中不存在这样的圈为止。

增广圈:设容量网络 D D D f f f 是其上的一个流, Q Q Q 是一个具有指定正向的圈, Q + Q^+ Q+ 记为圈 Q Q Q 上正向弧的集合, Q − Q^- Q 记为圈 Q Q Q 上反向弧的集合。若 Q + Q^+ Q+ 中所有弧都满足 c i j > f i j c_{ij}>f_{ij} cij>fij ,并且 Q − Q^- Q 中所有弧都满足 f i j > 0 f_{ij}>0 fij>0 ,则称 δ = m i n { m i n { c i j − f i j ∣ ( v i , v j ) 为正向弧 } , m i n { f i j ∣ ( v i , v j ) 为反向弧 } } \delta = min\{min\{c_{ij}-f_{ij}|(v_i,v_j)为正向弧\},min\{f_{ij}|(v_i,v_j)为反向弧\}\} δ=min{min{cijfij(vi,vj)为正向弧},min{fij(vi,vj)为反向弧}}允许修正量,圈 Q Q Q 为容量网络 D D D 上关于 f f f 的增广圈。
修正流:对每个正向弧的 f i j f_{ij} fij 加上 δ \delta δ ,每个反向弧的 f i j f_{ij} fij 减去 δ \delta δ ,圈外的弧流量不变,得到的新流 f ′ f' f 为修正流。
增广圈的费用 f f f 增广圈的费用 b ( Q , f ) = ∑ ( v i , v j ) ∈ Q + b i j − ∑ ( v i , v j ) ∈ Q − b i j b(Q,f) = \displaystyle\sum_{(v_i,v_j)\in Q^+}b_{ij}-\displaystyle\sum_{(v_i,v_j)\in Q^-}b_{ij} b(Q,f)=(vi,vj)Q+bij(vi,vj)Qbij
负圈:费用小于0的增广圈称为负圈。

定理3 f f f 是最小费用最大流当且仅当任何 f f f 增广圈 Q Q Q 的费用 b ( Q , f ) ≥ 0 b(Q,f)\ge 0 b(Q,f)0 ,即无负圈。

Klein算法
Step1:求容量网络 D D D 的一个最大流;
Step2:寻找网络中的负圈,若没有负圈,算法结束;若找到一个负圈 Q Q Q ,跳到 Step3。
Step3:修改负圈 Q Q Q 上各弧的流量得到修正流,转 Step2,继续寻找负圈。

第五章 遍历性及其算法

5.1 Euler图

Euler图/欧拉图:若图 G G G 中存在一条包含所有边的闭迹 W W W ,则称 G G G 为Euler图, W W W 称为 G G GEuler闭迹
半Euler图:若图 G G G 中存在一条包含所有边的迹 P P P ,则称 G G G 为半Euler图, P P P 称为 G G GEuler迹

定理1 G G G 是非空连通图,则下面三个命题等价:
(1) G G G 是Euler图;
(2) G G G 中不含奇点;
(3) G G G 可以表示为若干个没有公共边的圈的并。

有向Euler图:若图 D D D 中存在一条包含所有弧的有向闭迹 W W W ,则称 G G G 为有向Euler图, W W W 称为 G G G有向Euler闭迹
有向半Euler图:若图 D D D 中存在一条包含所有弧的有向迹 P P P ,则称 G G G 为有向半Euler图, P P P 称为 G G G有向Euler迹

定理2 D D D 是非空连通有向图,则下面三个命题等价:
(1) D D D 是有向Euler图;
(2) D D D 中所有顶点的入度等于出度;
(3) D D D 可以表示为若干个弧不交的回路的并。

推论1 连通有向图 D D D 是有向半Euler图而不是有向Euler图,当且仅当(1)起点的出度=入度+1,终点的入度=出度+1;(2)其他中间点的入度等于出度。

Fleury算法:从任意顶点出发,除非别无选择,总是选择一条不是割边(在圈上)且没走过的边,直到获得Euler闭迹为止。

定理3 G G G 是Euler图, W = v 0 e 1 v 1 . . . e n v n W=v_0e_1v_1...e_nv_n Wv0e1v1...envn 是Fleury算法结束时得到的迹,则 W W W 一定是图 G G G 的Euler闭迹。

Euler图的应用:

编码盘设计问题:对于一个四位二进制编码盘,如何设计盘上16个位置的0/1,使得盘转一周后刚好遍历 2 4 2^4 24 种编码?
解决方案
Step1:定义一个含有8个编号分别为 ( 000 , 001 , 010 , . . . , 111 ) (000,001,010,...,111) (000,001,010,...,111) 的顶点的图,对于顶点 x 1 x 2 x 3 x_1x_2x_3 x1x2x3 ,添加弧使其与 x 2 x 3 0 x_2x_30 x2x30 x 2 x 3 1 x_2x_31 x2x31 以出弧的形式相邻(每个顶点的入度=出度=2),构造出一个有向Euler图 D D D
Step2:取图 D D D 的一条有向Euler闭迹 P P P ,如 000 → 000 → 001 → . . . → 100 → 000 000\rightarrow000\rightarrow001\rightarrow...\rightarrow100\rightarrow000 000000001...100000
Step3:取 P P P 中每个顶点的最后一位 001...00 001...00 001...00 作为序列,即为所求结果。
推广:若编码盘上有 n n n 个顶点,则构造出的有向图为德布鲁英图 B ( 2 , n ) B(2,n) B(2,n) ,得到的序列为德布鲁英序列

5.2 中国邮递员问题(管梅谷教授提出)

1. 问题描述:从邮局出发,每个街道经过至少一次,最终回到邮局,如何走使得总路程最少?
2. 图论问题转换:在加权连通图 G G G 中,寻找一条经过每条边至少一次且权和最小的闭迹,即寻找 G G G最优环游
3. 算法:奇偶点图上作业法
Step1:若图是欧拉图,则欧拉闭迹是最优解;
Step2:若图不是欧拉图,在图中的每对奇点之间分别找一条链,链上的每条边添加一条重边;
Step3:若两顶点间有 k ( k ≥ 3 ) k(k\ge 3) k(k3) 重边,则删除其中的偶数条边。
Step4:检查图中的每一个圈,若圈上所有重边的权和大于所有单边的权和,则将所有重边去掉一条边变为单边,将单边添加一条边变为重边。
Step5:重复执行Step4,直到图中所有圈上的重边权和不超过圈权和的一半。
Step6:用Fleury算法求图的Euler闭迹,即为最优环游。
算法规模:因为需要遍历所有的圈,所以不可能在二项式时间内得解。

定理4 G G G 是加权连通图,则奇偶点图上作业法得到的闭途径是最优环游。

5.3 Hamilton图

Hamilton图:若图 G G G 中存在包含一切顶点的圈 C C C ,则称 G G G 为Hamilton图, C C C 称为Hamilton圈
半Hamilton图:若图 G G G 中存在包含一切顶点的链 P P P ,则称 G G G 为半Hamilton图, P P P 称为Hamilton链

定理1 Hamilton图的必要条件
(1)若 G G G 是Hamilton图,则 ω ( G − S ) ≤ ∣ S ∣ , ( ∀ S ⊂ V , S ≠ ∅ ) \omega(G-S)\le|S|,(\forall S\subset V,S\neq \varnothing) ω(GS)S,(SV,S=) 。(即从 G G G 中删除顶点子集 S S S 后,连通分支个数一定少于 S S S 中顶点个数)
(2)若 G G G 是半Hamilton图,则 ω ( G − S ) ≤ ∣ S ∣ + 1 , ( ∀ S ⊂ V , S ≠ ∅ ) \omega(G-S)\le|S|+1,(\forall S\subset V,S\neq \varnothing) ω(GS)S+1,(SV,S=)

推论1 对于二部图 G = ( X , Y , E ) G=(X,Y,E) G=(X,Y,E) ,若 G G G 是Hamilton图,则 ∣ X ∣ = ∣ Y ∣ |X|=|Y| X=Y ;若 G G G 是半Hamilton图,则 ∣ ∣ X ∣ − ∣ Y ∣ ∣ ≤ 1 ||X|-|Y||\le 1 ∣∣XY∣∣1

闭包:设 G G G 是简单图,反复连接 G G G 中度之和不小于 ν \nu ν 的不相邻顶点对,直到没有这种顶点对为止,这样得到的图称为 G G G 的闭包,记作 c ( G ) c(G) c(G)

引理1 G G G 是简单图, u u u v v v G G G 中不相邻, u ≠ v u\neq v u=v ,且 d ( u ) + d ( v ) ≥ v d(u)+d(v)\ge v d(u)+d(v)v ,则“ G G G 是Hamilton图”的充要条件是“ G + u v G+uv G+uv 是Hamilton图”。

定理2 一个简单图 G G G 是Hamilton图,当且仅当 c ( G ) c(G) c(G) 是Hamilton图。

推论2 G G G 是简单图,且 v ≥ 3 v\ge 3 v3 ,若 c ( G ) c(G) c(G) 是完全图,则 G G G 是Hamilton图。

推论3 G G G 是简单图, v ≥ 3 v\ge 3 v3 且对于 G G G 中任意一对不相邻相异顶点 u u u v v v ,有 d ( u ) + d ( v ) ≥ v d(u)+d(v)\ge v d(u)+d(v)v ,则 G G G 是Hamilton图。

推论4 G G G 是简单图,且 v ≥ 3 v\ge 3 v3 δ ≥ v − 1 2 \delta\ge \frac{v-1}{2} δ2v1 ,则 G G G 是Hamilton图。

推论5 G G G 是简单图,且对 G G G 中任何一对不相邻的相异顶点 u u u v v v ,有 d ( u ) + d ( v ) ≥ v − 1 2 d(u)+d(v)\ge\frac{v-1}{2} d(u)+d(v)2v1 ,则 G G G 是半Hamilton图。

推论6 G G G 是简单图,并且 δ ≥ v − 1 2 \delta\ge\frac{v-1}{2} δ2v1 ,则 G G G 是半Hamilton图。

定理3(范更华,1984)
G G G 连通简单图, ∀ v ∈ V ( G ) \forall v \in V(G) vV(G) G − v G-v Gv 仍连通,对 G G G 中满足 d ( u , v ) = 2 d(u,v)=2 d(u,v)=2 的任意顶点对 u u u v v v 都有 m a x { d ( u ) , d ( v ) } ≥ v 2 max\{d(u),d(v)\}\ge\frac{v}{2} max{d(u),d(v)}2v ,则 G G G 是Hamilton图。


(1)以上定理为Hamilton图的充分条件,推论为一些必要条件,尚不存在充分必要条件
(2)重边和环在研究Hamilton图中没有意义。

格雷码

《图论与网络优化》学习笔记(第1-5章),学习笔记,图论,网络,学习《图论与网络优化》学习笔记(第1-5章),学习笔记,图论,网络,学习《图论与网络优化》学习笔记(第1-5章),学习笔记,图论,网络,学习

  • 格雷码即为立方体的Hamilton圈(n立方体是Hamilton图)

5.4 有向Hamilton图

定理1 强连通的充要条件
G G G 是连通图,则 G G G 有强连通定向图,当且仅当 G G G 中没有割边。

定理2 强连通的等价刻划
D = ( V , A ) D=(V,A) D=(V,A) ν ≥ 2 \nu\ge2 ν2 的有向图,则下列命题等价:
(1) D D D 是强连通的;
(2) D D D 是连通的,且 D D D 的每条弧都在一个回路上;
(3) ∀ S ⊂ V \forall S\subset V SV S ≠ ∅ S\neq\varnothing S= ( S , S ˉ ) ≠ ∅ (S,\bar{S})\neq\varnothing (S,Sˉ)= ( S ˉ , S ) ≠ ∅ (\bar{S},S)\neq\varnothing (Sˉ,S)=

推论1 D D D 是简单有向图,且 d D + ( u ) + d D − ( v ) ≥ ν − 1 d_D^+(u)+d_D^-(v)\ge\nu-1 dD+(u)+dD(v)ν1 ∀ ( u , v ) ∉ A ( D ) \forall(u,v)\notin A(D) (u,v)/A(D) u ≠ v u\neq v u=v ,则 D D D 是强连通的。

有向Hamilton图:若有向图 D D D 中存在包含所有顶点的回路,则称 D D D 为有向Hamilton图,这种回路称为 D D D 的Hamilton回路
有向半Hamilton图:若有向图 D D D 中存在包含所有顶点的路,则称 D D D 为有向半Hamilton图,这样的路称为 D D D 的Hamilton路
竞赛图:任何两个顶点间都恰有一条弧相连的无环有向图,称为竞赛图,即竞赛图就是完全图的定向图。

定理3 任何 ν \nu ν 阶竞赛图 D D D 都是有向半Hamilton图。

定理4 对任何满足 3 ≤ k ≤ ν 3\le k\le \nu 3kν 的整数 k k k ν ≥ 3 \nu\ge3 ν3 的强连通竞赛图 D D D 的每个顶点都在 D D D 中某个 k k k 回路上。

推论2 v ≥ 3 v\ge3 v3 的竞赛图 D D D 是有向Hamilton图,当且仅当 D D D 是连通的。

定理5 有向Hamilton的充分条件
D D D ν ≥ 2 \nu\ge2 ν2 的强连通简单有向图,若对任一对不相邻的相异顶点 u u u v v v ,有 d ( u ) + d ( v ) ≥ 2 ν − 1 d(u)+d(v)\ge2\nu-1 d(u)+d(v)2ν1 ,则 D D D 是有向Hamilton图。

5.5 连通度和边连通度

刻画图的连通程度:
顶点割:若在图 G G G 中去掉顶点子集 V ˊ \acute{V} Vˊ 使得 G − V ˊ G-\acute{V} GVˊ 不连通,则称 V ˊ \acute{V} Vˊ G G G 的顶点割,若 ∣ V ˊ ∣ = k |\acute{V}|=k Vˊ=k ,则称 V ˊ \acute{V} Vˊ G G G k k k顶点割
连通度 G G G 的最小顶点割中的顶点数为 G G G 的连通度,记作 κ ( G ) \kappa(G) κ(G) 。规定完全图的连通度 κ ( G ) = ν − 1 \kappa(G)=\nu-1 κ(G)=ν1
k k k连通图:若图 G G G 的连通度 κ ( G ) ≥ k \kappa(G)\ge k κ(G)k ,则称 G G G k k k连通图。(要使图 G G G 不连通,至少需要去掉 k k k 个顶点)
边连通度 G G G 的最小边割中的边数为 G G G 的边连通度,记作 κ ˊ ( G ) \acute\kappa(G) κˊ(G) 。规定非平凡图或非连通图的边连通度 κ ˊ ( G ) = 0 \acute\kappa(G)=0 κˊ(G)=0
k k k边连通图:若图 G G G 的边连通度 κ ˊ ( G ) ≥ k \acute\kappa(G)\ge k κˊ(G)k ,则称 G G G k k k边连通图。(要使图 G G G 不连通,至少需要去掉 k k k 条边)

定理1 对于任何图 G G G 都有 κ ( G ) ≤ κ ˊ ( G ) ≤ δ ( G ) \kappa(G)\le\acute\kappa(G)\le\delta(G) κ(G)κˊ(G)δ(G) 。( 其中 δ ( G ) = m i n { d ( v ) ∣ d ( v ) ∈ V } \delta(G)=min\{d(v)|d(v)\in V\} δ(G)=min{d(v)d(v)V},为顶点的最小度)

定理2 对于任何满足 0 < l ≤ m ≤ n 0<l\le m\le n 0<lmn 的正整数 l , m , n l,m,n l,m,n 总存在一个简单图 G G G ,使得 κ ( G ) = l , κ ˊ ( G ) = m , δ ( G ) = n \kappa(G)=l,\acute\kappa(G)=m,\delta(G)=n κ(G)=l,κˊ(G)=m,δ(G)=n

定理3 一个 ν ≥ 3 \nu\ge3 ν3 的图 G G G 是2连通图,当且仅当 G G G 的任何两个顶点由至少两条内部不相交的链链接。

推论1 G G G 是2连通图,则 G G G 的任何两个顶点在一圈上。

推论2 G G G ν ≥ 3 \nu\ge3 ν3 的块(2连通图),则 G G G 的任何两条边在一个圈上。

引理1 G G G k k k连通图, k ≥ 2 k\ge2 k2 ,则对于 G G G 的任何连杆 e e e G ⋅ e G\cdot e Ge k − 1 k-1 k1 连通图。

引理2 κ ( G ) = k ≥ 1 \kappa(G)=k\ge1 κ(G)=k1 ,且 V ˊ = { v 1 , v 2 , . . . , v k } \acute{V}=\{v_1,v_2,...,v_k\} Vˊ={v1,v2,...,vk} G G G k k k 顶点割, G 1 , G 2 , . . . , G p G_1,G_2,...,G_p G1,G2,...,Gp G − V ˊ G-\acute{V} GVˊ 的全部连通分支,则对于 ∀ 1 ≤ i ≤ k \forall1\le i\le k ∀1ik ∀ 1 ≤ j ≤ p \forall1\le j\le p ∀1jp ,顶点 v i v_i vi 必与连通分支 G j G_j Gj 的某个顶点在 G G G 中相邻。

定理4 G G G 是3连通图, ν ≥ 5 \nu\ge5 ν5 ,则存在 G G G 的连杆 e e e ,使 G ⋅ e G\cdot e Ge 仍然是3连通图。

5.6 坚韧度

坚韧度:设 G G G ν \nu ν 阶图,且至少有一对相异顶点不相邻,则 G G G 的坚韧度 t ( G ) = m i n { ∣ S ∣ ω ( G − S ) ∣ S ⊂ V ( G ) , S ≠ ∅ , ω ( G − S ) ≥ 2 } t(G)=min\{\frac{|S|}{\omega(G-S)}|S\subset V(G),S\neq\varnothing,\omega(G-S)\ge2\} t(G)=min{ω(GS)SSV(G),S=,ω(GS)2} 。对于完全图,规定 t ( G ) = ν ( G ) − 1 2 t(G)=\frac{\nu(G)-1}{2} t(G)=2ν(G)1
t t t坚韧图:若图 G G G 的坚韧度 t ( G ) ≥ t t(G)\ge t t(G)t ,则称 G G G t t t坚韧图。
坚韧集:若存在 S ∗ ⊂ V ( G ) S^{*}\subset V(G) SV(G) ω ( G − S ∗ ) ≥ 2 \omega(G-S^*)\ge2 ω(GS)2 满足 t ( G ) = ∣ S ∗ ∣ ω ( G − S ∗ ) t(G)=\frac{|S^*|}{\omega(G-S^*)} t(G)=ω(GS)S ,则称 S ∗ S^* S G G G 的坚韧度顶点集,简称坚韧集。

定理1 ν ( ν ≥ 3 ) \nu(\nu\ge3) ν(ν3) 阶连通图 G G G ,则 1 ν ( G ) − 1 ≤ t ( G ) ≤ ν ( G ) − 1 2 \frac{1}{\nu(G)-1}\le t(G)\le\frac{\nu(G)-1}{2} ν(G)11t(G)2ν(G)1

定理2 T T T 是树, Δ \Delta Δ 表示 T T T 的最大度,则有 t ( T ) = 1 Δ t(T)=\frac{1}{\Delta} t(T)=Δ1

推论1 P P P ν ( ν ≥ 3 ) \nu(\nu\ge3) ν(ν3) 的链,则 t ( P ) = 1 2 t(P)=\frac{1}{2} t(P)=21

边坚韧度:设 G G G 是一个非平凡连通图,则图 G G G 的边坚韧度 t ˊ ( G ) = m i n { ∣ E ˊ ∣ ω ( G − E ˊ ) − 1 ∣ E ˊ ⊆ E ( G ) , ω ( G − E ˊ ) ≥ 2 } \acute{t}(G)=min\{\frac{|\acute{E}|}{\omega(G-\acute{E})-1}|\acute{E}\subseteq E(G),\omega(G-\acute{E})\ge2\} tˊ(G)=min{ω(GEˊ)1EˊEˊE(G),ω(GEˊ)2} 。对于平凡图或非连通图,规定 t ˊ ( G ) = 0 \acute{t}(G)=0 tˊ(G)=0

定理3 对于任何非平凡连通图 G G G ,有 κ ˊ ( G ) 2 < t ˊ ( G ) ≤ κ ˊ ( G ) \frac{\acute\kappa(G)}{2}<\acute{t}(G)\le\acute\kappa(G) 2κˊ(G)<tˊ(G)κˊ(G)文章来源地址https://www.toymoban.com/news/detail-816468.html

到了这里,关于《图论与网络优化》学习笔记(第1-5章)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图论与算法(1)图论概念

    在计算机科学中,图论与算法是两个重要且紧密相关的领域。图论研究图的性质和特征,而算法设计和分析解决问题的方法和步骤。图论提供了一种形式化的方法来描述和分析各种关系和连接,而算法则为解决图相关的问题提供了有效的解决方案。 图论是研究图的结构和性质

    2024年02月07日
    浏览(41)
  • 图论与算法(2)图的基本表示

    (1) 有向图和无向图: 有向图(Directed Graph):图中的边具有方向,表示节点之间的单向关系。 无向图(Undirected Graph):图中的边没有方向,表示节点之间的双向关系。 (2)加权图和无权图: 加权图(Weighted Graph):图中的边具有权重或距离,表示节点之间的关系有一定

    2024年02月04日
    浏览(45)
  • 图论与算法(7)最短路径问题

    最短路径问题是指在一个加权图中寻找两个顶点之间的最短路径,其中路径的长度由边的权重确定。 常见的最短路径算法包括: Dijkstra算法 :适用于解决单源最短路径问题,即从一个固定的起点到图中所有其他顶点的最短路径。该算法通过不断选择当前路径上权重最小的顶

    2024年02月06日
    浏览(41)
  • 图论与算法(3)图的深度优先遍历

    图的遍历 是指按照一定规则访问图中的所有顶点,以便获取图的信息或执行特定操作。常见的图遍历算法包括深度优先搜索(DFS)和广度优先搜索(BFS)。 深度优先搜索 (DFS):从起始顶点开始,递归或使用栈的方式访问相邻的顶点,直到所有顶点都被访问过为止。DFS通过

    2024年02月06日
    浏览(48)
  • 图论与算法(遍历、最小生成树、最短路径)

    图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E),其中:顶点集合V = {x|x属于某个数据对象集}是有穷非空集合;E = {(x,y)|x,y属于V}或者E = {x, y|x,y属于V Path(x, y)}是顶点间关系的有穷集合,也叫做边的集合。(x, y)表示x到y的一条双向通路,即(x, y)是无方向的;Path

    2024年04月14日
    浏览(45)
  • 图论与算法(5)图的广度优先遍历应用

    树的广度优先遍历(Breadth-First Traversal),也称为层次遍历,是一种按层次顺序逐级访问树节点的遍历方式。在广度优先遍历中,先访问树的根节点,然后按照从上到下、从左到右的顺序逐层访问树的节点。 首先将树的根节点入队列,然后循环执行以下操作:出队列一个节点

    2024年02月08日
    浏览(43)
  • 【图论】重庆大学图论与应用课程期末复习资料(私人复习资料)

    填空 顶点集和边集都有限的图,称为有限图 只有一个顶点的图,称为平凡图 边集为空的图,称为空图 顶点数为n的图,称为n阶图 连接两个相同顶点的边的条数称为边的重数;重数大于1的边,称为重边 端点重合为一点的边,称为环 既无环又无重边的图,称为简单图 每两个

    2024年02月05日
    浏览(38)
  • B3610 [图论与代数结构 801] 无向图的块 题解

    2023 2023 2023 ,再见。 2024 2024 2024 ,你好! 其实就是统计点双连通分量的个数。需要注意的是,孤立点在这里不被看作块。本文使用 tarjan 算法来解决这道题。 概念明晰 时间戳:这里记为 d f n i dfn_i df n i ​ ,表示第一次深度优先搜索到节点 i i i 的时间。时间 t i m e ∈ N + t

    2024年02月03日
    浏览(41)
  • 利用GAT(图论分析工具箱)构建并分析大脑结构协变网络学习笔记

    前面我学习了利用DTI构建白质纤维脑网络,并采用GRETNA计算了小世界网络属性。阅读文献发现可以利用灰质体积或皮层指标(皮层厚度、折叠指数、沟深)等构建结构协变网络再进行网络拓扑属性的计算。因此,我采用前面提取的灰质体积和皮质数据进行了结构协变网络分析

    2024年04月16日
    浏览(92)
  • C#,图论与图算法,图(Graph)广度优先遍历(BFS,Breadth First Search)算法与源代码

    深度优先算法(DFS,Deep First Search)与 宽度优先遍历(BFS,Breadth First Search) 是树、图数据结构的基础性、标准性的遍历算法。 深度优先搜索(DFS)是一种用于搜索图形或树数据结构的算法。该算法从树的根(顶部)节点开始,尽可能沿着给定的分支(路径)向下,然后回溯

    2024年03月23日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包