图论-网络流①-什么是网络流

图论-网络流①-什么是网络流 下一篇:图论-网络流②-最大流①
参考文献:

  • https://www.cnblogs.com/DuskOB/p/11216861.html
  • https://blog.csdn.net/yjr3426619/article/details/82808303
  • https://blog.csdn.net/lym940928/article/details/90209172
  • https://baike.baidu.com/item/%E7%BD%91%E7%BB%9C%E6%B5%81/2987528?fr=aladdin
  • https://www.cnblogs.com/pk28/p/8039645.html
  • https://blog.csdn.net/disgustinglemon/article/details/51296636
网络流是一类图论算法,同时也多用于解决应用问题,是图论转化解决问题的代表性算法。
大纲
  • 什么是网络流Start \color{#33cc00}\texttt{Start} StartEnd \color{red}\texttt{End} End
  • 最大流(最小割)
  • D i n i c Dinic Dinic (常用)
  • E K EK EK
  • S a p Sap Sap
  • F o r d ? F u l k e r s o n Ford-Fulkerson Ford?Fulkerson(不讲)
  • H L P P HLPP HLPP (快)
  • 最大流解题
  • 费用流
  • E K EK EK 费用流
  • D i n i c Dinic Dinic 费用流
  • z k w zkw zkw 费用流
  • 费用流解题
  • 有上下界的网络流
  • 无源汇上下界可行流
  • 有源汇上下界可行流
  • 有源汇上下界最大流
  • 有源汇上下界最小流
  • 最大权闭合子图
  • 有上下界的网络流解题
什么是网络流
网络流(network-flows)是一种类比水流的解决问题方法,与线性规划密切相关。网络流的理论和应用在不断发展,出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。 ——百度百科
【图论-网络流①-什么是网络流】网络流图是一个有向图,不一定是有向无环图(DAG)。其中的点是网络流节点,边权是流量。大部分网络流有源点(S)和汇点(T)。如下:
图论-网络流①-什么是网络流
文章图片

如果把网络流图比作水管道系统,那么网络流节点就是一个水库,网络流边就是管道,网络流边的边权就是管道的宽度。源点就是某个输水的大江大河,汇点就是水最终流到的地方。
如果把网络流图比作电路图,那么源点汇点就分别是电源两头,网络流边就是导线,边权就是电流。
下一篇会讲最大流定义、最小割定理以及 D i n i c Dinic Dinic算法。
祝大家学习愉快!

    推荐阅读