首页 > 其他分享 >「Note」图论方向 - 网络流

「Note」图论方向 - 网络流

时间:2023-08-27 12:22:35浏览次数:37  
标签:图论 定义 容量 增广 sum 网络 流量 Note

1. 网络流

1.1. 定义

1.1.1. 网络

网络是指一个有向图 \(G=(V,E)\),每条边 \((u,v)\in E\) 有一个权值,\(c(u,v)\) 称为容量,当 \((u,v)\notin E\) 时,有 \(c(u,v)=0\)。

特殊地,在图中有源点汇点两点,分别为 \(s\in V,t\in V\)。

1.1.2. 流

流函数 \(f(u,v)\to\R(u,v\in V)\) 表示由二元组 \((u,v)\) 向实数集 \(\R\) 的映射,我们称 \(f(u,v)\) 为边 \((u,v)\) 的流量。

流函数 \(f(u,v)\) 需满足以下性质:

  • 容量限制:对于每条边,其流量不能超过其容量,即 \(f(u,v)\le c(u,v)\)。
  • 斜对称性:相反两边流量和为 \(0\),即 \(f(u,v)=-f(v,u)\)。
  • 流守恒性:从源点流出的流量等于流入汇点的流量,也可称除源汇点外所有点流入流出流量相等,即 \(\forall x\in V\land i\notin\{S,T\},\sum f(u,x)=\sum f(x,v)\)。

流函数完整定义:

\[f(u,v)=\begin{cases}f(u,v),&(u,v)\in E\\-f(v,u),&(v,u)\in E\\0,&(u,v)\notin E,(v,u)\notin E\end{cases} \]

1.1.3. 其他定义

对于当前状态下的网络,定义源点流出的流量(流入汇点的流量)为网络此状态下(当前流)的流量

对于边 \((u,v)\) 定义 \(C_f(u,v)\) 为此边容量与流量之差,表示此边的剩余流量,即 \(C_f(u,v)=c(u,v)-f(u,v)\)。

对于图 \(G\) 定义 \(G_f\) 为 \(G\) 中所有节点与剩余流量大于 \(0\) 的边构成的子图,表示残余网络,即 \(G_f=(V,E_f)\),其中 \(E_f=\{(u,v)|c_f(u,v)>0\}\)。

定义增广路 \(P\) 为残余网络 \(G_f\) 上从 \(s\) 到 \(t\) 的路径。

定义,将点集 \(V\) 分为无交集的两集合 \(A,B\) 且 \(s\in A,t\in B\),这种点的划分方式称为。定义割的容量为 \(\sum\limits_{u\in A} \sum\limits_{v\in B}c(u,v)\),割的流量为 \(\sum\limits_{u\in A} \sum\limits_{v\in B}f(u,v)\)。若边 \((u,v)\) 中 \(u,v\) 所属点集不同,称此边为一条割边

1.2. 网络最大流(最小割)

进入正题,给定网络 \(G=(V,E)\) 与源汇,求此网络的最大流量。

1.2.1 最大流最小割定理

最大流等于最小割,证明如下。

对于每一单位的流量,设其经过割边 \((u,v)(u\in A,v\in B)\) 的次数为 \(\mathrm{to}\) 经过边 \((v,u)\) 的次数为 \(\mathrm{back}\)。一定有 \(\mathrm{to}=\mathrm{back}+1\),否则不可能从源点流至汇点。

可以得出流量等于割边流量不大于割边总容量,即割的容量。得出结论:

  • 任意一组流的流量不大于一组割的流量。

当最大流存在时,此时残余网络一定无法增广,从而得到 \(s,t\) 不连通,残余网络也不连通,自然我们得到了一组割,此时最大流量等于割的容量。得出结论:

  • 存在一组流的流量等于一组割的容量。

综上所述,可以得到最大流等于最小割

1.2.2. 增广

采用贪心的思想对残余网络 \(G_f\) 进行增广,具体围绕以下两原则:

  • 能流满就流满
  • 不断寻找增广路

具体地,对于我们在 \(G_f\) 上找到的一条增广路 \(P\),根据能流满就流满的原则,我们令其增加流量 \(c_f(P)=\min\limits_{(u,v)\in P}c_f(u,v)\)。

为保证贪心的正确性,我们尝试加入反悔操作。将边 \((u,v)\) 的流量增加 \(c_f(P)\),可以理解成将边 \((u,v)\) 的剩余容量减少 \(c_f(P)\),我们在进行此操作的同时将反边 \((v,u)\) 的剩余容量减少 \(c_f(P)\),使得我们可以在接下来的操作中进行增广。所以对于每一条边来说我们维护的实际上是其剩余流量。

1.2.3 EK 算法

EK 并不是 EK 鲁比,而是 Edmonds-Karp。

采用 BFS 找一条长度最短增广路,再进行增广,就这样。
时间复杂度为 \(O(nm^2)\),证明详见 OI-Wiki。

