• 数论的素数测试理论:这个暂不总结,等把代码写了再总结。
  • PS:研究下gprof的行计数:

1。http://sourceware.org/binutils/docs-2.16/gprof/Annotated-Source.html#Annotated-Source,但加有条件编译的行居然返回乱码!

2。gprof实现,秒了一眼,貌似[本菜的第一感觉而已,少拍少拍mount()]比较简单,

  • 图论的基本知识部分[看得晕头转向,我更喜欢搜索的风格]

1。图连通性:

  • 点连通性->点割集,割点,G的k(G)为点数最少割集的点数[G的点连通度]
  • 边连通性->边割集,桥,G的k'(G)为边数最少的边割集的边数[G的边连通度]
  • 图的连通性->连通分量,强连通图[对于任意两点,双向路径可达]

两个莫名其妙的定理[不晓得怎么证明]

Menger定理:G是k-连通图的充要条件是G中任何两点之间有k条独立路[无公共点的路]

度序列的k连通定理:设图的度序列为d(v1)<=d(v2)…<=d(vn),若存在k(0<=k<=n),使得d(vn)<=j+k-1,则G是k-连通的

2。图着色问题:

  • 点着色问题:[通常我们只研究这个,菜鸟嘛,见BOP上面非常非常简单的描述,转化为图着色问题,OK,很典型的CSP问题,N-Queen的框架]

其模糊的上下界分析:1<=X(G)<=n,X(G)>=[n/q],X(G)<=Max(d)+1…….

  • 边着色问题:对于简单图X‘(G)=Max(d),这类图为K2n,称为第一类图,即二分图;另一类X'(G)=Max(d)+1,这类图为K2n+1,称为第二类图。
  • 色多项式:用k种颜色给图G上色,那么方案数为一个Pk(G)多项式。性质见黑书。这里只说一个P(G)=P(G1)-P(G2),将u,v连通边合并后,直到零图。显然对于零图的色多项式为k^n.好了,这个是我唯一看懂的地方,觉得很精妙,90分的思路,顶点合并。

3。独立集,团,完美图

  • 以前看过,独立集和团互补,我们用单射函数可以从一个G图得到其补图,那么G的独立集就是其生成补图的团。
  • 一M的多结论,不写了,我觉得没多大必要的,用CSP搜索即可,没多大意思[浅见,个人浅见]

4。可行连通性问题

  • 著名的Hamilton路以及回路问题基于顶点的周游,太出名了,出名的地球人都知道[提一下,可以用状态标记的动规来生成其代价最小回路,参见高级动规。PS:不晓得高在什么地方,因为凹凸性以及用栈扫描的部分看得我到现在都二懂二懂,这个还好!公式很平易近人]
  • 出名的Emuler路以及回路问题:基于边的周游
  • TSP问题
  • 中国邮递员问题:若找不到Emuler回路,那么怎样才能在每条边至少走一次后,回到出发点,并且使得回路上权和最小。

Advertisements