最大流最小割定理
最大流最小割定理是最优化理论的定理。根据该定理，在一个网络流中，从源点到汇点的最大的流量，等于它的最小割中每一条边的容量之和。“割”指的是一种边的集合，如果移除这个集合的全部边，就会断开源点和汇点的连接。 最大流最小割定理是线性规划中的对偶问题的一种特殊情况，并且可以用来推导门格尔定理和König–Egerváry定理。 定义 最大流和最小割定理是图论的一部分，因此为了准确定义，我们需要先定义图、流、割，然后再定义这个定理。 图 设 G…
标签：#網絡流
共 7 篇文章
网络流
在圖論中，網絡流（）是指在一個每條邊都有容量（Capacity）的有向圖分配流，使一條邊的流量不會超過它的容量。通常在运筹学中，有向图称为网络。顶点称为节点（Node）而边称为弧（Arc）。一道流必須符合一個結點的進出的流量相同的限制，除非這是一個源點（Source）──有較多向外的流，或是一個匯點（Sink）──有較多向內的流。一個網絡可以用來模擬道路系統的交通量、管中的液體、電路中的電流或類似一些東西在一個結點的網絡中遊動的任何事物…
福特-富尔克森算法
福特-富尔克森方法（），又稱福特-富尔克森算法（），是一类计算网络流的最大流的贪心算法。之所以称之为“方法”而不是“算法”，是因为它寻找增广路径的方式并不是完全确定的，而是有几种不同时间复杂度的实现方式。它在1956年由小萊斯特·倫道夫·福特及德爾伯特·雷·富爾克森发表。“福特-富尔克森”这个名词通常也指代埃德蒙兹-卡普算法，这是一个特殊的福特-富尔克森算法实现。 算法的思想如下：只要有一条从源点（开始节点）到汇点（结束节点）的路径，在…
迪尼茨算法
迪尼茨算法（）是在网络流计算最大流的强多项式复杂度的算法，设想由以色列计算机科学家在1970年提出。算法O(V^2 E)的时间复杂度类似于埃德蒙兹-卡普算法，其时间复杂度为O(VE^2)，迪尼茨算法与埃德蒙兹-卡普算法的不同之处在于它每轮算法都选择最短的可行路径进行增广。迪尼茨算法中采用高度标号（level graph）以及阻塞流（blocking flow）实现性能。 历史 迪尼茨在格奧爾吉·阿傑爾松-韋利斯基（AVL树的发明者之一）…
最大流问题
在优化理论中，最大流问题（）涉及到在一个单源点、单汇点的网络流中找到一条最大的流。 最大流问题可以被看作是一个更复杂的网络流问题（循环问题，circulation problem）的特殊情况。s-t流（从源点s到汇点t）的最大值等于s-t割的最小容量，这被称为最大流最小割定理。 历史 最大流问题最早是在1954年由和F·S·羅斯（F. S. Ross）通过一个苏联铁路的交通流量的简化模型提出的。 1955年，小萊斯特·倫道夫·福特和德爾…
布雷斯悖论
布雷斯悖论（）是1968年由德國數學家迪特里希·布雷斯提出的一個悖論，它是指在一个交通网络上增加一条路段反而使网络上的旅行时间增加；这一附加路段不但没有减少交通延滞，反而降低了整个交通网络的服务水准。 这一悖论在电网和生物系统中也有相似的例子。理论上，在一些情况下，去除网络的一部分可能可以改善网络。这一悖论可以解释现有主要道路关闭后交通反而改善的例子。这种出力不讨好且与人们直观感受相背的现象主要源於纳什均衡並不一定使社會最優化。 发现和…
多物網絡流問題
多物網絡流問題（Multi-commodity Flow Problem）是多種物品（或貨物）在網絡中從不同的源點流向不同的匯點的網絡流問題。 定義 已知一流網絡\,G(V,E)，其中邊(u,v) \in E的容量為\,c(u,v)。有\,k件物品K_1,K_2,\dots,K_k，定義為\,K_i=(s_i,t_i,d_i)，其中\,s_i和\,t_i是物品\,i的源點及匯點，及\,d_i是需求。物品\,i沿邊\,(u,v)的流量是\…