我们正在努力恢复Google Play商店上的Unionpedia应用程序
传出传入
🌟我们简化了设计以优化导航!
Instagram Facebook X LinkedIn

最大流最小割定理

指数 最大流最小割定理

在最优化理论中,最大流最小割定理提供了对于一个网络流,从源点到目标点的最大的流量等于最小割的每一条边的和。即对于一个如果移除其中任何一边就会断开源点和目标点的边的集合的边的容量的总和。 最大流最小割定理是线性规划中的对偶问题的一种特殊情况,并且可以用来推导Menger定理和König–Egerváry定理。.

目录

  1. 9 关系: 当且仅当克劳德·香农线性规划网络流Edmonds–Karp算法集合划分Ford–Fulkerson算法有界最优化

  2. 图论定理
  3. 網絡流
  4. 组合优化

当且仅当

当且仅当(If and only if)(中国大陆又称作当且--仅当,臺灣又称作若且--唯若),在--邏輯中,逻辑算符反互斥或閘(exclusive or)是对两个运算元的一种邏輯分析类型,符号为XNOR或ENOR或\Leftrightarrow。与一般的邏輯或非NOR不同,當兩兩數值相同為是,而數值不同時為否。在数学、哲学、逻辑学以及其他一些技术性领域中被用来表示“在,并且仅仅在这些条件成立的时候”之意,在英语中的对应标记为iff。“A当且仅当B”其他等价的说法有“当且仅当A則B”;“A是B的充分必要条件(充要條件)”。 一般而言,當我們看到“A当且仅当B”,我們可以知道“如果A成立時,則B一定成立;如果B成立時,則A也一定成立”;“如果A不成立時,則B一定不成立;如果B不成立時,則A也一定不成立”。.

查看 最大流最小割定理和当且仅当

克劳德·香农

克劳德·艾尔伍德·香农(Claude Elwood Shannon,),美国数学家、电子工程师和密码学家,被誉为信息论的创始人。 香农是密西根大學學士,麻省理工學院博士。 1948年,香农发表了划时代的论文——通信的数学原理,奠定了现代信息论的基础。不仅如此,香农还被认为是数字计算机理论和数字电路设计理论的创始人。1937年,21岁的香农是麻省理工學院的硕士研究生,他在其硕士论文中提出,将布尔代数应用于电子领域,能够构建并解决任何逻辑和数值关系,被誉为有史以来最具水平的硕士论文之一。二战期间,香农为军事领域的密码分析——密码破译和保密通信——做出了很大贡献。.

查看 最大流最小割定理和克劳德·香农

线性规划

在數學中,線性規劃(Linear Programming,簡稱LP)特指目標函數和約束條件皆為線性的最優化問題。 線性規劃是最優化問題中的一個重要領域。在作業研究中所面臨的許多實際問題都可以用線性規劃來處理,特別是某些特殊情況,例如:網路流、多商品流量等問題,都被認為非常重要。目前已有大量針對線性規劃算法的研究。很多最優化問題算法都可以分解為線性規劃子問題,然後逐一求解。在線性規劃的歷史發展過程中所衍伸出的諸多概念,建立了最優化理論的核心思維,例如「對偶」、「分解」、「凸集」的重要性及其一般化等。在微观经济学和商业管理领域中,线性规划亦被大量应用于例如降低生产过程的成本等手段,最終提升產值與營收。乔治·丹齐格被認爲是线性规划之父。.

查看 最大流最小割定理和线性规划

网络流

在圖論中,網絡流(Network flow)是指在一個每條邊都有容量(capacity)的有向圖分配流,使一條邊的流量不會超過它的容量。通常在運籌學中,有向图称为网络。顶点称为节点(node)而边称为弧(arc)。一道流必須符合一個結點的進出的流量相同的限制,除非這是一個源點(source)──有較多向外的流,或是一個匯點(sink)──有較多向內的流。一個網絡可以用來模擬道路系統的交通量、管中的液體、電路中的電流或類似一些東西在一個結點的網絡中遊動的任何事物。.

查看 最大流最小割定理和网络流

Edmonds–Karp算法

计算机科学中, Edmonds–Karp算法通过实现Ford–Fulkerson算法来计算网络中的最大流,其时间复杂度为O(VE^2)。该算法由Yefim (Chaim) Dinic 在1970年最先提出并由Jack Edmonds和理察·卡普在1972年独立发表。.

查看 最大流最小割定理和Edmonds–Karp算法

集合划分

在数学中,集合X的划分是把X分割到覆盖了X的全部元素而又不重叠的“部分”或“块”或“单元”中。更加形式的说,这些“单元”對于被划分的集合是既又相互排斥的。.

查看 最大流最小割定理和集合划分

Ford–Fulkerson算法

Ford–Fulkerson方法(Ford-Fulkerson method)或 Ford–Fulkerson算法(FFA)是一类计算网络流的最大流的贪心算法。 之所以称之为“方法”而不是“算法”,是因为它寻找增广路径的方式并不是完全确定的,而是有几种不同时间复杂度的实现方式它在1956年由L.R.Ford,Jr.

查看 最大流最小割定理和Ford–Fulkerson算法

有界

有界可以指:.

查看 最大流最小割定理和有界

最优化

最优化,是应用数学的一个分支,主要研究以下形式的问题:.

查看 最大流最小割定理和最优化

另见

图论定理

網絡流

组合优化