Flow network

Summary

In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes. Definition A network is a directed graph G = (V, E) with a non-negative capacity function c for each edge, and without multiple arcs (i.e. edges with the same source and target nodes). Without loss of generality, we

Official source

https://en.wikipedia.org/wiki/Flow_network

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (24)

Related publications

Related people (1)

Related people

Related units (1)

Related units

Related concepts (14)

Related concepts

Related courses (8)

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, sorting and searching, and graph algorithms.

The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer science and in practice.

This course is an introduction to linear and discrete optimization. Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to prove theorems.

Related courses

Related lectures (22)

Related lectures

Graph orientations with edge-connection and parity constraints

Parity (matching theory) and connectivity (network flows) are two main branches of combinatorial optimization. In an attempt to understand better their interrelation, we study a problem where both parity and connectivity requirements are imposed. The main result is a characterization of undirected graphs G = (V,E) having a k-edge-connected T-odd orientation for every subset with |E| + |T| even. (T-odd orientation: the in-degree of v is odd precisely if v is in T.) As a corollary, we obtain that every (2k)-edge- connected graph with |V| + |E| even has a (k-1)-edge- connected orientation in which the in-degree of every node is odd. Along the way, a structural characterization will be given for digraphs with a root-node s having k edge- disjoint paths from s to every node and k-1 edge-disjoint paths from every node to s.

2001

Interfaces and the edge percolation map of random directed networks

Paolo De Los Rios

The traditional node percolation map of directed networks is reanalyzed in terms of edges. In the percolated phase, edges can mainly organize into five distinct giant connected components, interfaces bridging the communication of nodes in the strongly connected component and those in the in and out components. Formal equations for the relative sizes in the number of edges of these giant structures are derived for arbitrary joint degree distributions in the presence of local and two-point correlations. The uncorrelated null model is fully solved analytically and compared against simulations, finding an excellent agreement. Interfaces, and their particular conformations giving place from "hairy ball" percolation landscapes to bottleneck straits, could bring new light to the discussion of how a structure is interwoven with functionality in flow networks.

2007

Structural Efficiency of Percolated Landscapes in Flow Networks

Paolo De Los Rios

The large-scale structure of complex systems is intimately related to their functionality and evolution. In particular, global transport processes in flow networks rely on the presence of directed pathways from input to output nodes and edges, which organize in macroscopic connected components. However, the precise relation between such structures and functional or evolutionary aspects remains to be understood. Here, we investigate which are the constraints that the global structure of directed networks imposes on transport phenomena. We define quantitatively under minimal assumptions the structural efficiency of networks to determine how robust communication between the core and the peripheral components through interface edges could be. Furthermore, we assess that optimal topologies in terms of access to the core should look like "hairy balls'' so to minimize bottleneck effects and the sensitivity to failures. We illustrate our investigation with the analysis of three real networks with very different purposes and shaped by very different dynamics and time scales-the Internet customer provider set of relationships, the nervous system of the worm Caenorhabditis elegans, and the metabolism of the bacterium Escherichia coli. Our findings prove that different global connectivity structures result in different levels of structural efficiency. In particular, biological networks seem to be close to the optimal layout.

Public Library of Science2008