锐客网

  1. 首页 > it技术 > >

图论 北师大 张秀平 自学 视频 NOIP

姐妹篇：组合数学 北师大 张秀平 自学 视频 NOIP 请看https://blog.csdn.net/mrcrack/article/details/80562324
图论 北师大 张秀平 自学 视频 NOIP
共60讲。2018-8-16 13:53
体会，虽然在书中，图论篇幅不大，但视频同样有60讲，原因是图论中算法特别多，学习的过程中，若无程序编出，感觉图论等同于没学，虽然编出的程序算法，未必与书中一致，但能解决问题就是硬道理，更何况，数学中的算法，有时计算机编起来比较困难，那还是编一个能解决问题的算法。2018-8-22 08:07
视频中的教学用书：2018-8-16 13:50
图论 北师大 张秀平 自学 视频 NOIP
文章图片

http://i.youku.com/i/UMTM5NzYwNDEy/videos?spm=a2hzp.8253869.0.0&order=1&page=1&last_item=&last_pn=2&last_vid=39648346有全部视频。2018-6-4

第1讲内容：第11章 图论导引 2018-6-4
开始-12:10 哥尼斯堡七桥问题（讲得透彻），远超书本介绍。核心，一进一出，具体到某点，必须偶数条边。2018-8-16 20:13
13:00-21:56 图能解决什么样的问题。提到无向图，有向图。生活实例表示成图。讲 猫 老鼠 粮食，竟然出现了并查集，虽然没有明说。2018-8-16 20:27
22:10-33:33 图的基本性质。点vertex、边edge、图graph。有重边的图 叫 多重图。 无重边的图 叫 简单图。点点 邻接，点边 关联。2018-8-1620:43
33:48-35:36 例子 GraphBuster(小鬼图)。2018-8-16 20:46
35:40-39:53 完全图Kn 任意两点间有边。边数结算，C(n,2)。2018-8-16 20:56
39:57-结束 平面图，内部边不交。可平面图。不可平面图。2018-8-16 21:02
http://v.youku.com/v_show/id_XMTU1NTAzMTcy.html?spm=a2hzp.8253869.0.0
第2讲内容：第11章 图论导引
开始-03:48 度deg(v) degree 与点关联的边数。图的度序列。完全图的度序列。2018-8-16 21:13
03:49-06:29 小鬼图上各点对应的度，点上出现 环 度按 2 来算。2018-8-16 21:18
06:31-11:44 定理11.1.1。一般图，允许有重边，允许有环。度的和=2e，想了半天就是这个，无奈就是写不出。2018-8-16 21:28
11:48-14:29 同构 概念。2018-8-16 21:40
14:30-16:30 书本 图11-5 同构证明。2018-8-16 21:39
16:31-18:58 例子 该例书中无，要同构，需找好映射。2018-8-17 07:35
19:00-21:14 例子16:31-18:58 继续增添条件，同构 不仅点的个数要相同，边数也要相同，说得好。2018-8-17 07:40
21:29-26:41 点数，边数一样多，是否同构。这个容易想，未必同构。视频中，采用度序列不同，来说明不同构。2018-8-17 07:50
26:50-29:15点数相同，边数相同，度序列相同，是否同构。这个也容易想，未必同构。书本 图11-7 为例 进行讲解。2018-8-17 08:00
29:16-30:39 同构 必须什么一致，简单说了说。类似 全等，但又不全是。2018-8-17 08:02
30:42- 途径 概念介绍。边不重 的途径 叫 迹。点不重 的途径 叫链。这两个概念第一次接触。开 X0!=Xm，闭X0=Xm。闭链是圈。举了例子。链是迹是途径。2018-8-17 08:43
https://v.youku.com/v_show/id_XMTU1NTAzMTg4.html?spm=a2h0j.11185381.listitem_page1.5!2~A&&f=4236391
第3讲内容：第11章 图论导引
开始-07:54 小鬼图 复习 途径 迹 链 概念。2018-8-17 16:49
07:57-15:58 两点之间有途径，一定有迹，一定有链。点x与y之间有链，称x与y连通。最短链的长度叫x与y的距离。G中的任何两点都连通，称G是连通的。2018-8-17 17:04
16:15-17:46 不连通的图，举例。2018-8-17 17:04
17:54-24:23 导出子图 邻接是核心。生成子图 核心 点全选，原有的边随便选。导出生成子图 就是 原图。2018-8-17 17:14
24:31-27:13 图11-10 导出子图，生成子图，讨论。2018-8-17 17:24
27:27-33:44 定理11.1.3。连通分量。2018-8-17 17:32
33:47-35:02 定理11.1.4。 2018-8-17 17:35
35:05-结束 邻接矩阵 邻接写1，几条重边就写几，不邻接写0，同一点上有环写1有几个环就写几。邻接矩阵 与 度 的关系。图与邻接矩阵，可以互相找到对方。开眼了。2018-8-17 17:46
https://v.youku.com/v_show/id_XMTU1NTAzMTk2.html?spm=a2h0j.11185381.listitem_page1.5!3~A&&f=4236391
第4讲内容：第11章 欧拉迹
开始-00:44 哥尼斯堡七桥问题 回忆。2018-8-17 19:30
00:45-02:55 例子 设想一个邮递员。2018-8-17 19:35
02:56-05:13 一笔画问题 图必须是连通的，要能回到出发点，每个点的度必须是偶数。2018-8-17 19:39
05:26-08:45 引理11.2.1 简介。2018-8-17 19:44
08:46-20:23 求闭迹的算法。2018-8-17 20:02
求闭迹的算法，在Dev-cpp4.9.9.2下编写。给书中作个勘误，P253 表 F列最后一行，倒数第2个，{h,b}改成{b,h}。
该算法是求某点的闭迹。该程序独立编出，除本书外，未参考其它资料。2018-8-18 17:16
图11-14 对应
输入数据：
9 13
i a
i h
a h
a h
a b
h b
b d
b c
d c
b e
b e
b g
b g
输出数据，截取部分如下：
a b c d b e b g b h a
a b c d b e b g b h i a
a b c d b e b h a
a b c d b e b h i a
a b c d b g b e b h a
a b c d b g b e b h i a
a b c d b g b h a
a b c d b g b h i a
a b c d b h a
//图11-14 很是奇怪 ，少了 f 这个点，在配置输入数据时，因为这个查了半天。
//2018-8-18 16:50
#include
#include
#define maxn 20
int e[maxn][maxn],n,m,u,v,w[maxn]; //n点数 m边数
char in1[maxn],in2[maxn];
void dfs(int pre_v,int step){
int i;
if(step>1&&u==pre_v){
for(i=0; iprintf("%c ",'a'+w[i]);
printf("\n");
return ;
}
for(i=0; iif(e[pre_v][i]>0){
e[pre_v][i]--; e[i][pre_v]--; //此处写成 e[pre_v][i]--;
w[step]=i;
dfs(i,step+1);
e[pre_v][i]++,e[i][pre_v]++; //此处写成e[pre_v][i]++; //回溯
}
}
int main(){
int i,j;
memset(e,0,sizeof(e));
scanf("%d%d",&n,&m);
for(i=1; i<=m; i++){
scanf("%s%s",in1,in2);
u=in1[0]-'a',v=in2[0]-'a';
e[u][v]++,e[v][u]++;
}
for(i=0; iu=i;
w[0]=i;
dfs(i,1);
}
return 0;
}
20:30-28:46 定理11.2.2。是个充要条件。2018-8-18 18:23
28:56-34:22 例子 继续前面的例子，利用定理。欧拉闭迹，目测算法，程序编起来有些累啊，还得再想想。2018-8-18 19:03
该算法是求某点的欧拉闭迹。该程序独立编出，除本书外，未参考其它资料。2018-8-18 18:12
图11-14 对应
输入数据：
9 13
i a
i h
a h
a h
a b
h b
b d
b c
d c
b e
b e
b g
b g
输出数据，截取部分如下：
a b c d b e b g b h a h i a
a b c d b e b g b h a i h a
a b c d b e b g b h i a h a
a b c d b g b e b h a h i a
a b c d b g b e b h a i h a
a b c d b g b e b h i a h a
a b d c b e b g b h a h i a
a b d c b e b g b h a i h a
a b d c b e b g b h i a h a
//图11-14 很是奇怪 ，少了 f 这个点，在配置输入数据时，因为这个查了半天。
//2018-8-18 20:14
#include
#include
#define maxn 20
int e[maxn][maxn],n,m,u,v,w[maxn],cnt; //n点数 m边数
char in1[maxn],in2[maxn];
void dfs(int pre_v,int step){
int i;
if(step==m+1){
for(i=0; i<=m; i++)
printf("%c ",'a'+w[i]);
printf("\n");
return ;
}
for(i=0; iif(e[pre_v][i]>0){
e[pre_v][i]--,e[i][pre_v]--,cnt++; //此处写成 e[pre_v][i]--;
w[step]=i;
dfs(i,step+1);
e[pre_v][i]++,e[i][pre_v]++,cnt--; //此处写成e[pre_v][i]++; //回溯
}
}
int main(){
int i,j;
memset(e,0,sizeof(e));
scanf("%d%d",&n,&m);
for(i=1; i<=m; i++){
scanf("%s%s",in1,in2);
u=in1[0]-'a',v=in2[0]-'a';
e[u][v]++,e[v][u]++;
}
for(i=0; iu=i;
w[0]=i;
cnt=0;
dfs(i,1);
}
return 0;
}
自我感觉，这个欧拉闭迹程序编得还不错。2018-8-18 20:15
34:35-40:28 定理11.2.3。欧拉开迹。2018-8-18 19:16
40:29-结束 定理11.2.4 简单提提。2018-8-18 19:16
https://v.youku.com/v_show/id_XMTU1NTAzMjAw.html?spm=a2h0j.11185381.listitem_page1.5!4~A
第5讲内容：第11章 欧拉迹 哈密尔顿路径和哈密尔顿圈
开始-02:23 定理11.2.4 证明。2018-8-20 07:38
02:52-06:43 图11-15 图11-16 图11-17 一笔画讨论。2018-8-20 07:47
06:44-10:57 由定理11.2.4 引出 中国邮递员 问题。2018-8-20 07:52
10:58-13:07 定理11.2.5。2018-8-20 08:38
13:08-16:29 中国邮递员问题的解决。突然想到，将一对一对的奇点用边连好，之后即可采用最短路径算法，解决中国邮递员问题了。2018-8-20 08:38
16:30-24:28 Hamilton哈密尔顿图。欧拉图，是走遍每条边一次；哈密尔顿图，是走遍每个点一次，至于边，不要求都走到。哈密尔顿链，哈密尔顿圈。哈密尔顿图，还没有找到充要条件，只能具体问题，具体分析。2018-8-20 08:54
19:07-19:24 12个面的解释，尤其是第12个，解惑确实不错。2018-8-20 08:44
24:29-25:29 完全图一定有哈密尔顿圈。有哈密尔顿圈，一定有哈密尔顿链。2018-8-20 09:16
25:30-33:37 有哈密尔顿链，未必有哈密尔顿圈，图11-19 讲解。介绍了桥的概念。2018-8-20 09:56
33:38-34:59 定理11.3.1。2018-8-20 09:56
35:00-结束 Ore性质。定理11.3.2。2018-8-20 10:32
38:42-38:48 还剩57个点 有误，应改成47个点，计算如下：总共50个点，x占用1个，x的度为2，相邻的点占用2个，故剩下不相邻的点为50-2-1=47。2018-8-20 10:32
https://v.youku.com/v_show/id_XMTU1NTAzMjA4.html?spm=a2h0j.11185381.listitem_page1.5!5~A&&f=4236391
第6讲内容：第11章 哈密尔顿路径和哈密尔顿圈 二分多重图 第9章 相异代表系
开始-01:43 没有桥，但是不存在哈密尔顿圈的例子，即将图11-19 右图c,d边变成一个点。2018-8-20 17:28
01:45-06:32 定理11.3.2 证明。G是连通的证明，反证法。简单图，无环，无重边。2018-8-22 08:09
06:34-23:45 求哈密尔顿圈的算法。视频看一遍，书看一遍，视频再看一遍，书再看一遍，重心放在(3)的证明，反复的看，(3)的证明还是有些函数，容再想想。2018-8-22 10:05
该算法是求某点的哈密尔顿圈。该程序独立编出，除本书外，未参考其它资料。2018-8-20 17:48
书中 图11-19 左图 对应
输入数据：
6 9
a b
a c
a e
c d
d e
d f
e f
b c
b f
输出数据，截取部分如下：
a b c d f e a
a b f e d c a
a c b f d e a
a c d e f b a
a e d f b c a
a e f d c b a
b a c d e f b
//图11-19 左图，哈密尔顿圈
//2018-8-20 17:46
#include
#include
#define maxn 20
int e[maxn][maxn],n,m,u,v,w[maxn],vis[maxn]; //n点数 m边数
char in1[maxn],in2[maxn];
void dfs(int pre_v,int step){
int i;
if(step==n&&e[pre_v][u]>0){
w[step]=u;
for(i=0; i<=step; i++)
printf("%c ",'a'+w[i]);
printf("\n");
return ;
}
for(i=0; iif(vis[i]==0&&e[pre_v][i]>0){
e[pre_v][i]--; e[i][pre_v]--,vis[i]=1; //此处写成 e[pre_v][i]--;
w[step]=i;
dfs(i,step+1);
e[pre_v][i]++,e[i][pre_v]++,vis[i]=0; //此处写成e[pre_v][i]++; //回溯
}
}
int main(){
int i,j;
memset(e,0,sizeof(e));
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&m);
for(i=1; i<=m; i++){
scanf("%s%s",in1,in2);
u=in1[0]-'a',v=in2[0]-'a';
e[u][v]++,e[v][u]++;
}
for(i=0; iu=i;
w[0]=i;
vis[i]=1;
dfs(i,1);
vis[i]=0;
}
return 0;
}
24:04-25:18 推论11.3.2。2018-8-22 10:09
25:40-26:15 定理11.3.4。2018-8-22 10:11
26:16-29:37 例子 旅行商问题。2018-8-22 10:16
30:01-结束 二分图(二部图)。2018-8-22 10:47
30:44-30:47 翻到197页，即第5版书中的198页。 2018-8-22 10:22
30:41-34:09 书中198页的几个问题。2018-8-22 10:33
34:10-36:13 二部图(二分图)定义，核心 同一个集合之间无边。2018-8-22 10:37
36:28-38:51 二部图(二分图)例子，及其表示方式。2018-8-22 10:40
38:52-结束 二部图(二分图) 与 书中198页的几个问题 关系。书中P199 图9-1 讲解。二部图(二分图)与棋盘的关系。2018-8-22 10:47
https://v.youku.com/v_show/id_XMTU1NTAzMjE2.html?spm=a2h0j.11185381.listitem_page1.5!6~A&&f=4236391
第7讲内容：第11章 二分多重图 第9章 相异代表系
开始-15:23 棋盘与二分图的关系。匹配 二部图(二分图)中无公共端点的边的集合。最大匹配。2018-8-23 09:10
15:41-29:12 书中P200 图9-3 多米诺骨牌 讲解。匹配。最大匹配。2018-8-23 09:27
29:22-39:40 书中P198 问题3 人员分配工作。匹配。最大匹配。2018-8-23 09:40
39:41-结束 最大匹配。总结了该讲的3个问题。2018-8-23 09:45
https://v.youku.com/v_show/id_XMTU1NTAzMjQ0.html?spm=a2h0j.11185381.listitem_page1.5!7~A&&f=4236391
第8讲内容：第12章 匹配数 第13章 回顾二分图匹配
开始-03:57 P300 图G的匹配数介绍。2018-8-25 17:55
04:05-07:34 翻书202页，实则是翻到P321 例子 考虑图13-7所示的二分图。2018-8-25 18:09
07:48-10:32 二部图的圈有偶数条边。2018-8-25 18:13
10:36-13:54 例子 考虑图13-8所示的二分图G。2018-8-25 18:22
13:58-16:28 讨论了匹配为0的情况。2018-8-25 18:26
16:29-19:09书中P321 M交错路径。2018-9-1 08:12
19:11-21:27 M交错路径 简单例子。2018-9-1 08:23
21:30-25:39通过例子 来说明 不属于M的变数=属于M的边数+1 。2018-9-1 09:11
25:51-结束 例子 考虑图中13-8所示的二分图G。2018-9-1 09:43
33:32-34:07 多一条边说明。2018-9-1 18:42
34:08-38:24 匹配证明。这个部分，笔者还是仔细想过了，想通还是花了点时间。2018-9-1 18:40
https://v.youku.com/v_show/id_XMTU1NTAzMjYw.html?spm=a2h0j.11185381.listitem_page1.5!8~A&&f=4236391
第9讲内容：第12章 匹配数 第13章 回顾二分图匹配

https://v.youku.com/v_show/id_XMTU1NTAzMjY4.html?spm=a2h0j.11185381.listitem_page1.5!9~A&&f=4236391













【图论 北师大 张秀平 自学 视频 NOIP】

    推荐阅读


    上一篇：51822静态配对密码

    下一篇：[Java]|通过Git提交项目到码云