20210511

回顾 | 线性代数-线性方程组(一)| 数据结构-图(三)| 恋词U15

Table of Contents

回顾

恋词复习

离散数学-判断某非负整数列是否能简单图化

首先用必要条件去试试

  1. 奇数度结点度数之和是否为偶数
  2. 无向图顶点度数之和是否为边数的2倍

然后就是用Havel定理(这个真好用!)且这个是充要条件。大概步骤是这样的

  1. 对已知的度数列进行降序排列(相等的放在一起)。
  2. 假设最大的度为k(已经排在首位),删去最大的度数k,对后面的k个度数都进行减1,再进行降序排列,由此得到一个新度数列。
  3. 重复第2步的操作。
  4. 若在此期间出现了负数,则不是简单图;若最后剩下的度数列的度数均为0.则为简单图。

举几个例子就懂了!

这个数列其实不用Havel定理就可以看出来不行了,因为第一个有5个度,可是除了他自己只剩下4个结点,很明显出现了环或者重边,就不是简单图了。

这个数列也是,加起来度数之和是奇数,不是偶数,连必要条件都不满足

这个就可以用havel定理了,因为必要条件啥的都满足。

3,3,3,1;
//删掉最大的度3,对后面3个度数都减1
2,2,0;
//删掉最大的度2.对后面2个度数都减1
1,-1; //出现了负数,不是简单图
4,4,3,3,2,2;
//删掉最大的度4,对后面4个度数都减1
3,2,2,1,2;
//此时不是降序排列,则重新排列
3,2,2,2,1;
//删掉最大的度3,对后面3个度数都减1
1,1,1,1//
//删掉最大的度1,对后面1个度数都减1
0,1,1;
//此时不是降序排列,则重新排列
1,1,0;
//删掉最大的度1,对后面1个度数都减1
0,0;
//最后剩下的度数列的度数均为0.则为简单图。

线性代数-线性方程组(一)

不知不觉来到了第四章,这一章是考试的重点,mark一下。

--

数据结构-最小(代价)生成树-最短路径-图(三)

普里姆算法(Prim)

选出A,把A0并入生成树中
→ 找出与之相邻鹅所有边即长度为1,2,3的边,显然为长度为1的边,将A与长度为1的边并入生成树中
→ 找出A0,A1相邻的所有边:8,7,2,3,选2,将A2与2并入
→ 找出A0,A1,A2相邻的所有边:8,4,3,6,7,7舍掉,因为选7会形成环就不是树了。选3,将A3与3并入
→ 找出A0,A1,A2,A3相邻的所有边:8,4,5,选4,将A4与4并入
→ 找出A0,A1,A2,A3,A4相邻的所有边,5,9,选5,将A5与5并入

克鲁斯卡尔算法(Kruskal)

哪条边最短?
→ 权值为1的那条,并入
→ 权值为2的那条,并入
→ 权值为3的那条,并入
→ 权值为4的那条,并入
→ 权值为5的那条,不能并入,会形成环
→ 权值为6的那条,并入

每次选未被并入且不会产生环的最短的边进行并入。 那么如何检查会不会产生环? → 并查集 → 查找是否为同一个根结点。


迪杰斯特拉算法(Dijkstra)

弗洛伊德算法(Floyd)


恋词U15