首页 | 本学科首页   官方微博 | 高级检索  
     检索      


The Max-Flow Min-Cut theorem for countable networks
Authors:Ron Aharoni  Eli Berger  Agelos Georgakopoulos  Amitai Perlstein
Institution:a Department of Mathematics, Technion, Haifa, Israel 32000
b Department of Mathematics, Faculty of Science and Science Education, Haifa University, Israel 32000
c Universität Hamburg, Germany
Abstract:We prove a strong version of the Max-Flow Min-Cut theorem for countable networks, namely that in every such network there exist a flow and a cut that are “orthogonal” to each other, in the sense that the flow saturates the cut and is zero on the reverse cut. If the network does not contain infinite trails then this flow can be chosen to be mundane, i.e. to be a sum of flows along finite paths. We show that in the presence of infinite trails there may be no orthogonal pair of a cut and a mundane flow. We finally show that for locally finite networks there is an orthogonal pair of a cut and a flow that satisfies Kirchhoff's first law also for ends.
Keywords:Infinite graphs  Flows  Networks  Max-Flow Min-Cut  Ends of graphs
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号