图论与线性规划

算是个回顾吧。到底我很久没看图论甚至数学相关的东西了(看的都是 Haskell 或 thread local 这种),这次只是翻看了些原来就知道的知识。

首先从图论开始。大学课程一般会熟悉 Hall结婚定理,和著名的 最大流最小割 定理。这两个定理和数个其它定理实质上是等价的,参看 Equivalence of seven major theorems in combinatorics。结婚定理 和 最大流最小割 定理的相似性从他们的证明和实现算法上看其实相当明显,都是利用增广路这一工具。
很多图论问题或看起来非图论但可以用图来建模的问题最终都可以比较方便的归纳成最大流最小割问题。而同时最大流又可以用超著名的 线性规划 来解决(虽然在实现上一般不会这么做),然后它的对偶问题就是最小割问题。

线性规划的重要性不吝多言。需要注意的是 对偶 这一概念在很多更具通用性的场合都有应用,比如 凸优化KKT条件

好吧回顾到此为止,上面提到的基本都是在大学教程上就能找到的概念罢了。

Advertisements
This entry was posted in Science and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s