1.2.4 Dinic 算法

对于网络用 BFS 进行分层,在 DFS 进行多路增广时只允许向下一层的点转移。这样将网络视为 DAG,规范增广路形态,避免了环的出现。

Dinic 算法的核心优化为当前弧优化。增广时,对于容量等于流量的边无需访问,不是每次遍历都需要从邻接表头进行枚举。我们记录一个第一条没有流满的边,从此进行遍历即可。

优化后的 Dinic 时间复杂度为 \(O(n^2m)\),证明详见 OI-Wiki,我实在是太懒了。

标签:图论,定义,容量,增广,sum,网络,流量,Note
From: https://www.cnblogs.com/Eon-Sky/p/17658059.html

相关文章

  • 网络IO控制——Quality of Service
    早上没吃饭,坐在公司里测试,等结果等的太无聊,翻译一下libvirt上的关于网络IO控制的一点内容。希望翻译完,就可以吃饭了。原文如下:...<devices><interfacetype='network'><sourcenetwork='default'/><targetdev='vnet0'/><bandwidth>......
  • 2023.08.20CCPC网络赛
    rank:732,寄首先开场打E手速不行,还WA了一两发,其次D开始觉得是二分让队友先写了一发,后面看出是三分,但是反应过来的时候只剩20min了,而且是在队友之前的代码上改的,手忙脚乱,最后还是没有调出来,令人寒心;D.DiscreteFourierTransform题意:根据欧拉公式可以将原式化成许多个与fk的值为......
  • Cross-Origin Read Blocking (CORB) 网络兼容性和对其他资源的影响问题
    CORB对图像的影响CORB对标签应该没有明显的影响<img>,除非图像资源1)被错误地标记为不正确的、非图像的、受CORB保护的Content-Type和2)与响应标头一起提供X-Content-Type-Options:nosniff。例子:正确标记的HTML文档标签中使用的资源<img>:正文:一个HTML文档Co......
  • Web 安全字体和网络字体 (Web Fonts)
    什么是Web安全字体网络安全字体是由许多操作系统预先安装的字体。虽然不是所有的系统都安装了相同的字体,但你可以使用网络安全字体堆栈来选择几种看起来类似的字体,并且安装在你想支持的各种系统上。如果你想使用预装字体以外的字体,从CSS3开始,你可以使用网络字体Webfonts-Learn......
  • HyperLedger Fabric基础:搭建Fabric测试网络(三)
    在本系列第二篇中,我们介绍了如何创建通道与在通道上启动链码的问题。本篇将探索如何使用Peer客户端与区域链网络通信。启动测试网络后,可以使用Peer节点CLI与网络进行交互。Peer节点CLI允许您从CLI调用已部署的智能合约、更新通道或安装和部署新的智能合约。确定当前我们仍处于test-......
  • 计算机网络自顶向下方法
    1、概论1.1、什么是Internet?1.1.1、从具体构成角度节点:主机及其上运行的应用程序;路由器、交换机等网络交换设备。边:接入网链路:主机连接到互联网的链路;主干链路:路由器间的链路。互联网是数以亿计的、互联的计算机设备:主机=端系统;运行网络应用程序。1.1.2、从......
  • GPT之路(四) 神经网络架构Transformer工作原理
     原文:WhatAreTransformerModelsandHowDoTheyWork?Transformer模型是机器学习中最令人兴奋的新发展之一。它们在论文AttentionisAllYouNeed中被介绍。Transformer可以用于写故事、文章、诗歌,回答问题,翻译语言,与人类聊天,甚至可以通过对人类来说很难的考试!但是它们到底......
  • 网络基础-IP
    网络中的IP地址IP地址的作用:用于标识一个节点的网络合法的地址只有ABC这三类,DE配置不了A:0-127     类型:网络+主机+主机+主机  ||默认子网掩码: 255.0.0.0B:128-191    类型:网络+网络+主机+主机  || 默认子网掩码: 255.255.0.0C:192-223    类型:......
  • 网络配置之 vlan
    什么是广播域概念:能够接收到同样广播消息的网络节点的集合缺陷:当同一个广播域内广播报文过多时,会对局域网造成干扰,导致网络延迟,网络拥塞(上网卡,上网慢),严重情况可以造成广播风暴,导致网络瘫痪,给网络的可靠性和安全性带来了严重挑战。2、如何解决广播1)利用路由器分割广播域:路......
  • 网络之路由器交换机的设置
    一、基础知识之(交换机的)虚接口vlan1.端口加入vlan[S1]interfaceGigabitEthernet0/0/1[S1-GigabitEthernet0/0/1]portlink-typeaccess接口模式配置为access模式[S1-GigabitEthernet0/0/1]portdefaultvlan2接口加入vlan2<S1>displayvlan 查看当前配置的vlan ......