搜索文章

文章标题:

解的存在和唯一性

Gronwall不等式
设\(f(x),g(x)\in C[a,b], g(x)\ge 0\),\(c\)为常数,满足\[f(x)\le c+\int_a^x g(s)f(s)ds,\]则\[f(x)\le c\cdot \exp\{\int_a^x g(s)ds\}.\]

证明:令\(\Phi(x) = \int_a^x g(s)f(s)ds\),则\[\Phi'(x) = g(x)f(x) \le g(x)\cdot (c+\Phi(x)),\]
利用初等积分法可知\[\exp\{-\int_a^x g(s)ds\}\Phi(x) \le \int_a^x c\cdot g(s) \exp\{-\int_a^s g(t)dt\}ds.\]整理即得。

一致有界与等度连续, Ascoli-Arzela引理
设\(A\)为函数族\(\{f_\alpha\}\)的指标集且为无限集,\(I\subseteq R\), 如果存在\(M>0\),使得\[|f_\alpha (x) |\le M, \forall \alpha\in A, \forall x\in I\]则称\(\{f_\alpha\}_{\alpha_\in A}\)在I上一致有界。

如果\(\forall \epsilon>0, \exists \delta > 0, s.t.\forall x,y\in I, |x-y|<\delta, \)满足\[|f_\alpha(x) - f_\alpha(y)|<\epsilon ,\forall \alpha\in A\]称\(\{f_\alpha\}_{\alpha_\in A}\)在I上等度连续。

Ascoli-Arzela引理:
设A为可数集,如果\(\{f_\alpha\}_{\alpha\in A}\)在\([a,b]\)上一致有界且等度连续,则存在\([a,b]\)上一致收敛的子序列。

Picard定理
称函数\(f(x,y)\)在区域G上对y满足Lipschitz条件,如果存在常数L,使得对于任意的\((x,y_1),(x,y_2)\in G\),有\[|f(x,y_1)-f(x,y_2)|\le L|y_1-y_2|\]
Picard定理:假设\(f(x,y)\)在闭区域D上连续,对\(y\)满足Lipschitz脚尖,则微分方程\[\frac{dy}{dx}=f(x,y),\quad y(x_0)=y_0\]的解在\(|x-x_0|\le h\)上存在且唯一,其中\[h=\min(a,\frac b M), M = \max_{(x,y)} |f(x,y)|.\]
证明:构造Cauchy序列:\[y_0(x) = y_0,\quad y_n(x) = y_0 + \int_{x_0}^x f(s, y_{n-1}(s))ds\]并证明其一致收敛到方程的解。

Peano定理
假设\(f(x,y)\in C(D),D=\{|x-x_0|\le a, |y-y_0|\le b\}\),则上述微分方程在区间\(|x-x_0|\le h\)上至少有一个解,其中\(h=\min(a,\frac b M), M = \max_{(x,y)} |f(x,y)|.\)

解的延伸
延伸定理:
考虑Cauchy问题\[y'=f(x,y), y(x_0)=y_0\]其中\(f(x)\in C(G)\),其任意解曲线\(\Gamma\)均可延伸至G的边界。

比较定理
第一比较定理:设\( f(x,y), F(x,y)\in C(G), f(x,y) < F(x,y), \forall x,y\in G\). 又设\(y=\phi(x), y\in \Phi(x)\)在区间\((a,b)\)上分别是\(y'=\{f,F\}, y(x_0)=y_0\)的解,则\[\begin{cases} \phi(x) < \Phi(x), & x\in (x_0, b)\\ \phi(x) > \Phi(x), & x\in (a, x_0)\end{cases}\]
一个应用:考虑\(y'=f(x,y), D=(a,b)\times \mathbb R\), 满足\[|f(x,y)|\le A(x)|y|+B(x), A,B\ge 0, \in C(a,b)\]则方程的每个解存在区间均为\( (a,b)\).

最大解和最小解
如果初值问题\(y'=f(x,y), y(x_0)=y_0\)在区间\(|x-x_0|\le a\)上有2个解\(\Phi(x), \psi(x)\),使得对于该初值问题的任意解\(y(x)\),有\(\Psi(x)\le y(x)\le \Phi(x), |x-x_0|\le a,\) 则分别称\(\Psi(x), \Phi(x)\)为该问题在\(|x-x_0|\le a\)上的最小解和最大解。

最大解和最小解的存在性:
存在正数\(\tau\),使得\(|x-x_0|\le \tau\)上最大解和最小解存在。

    所属分类:常微分方程     发表于2023-03-28

初等积分法

初等积分法解常微分方程
待更新

    所属分类:常微分方程     发表于2023-03-28

Pandas 数据分析基础

import pandas as pd
pandas序列(Series)
data = pd.Series([0.1, 0.2, 0.3, 1.0]) #自动维护标号索引,支持下标切片
data = pd.Series([1,2,3,4], index=['a', 'b', 'c', 'd']) #指定索引
data.iloc[1] #按位置索引
#迭代器
for i in data.values:
print(i)
# 使用词典初始化序列
sdata = {'a':1, 'b':2, 'c':3}
keys = ['b', 'c', 'd']
obj = pd.Series(sdata, index = keys) # 'd'为Nan, 'a'被删去


pandas二维数据表(DataFrame)

多序列合并生成dataframe

dict1 = {'a':1, 'b': 2, 'c':3}
sdata_1 = pd.Series(dict1)
dict2 = {'a':2020, 'b':2021, 'c':2022}
sdata_2 = pd.Series(dict2)
df = pd.DataFrame({'c1': sdata_1, 'c2': sdata_2})
# 非对齐情况:用NaN填充


用二维Numpy数组生成:

pd.DataFrame(np.random.rand(3,2),
columns=['foo', 'bar'], index=['a', 'b', 'c'])

其他可以输入给DataFrame构造器的数据:
二维ndarray, 由数组、列表或元组组成的字典(每个序列变成DataFrame的一列, 长度必须相同),由Series组成的字典等

索引

state.index # 行索引 Index ['a', 'b', 'c']
state.columns # 列索引 Index ['c1', 'c2']


Pandas Index Object 与 表间关联计算
集合运算

indA = pd.Index([1,2,3,4,5])
indB = pd.Index([2,4,6,8])
indA & ind B
# Ind64Index([2,4])
ind A | ind B
# Ind64Index([1,2,3,4,5,6,8])
indA ^ indB
# Ind64Index([1,3,5,8])


索引

df = pd.DataFrame({'c1': sdata_1, 'c2': sdata_2})
df['c1'] #按列索引
df.c1 #也可使用字段名作为属性
df['c3'] = df['c1'] + df['c2'] # 创造新列并赋值
# 筛选
df.loc[ df.c1 > 0, ['c1', 'c2']]
# 赋值
df.iloc[0,1] = 3

    所属分类:Python     发表于2023-03-17

Linux批量操作文件

以删除文件为例:
find myFile -type f -name "*.txt" -exec rm -f {} \;
其中
myFile是要操作的文件夹,如果是当前文件夹可以用"."代替;
type f为普通文件,如果操作文件夹可换成d;
name是指要匹配的文件名,如"*.txt"为所有以.txt为后缀的文件;
{}代表要执行的文件,此处rm -f {}指直接删除所有匹配的文件。

    所属分类:Linux     发表于2022-09-09

网络流

网络与容许流
定义:一个网络\(N(V,E,C)\)是一个赋权有向简单弱连通图,满足:
1. V中恰有一个负度为0的结点s,称为发点(源);
2. V中恰有一个正度为0的结点他,称为收点(汇);
3.每条边\(v_i,v_j)\)的边权\(c_{i,j}\)是一个非负实数,称为该边的容量,\(C=(c_{i,j}\)为网络的容量函数。

定义:如果在网络\(N(V,E,C)\)的边集E上定义一个非负实值函数\(f=(f_{i,j})\),满足一下条件:
1. 容量限制条件,\(f_{i,j}\le c_{i,j}\);其中等号成立的边称为饱和边。
2. 平衡条件,对每个中间点v,有\(\sum\limits_{u\in N(v)} f_{u,v} = \sum\limits_{u\in N(v)} f_{v,u}.\)

设F为网络\(N(V,E,C)\)所有容许流组成的集合,称\(f_0=\arg\max w(f)\)为网络\(N(V,E,C)\)的最大流。

割切
定义:设S是网络N的结点子集,如果满足\(s\in S, t\in \bar S\),则\(S\times \bar S\)的所有有向边组成的集合称为N的一个割切,记为\((S,\bar S)\)。其中所有边的容量之和\[C(S,\bar S)=\sum\limits_{(u,v)\in (S,\bar S)} c_{u,v}\]称为割切\((S,\bar S)\)的容量。最小容量的割切称为最小割切。

引理1. 设f是网络N的任一容许流,\((S,\bar S)\)是N的任一割切,则有\[w(f) = \sum\limits_{u\in S,v\in\bar S} f_{u,v} - \sum\limits_{u\in \bar S,v\in S} f_{u,v}\]
定理2. 设f是网络N的任一容许流,\((S,\bar S)\)是N的任一割切,则有\[w(f)\le C(S,\bar S)\]

定理3. 若f是N最大流,则f的流量等于N的最小割切的容量。

    所属分类:离散数学     发表于2022-08-25

图的匹配

图的匹配问题
定义:设M是G的边子集,G是无向简单连通图(下同),M中任意两边不相邻,则称M是G的一个匹配。与M中边关联的点称为M的饱和点,其余为非饱和点。

定义:设M是G的一个匹配。如果对G的任一个匹配\(M'\)都有\(|M|\ge|M'|\),称M是G的最大匹配。特别的,若G的结点都是饱和点,称M为完美匹配。

定义:给定G的一个匹配M,G中属于M和不属于M的边交替出现的道路称为关于M的交错道路。如果交错道路P的起点和终点都是关于M的非饱和点,称P为可增广道路。

定理1. M是G的最大匹配当且仅当G中不存在关于M的可增广道路。
证明:必要性,若P是M的可增广道路,则\(P\oplus M\)边数比M多1;充分性,取G的最大匹配\(M'\),令\(G'=M\oplus M'\),则\(\Delta(G')\le 2\)(因为任一个匹配中的点至多与一边关联),\(G'\)的连通分支只有2种:要么是由M和\(M'\)的边交错形成的偶回路,要么是\(M'\)与\(M\)的边交错形成的道路P。P一定有偶数条边,否则P是M或M'的可增广道路。综上可知\(|M|=|M'|\)。

利用定理1可以给出求解最大匹配的算法:反复寻找可增广道路。

二部图的匹配
定义:设M是二部图\(G=(X,Y,E)\)的匹配,若\(|M|=|X|\),则称M是G的从X到Y的完全匹配。
引理2. 设M是G的一个匹配,\(x_0\)不是X中的饱和点。令U表示X中所有可通过以\(x_0\)为起点的交错道路到达的结点(含\(x_0\)),V表示Y中所有可通过以\(x_0\)为起点的交错道路到达的点,则有:
1. 存在以\(x_0\)为起点的可增广道路\(\Leftrightarrow\)V中存在M的非饱和点;
2. 不存在以\(x_0\)为起点的M的可增广道路\(\Leftrightarrow\)\(N(U)=|U|-1\)。
证明:结论1是显然的。对于结论2,首先说明U中除了\(x_0\)都是M的饱和点,V中的点也都是M的饱和点。必要性:由于每个V中的饱和点唯一对应一个U中除\(x_0\)外根据M的匹配唯一对应于V的点,所以\(|V|=|U|-1\)且\(N(U)=V\)。充分性:如果\(|N(U)| = |U|-1\),若存在以\(x_0\)为起点的可增广道路,取\(M'=M\oplus P\),则U和V的点都是\(M'\)的饱和点,\(|U|=|V|\),矛盾。

定理3. 在二部图\(G=(X,Y,E)\)中,存在X到Y的完美匹配的充要条件是对X的任意子集\(A\subseteq X\),恒有\(|N(A)|\ge |A|\)。
证明:必要性,设M是X到Y的完全匹配,因为A中的点一一匹配到\(N(A)\)中的点,所以\(|A|=|N(A)|\)。充分性,任取G的一个最大匹配M,若M不是完全匹配,则存在非饱和点\(x_0\in X\),不存在以\(x_0\)为起点的M可增广道路,由引理存在\(U\subseteq X\)使得\(N(U)=|U|-1\),矛盾。

推论4. 设k是正整数,若在二部图\(G=(X,Y,E)\)中,对任意\(x\in X, y\in Y\)都有\(d(x)\ge k, d(y)\le k\),则存在从X到Y的完美匹配。

定理5. 令\(\epsilon(A) =\max\{|A|-|N(A)|, 0\},\epsilon(G) = \max\limits_{A\subseteq X} \epsilon(A)\),则\(G=(X,Y,E)\)的最大匹配边数是\(|X|-\epsilon(G)\)。
证明:容易证明G的最大匹配边数不超过\(|X|-\epsilon(G)\)。下面给出构造,断言:若\(\epsilon(A)=\epsilon(G)\),则导出子图\(G'=(X-A, Y-N(A), E')\)满足\(\epsilon(G')=0\)。否则存在\(X-A\)的子结点集B,使得\(|B| > |N(B)\cap (Y-N(A))|\),此时计算得\(\epsilon(A\cup B) > \epsilon(G).\)下面对\(\epsilon(G)\)进行归纳。

    所属分类:离散数学     发表于2022-08-25

图的连通度

割点、割边和块
定义:设v是G的结点,如果\(G-v\)的连通分支比G多,则称v是G的一个割点。类似定义割边。
如果G有割边,则G一定有割点。

定义:图G的极大的无割点连通子图称为G的块。
如果G没有割点,则G本身是一个块。

定理1. 设v是G的结点。则以下论断等价:
1. v是G的割点;
2. 存在两个不同于v的结点u,w使得任意一条u到w的道路P都经过v;
3. \(V-v\)可以划分为两个结点子集\(U,W\),使得任意\(u\in U, w\in W\),v都在u到w的任意一条道路上。

定理2. 设e是G的一边。则以下论断等价:
1. e是G的割边;
2. e不属于G的任何回路;
3. 存在两结点u,v,使得e属于任何u到v的道路;
4. \(G-e\)的结点集可以划分为两个结点子集\(U,W\),使得任意\(u\in U, w\in W\),e都在u到w的任意一条道路上。

定理3. 设G是n阶无向连通图,则G是块当且仅当G的任意两结点在同一回路上。
证明:充分性显然。必要性对\(d(u,v)\)归纳。注意利用块的性质:删去任一结点后仍连通。

定理4. 设G是阶不小于3的连通图,则以下论断等价:
1. G是块;
2. G的任何两结点同属于某回路;
3. G的任一结点和任一边同属于某回路;
4. G的任意两边同属于某回路;
5. 给定任意两结点u,v和一边e,存在一条从u到v的道路包含e;
6. 对任意三个结点u,v,w,存在从u到w的道路经过v;
7. 对任意三个结点u,v,w,存在从u到w的道路不经过v。
证明:既得1,2,3,4等价,\(3\Rightarrow5\Rightarrow6\Rightarrow7\Rightarrow1\)显然。

可以在G的边集上定义一个等价关系:\(e_1\sim e_2\)当且仅当\(e_1,e_2\)在同一回路上或\(e_1=e_2\)。\(\sim\)的等价类即G的块。

连通度
定义:若连通图G删去结点子集\(A\subseteq V\)后不连通,称A为G的一个点断集。
称\(\mu(G)=\min |A|\)为G的连通度。
定义:对于连通图G的断集B,称\(\lambda(G)=\min |B|\)为G的边连通度。

定理5. 连通图G中有\[\mu(G)\le\lambda(G)\le\delta(G)\]
定义. 设G是连通图,若\(\mu(G)\ge k,\)则称G是k连通图;若\(\lambda(G)\ge k\),则称G是k边连通图。

定理6. 简单连通图G中,有\(\mu(G)\le [\frac{2m}{n}]\)。
证明:由握手定理显然。
用\(f(k,n)\)表示n阶k连通图的最少边数,则定理6说明\(f(k,n)\ge \lceil \frac {kn}{2}\rceil\)。

定理7. 设G是n阶简单图,k是正整数,结点度满足:\(d(v_1)\le d(v_2)\le \cdots\le d(v_n)\),且当\(1\le r\le n-1-d(v_{n-k+1})\)时有\(d(v_r)\ge r+k-1\),则G是k连通图。

定理8. 设G是n阶简单图,若\(\delta(G)\ge \lfloor \frac n 2\rfloor\),则\(\lambda(G)=\delta(G)\)。
证明:先证G是连通图。再取\(\lambda(G)\)边的断集,分别估计两个连通分支的边数。

定理9. 设G是n阶连通图,\(k\le n-1\)。则以下结论成立:
1. G是k连通的,当且仅当G中任意两点之间至少有k条内部不交的道路。
2. G是k边连通的,当且仅当G中任意两结点之间至少存在k条边不重复的道路。

    所属分类:离散数学     发表于2022-08-25

图的着色

图的着色
图的着色问题包括点着色,边着色,平面图的域着色。这三类问题都可以通过对偶关系转化为图的点着色问题。

定义:给定图G,满足相邻结点着不同颜色,所需的最少颜色数称为G的色数,记作\(\gamma(G)\)。
一些典型图的色数:\(\gamma(K_n)=n, \gamma(K_n-e)=n-1\),非空二部图色数为2,奇回路色数为3,
\(\gamma(G\times H) = \max(\gamma(G),\gamma(H)).\)

定理1. 设\(u,v\)在简单图G中不相邻。记\(\bar G=G+(u,v), H=G\circ \{u,v\}\), 则\(\gamma(G)=\min\{\gamma(\bar G), \gamma (H)\}\).
证明:对于G的着色方案,若\(u,v\)颜色不同则可以相连,若颜色相同则\(u,v\)可收缩为一点。重复操作得到某完全图,其阶数即G的色数。

最优着色问题是NP-难的。可以采用贪心着色算法得到近似解。
贪心着色算法:首先随机选择一个结点着色。然后依次选择未着色的点,选择一个不会造成颜色冲突的颜色。利用贪心着色算法可得:
定理2. 任意简单图G有\(\gamma(G)\le \Delta(G)+1.\)
一个更强的版本是:
定理3. 任意简单连通图G有\(\gamma(G)\le\Delta(G)\),除非G是完全图或者奇回路。
证明:当\(k=\Delta(G)\le 2\)时,结论成立。下设\(k\ge 3\)。基于贪心着色算法,我们的目标是将n个结点排序,使得每个结点至多有\(k-1\)个序号比它小的结点与它相邻。
当G不是k正则图时,取定一个度小于k的结点,作为\(v_n\)。因为G是连通图,从\(v_n\)出发,利用宽度优先检索算法,得到G的一颗生成树。 依照被检索顺序的倒序,得到结点序列\(v_1,v_2,\cdots, v_n\)。因此,对于\(v_1,\cdots,v_{n-1}\)中任意一点,总有一个邻点序号比它大(因为存在一条到\(v_n\)的道路),故序号比自己小的邻点至多\(k-1\)个。
当G是k-正则图时,首先若G存在割点x,则对G删去x后的每个连通分支\(V_i\),\(V_i\cup\{x\}\)都有k着色方案,令在这几个图中x的着色相同即可。
若G无割点,只需说明存在某个结点\(v_n\), 使得\(v_n\)有两个邻点\(v_1,v_2\)满足\(v_1,v_2\)不相邻,且G删去\(v_1,v_2\)仍连通,此时我们同样可以从\(v_n\)出发得到\(G-\{v_1,v_2\}\)的排序。
情况一:删去G的任何两个不同结点后都连通,因为G不是完全图,必有两结点\(u,v\)不相邻且\(d(u,v)\ge 2\)。取\(v_1=v\),在\(u,v\)道路上与v最近的两点分别为\(v_n,v_2\)。
情况二:存在G的两结点\(x,y\)使得\(G-\{x,y\}\)不连通。则\(G-\{x\}\)仍连通,但有割点。因为x与G-x的每个叶子块有邻点,取\(v_1,v_2\)某两个叶子块上的x邻点。因为\(k\ge 3\),所以x还有其他邻点,故\(G-\{v_1,v_2\}\)仍连通。取\(v_n=x\)即可。

色数多项式
设\(f(t,G)\)是用t种颜色对G着色的不同方案数,则\(f(t,G)\)是关于t的多项式。
定理4. 设\(u,v\)在G中不相邻。记\(G_{u,v} = G+(u,v), H_{u,v}=G\circ \{u,v\}\),则\(f(t,G)=f(t,G_{u,v})+f(t, H_{u,v})\)。
推论5. 设e是简单图G的一条边,则\(f(t,G) = f(t,G-e)-f(t, G\circ e)\)。

    所属分类:离散数学     发表于2022-08-24

平面图

平面图
定义:如果能把图G画在一个平面上,使得任何两边不相交,称G是可平面图。可平面图在平面上的一个嵌入(画法)称为平面图。

定义:设G是平面图。由它的若干条边所围成的区域内如果不含任何其它边,则称该区域为G的一个面或域。包围这个域的边称为其边界。
平面图G外边的无限区域称为无限域,其他的域叫内部域。每个域的边界是一条闭路径(不一定是道路),其长度称为域的边界长度。

割边只是一个域的边界(无限域),非割边一定是两个域的公共边界。平面图的每条边对边界长度的贡献都是2,因此域的边界长度之和等于\(2|E|\)。

定理1(欧拉公式). 设G是平面连通图,则G的域个数是\(d=m-n+2\)。
证明:取G的一颗生成树T,逐一加入T的弦。
推论2(欧拉不等式). 对任意平面图(不一定连通),有\(n-m+d\ge 2.\)

推论3. 若G是阶不小于3的简单平面图,则\(m\le 3n-6\)。
证明:如果G不含回路,由连通性知\(m\le n-1\le 3n-6\)。否则,G的每个域边界数不小于3,因此\(3d\le 2m\),带入欧拉不等式即得。
类似可以证明如果G的每个域边数不小于4,则\(m\le 2n-4\)。

定理4. \(K_5,\ K_{3,3}\)都是不可平面图。
证明:\(K_5\)边数为10,由推论3即得。\(K_{3,3}\)每个域的边界数不小于4,与\(m\le 2n-4\)推出矛盾。
\(K_5,\ K_{3,3}\)分别记作\(K^{(1)}, K^{(2)}\)图。本质上只有这两种非平面图。我们先介绍图同胚概念。

定义: 如果对图G进行如下若干操作:
1. 在图G某边中插入一个结点,使该边变成2条边;
2. 将G某个度为2的结点关联的两条边合并成一条。
得到的图\(G'\)称为与G同胚。图G可平面当且仅当G的任意同胚图可平面。
与\(K^{(1)},K^{(2)}\)所有同胚图分别称为\(K^{(1)},K^{(2)}\)型图,统称K型图。

定理5. 图G可平面的充要条件是G没有K型子图。

平面图的对偶图
定义:设G是平面图,如下定义的图\(G^*\)称为G的对偶图。
1. G的每个域\(f\)内设置一结点\(v^*\)作为\(G^*\)的结点;
2. 对G的非割边\(e\),必为两域\(f_i, f_j\)的公共边界,取\(e^*\)连接\(v_i^*,v_j^*\);
3. 对G的割边,必是某域\(f\)的边界,画\(G^*\)的一条自环\(e^*=(v^*,v^*)\)。

性质1. 平面图G的对偶图\(G^*\)唯一,且满足\(m^*=m,n^*=d, d^*=n\)。
性质2. \(G^*\)是连通图。
性质3. \((G^*)^*\)同构于G。
性质4. G的回路对应\(G^*\)的割集,G的割集对应\(G^*\)的回路。

    所属分类:离散数学     发表于2022-08-24

有向树与最优树

有向树
定义:设T是有向树,如果它有一个结点的入度为0,其余结点的入度均为1,则称T为根树。入度为0的结点称为树根,出度非0的结点称为分支点,出度为0的点称为树叶。
从根结点到结点v的有向路长度称为v的层数。最大层数称为树的高度。

定义:如果T的分支点都至多有m个儿子,称T为m元树。若每个分支点都恰有m个儿子,称为正则m元树。若正则m元树的所有树叶都在同一层,称为完全m元树。

定理1. 正则二元树的分支点数i与树叶数t满足\(i=t-1\)。
定理2. 设T是一颗正则二元树,I表示各分支点的层数之和,E表示各树叶的层数之和,则\(E=I+2i\)。

最优树
定义:设二元树T有t片树叶\(v_1,\cdots, v_t\),分别带权\(w_1,\cdots, w_t\in \mathbb R^+\),则称T为赋权二元树,称\(w(T)=\sum\limits_{i=1}^t w_i\cdot l(v_i)\)为二元树T的权,其中\(l(v)\)是树叶v的层数。

定义:在所有含t片树叶,且叶子权重分别为\(w_1,\cdots,w_t\)的二元树中,权最小的二元树称为最优二元树。

给定正实数\(w_1,\cdots,w_t\),构造一颗带权\(w_1,\cdots, w_t\)的最优二元树的哈夫曼算法可描述如下:
初始化\(S=\{w_1,\cdots,w_t\}, V=\{v_1,\cdots, v_t\}, E=\emptyset, w(v_i)=w_i\);
从S中取出权最小的\(w_a,w_b\),令\(w'=w_a+w_b\);
更新S:删去\(w_a,w_b\)并加入\(w'\), V中加入权为\(w'\)的结点\(v'\),E中加入\(v'\)与\(v_a,v_b\)的连边;
当S只有一个元素时结束。

编码
定义:设\(A=\{\beta_1,\cdots, \beta_m\}\)是一个字符串集合,若对\(A\)中任意两个不同的码字\(\beta_i,\beta_j\),都互相不是对方前缀,则称A为前缀码。

一个二元前缀码唯一对应一颗有序二元树。
给定字符集\(\{A_1,\cdots, A_t\}\),及表示这些字符的二元前缀码\(\{\beta_1,\cdots, \beta_t\}\),如果\(A_i\)出现的频率为\(w_i\),码字\(\beta_i\)的长度为\(l_i\),则用此二元前缀信息码表示信息花费的比特量是\(\sum\limits _{i=1}^t l_iw_i.\)

    所属分类:离散数学     发表于2022-08-23