Network

A generalization of the idea of a graph. A network is defined by a pair $ ( V , {\mathcal E} ) $, where $ V $ is a certain set and $ {\mathcal E} = ( E _ {0} ; E _ {1} ,\dots ) $ is a family of collection of elements from $ V $. The elements in the sets $ E _ {i} \in {\mathcal E} $ can, in general, be repeated. The elements of $ V $ are called the vertices of the network, those of $ E _ {0} $ its poles and the collections $ E _ {i} $, $ i = 1 , 2 \dots $ its edges. When the sets of poles is empty and each $ E _ {i} $ is a set, a network is a hypergraph. If each of the $ E _ {i} $, $ i = 1 , 2 \dots $ contains exactly two elements, the network is a graph with distinguished poles. Often, a network is regarded as a graph (with or without poles) to the elements of which are ascribed symbols from a certain set. For example, a graph with poles and such that to its edges are ascribed non-negative numbers, called channel capacities, is a transport network.

The concept of a network is used in the definition and description of a control system and of special classes of control systems (contact schemes, diagrams or functional elements), of transition diagrams of automata, communication networks, etc.

References

[1]	S.V. Yablonskii, "Fundamental concepts of cybernetics" Probl. Kibernet. , 2 (1959) pp. 7–38 (In Russian)
[2]	L.R. Ford, D.R. Fulkerson, "Flows in networks" , Princeton Univ. Press (1962)
[3]	J. Kuntzmann, "Théorie des réseaux (graphes)" , Dunod (1972)

Comments

For network in topology see Net (of sets in a topological space).

Most often, a network is simply defined as a graph $ \Gamma = ( V , E ) $ such that for each $ e \in E $ there is specified a (positive) number $ c _ {e} $, called the capacity of the edge $ e $. A directed network is a directed graph with for each $ e \in E $ a specified capacity $ c _ {e} $. Often $ c _ {e} $ is thought of as the maximal amount of something that can be transported over $ e $. But other interpretations are possible and occur. For example, a network of roads with $ c _ {e} = $ length of road $ e $ for each $ e \in E $.

A transportation network is a directed network with a specified vertex $ v _ {0} $, the source, and a second specified vertex $ v _ {1} $, the sink. Usually it is also assumed that there are no incoming arcs at $ v _ {0} $ and no outgoing arcs at $ v _ {1} $. For all $ e \in E $, $ v \in V $, let

$$ n ( e , v ) = \left \{ \begin{array}{rl} 1 & \textrm{ if } e \textrm{ is an incoming edge at } v , \\ - 1 & \textrm{ if } e \textrm{ is an outgoing edge at } v, \\ 0 & \textrm{ otherwise }. \\ \end{array} \right .$$

A flow in a transportation network is a function $ \phi : E \rightarrow \mathbf R $ such that $ 0 \leq \phi ( e) \leq c _ {e} $ and such that for all $ v \in V \setminus \{ v _ {0} , v _ {1} \} $ the following Kirchhoff law holds:

$$ \tag{a1 } \sum _ { e } n ( e , v ) \phi ( e) = 0 . $$

Sometimes an artificial arc, the return arc, going from $ v _ {1} $ to $ v _ {0} $, is added with capacity $ \infty $. By defining $ \phi ( \textrm{ return arc } ) = \sum _ {e} n ( e , v _ {1} ) \phi ( e) $, a flow is defined such that the Kirchhoff law holds for all vertices. This is the sole function of the return arc.

The network flow problem addresses the problem of calculating those flows for which $ \sum _ {e} n ( e , v _ {1} ) \phi ( e) $ is maximal.

In network planning one encounters "transportation networks" in which the edges correspond to tasks which can be performed and where the numbers $ c _ {e} $ represent, for example, the time needed to perform task $ e $. Here, finding a "shortest path" can be important.

An electrical network is a directed graph with for each $ e \in E $ two real numbers $ i _ {e} $ and $ E _ {e} $ specified (which are thought of as current and voltage, respectively). More generally, the $ i _ {e} $ and $ E _ {e} $ may well be functions of time or variables.

The currents $ i _ {e} $ are required to satisfy the Kirchhoff current law

$$ \sum _ { e } n ( e , v ) i _ {e} = 0 , $$

and the voltages $ E _ {e} $ are required to satisfy the Kirchhoff voltage law, which says that there are numbers $ E _ {v} $, the potential at node $ v $, such that

$$ \sum _ { v } n ( 1 , v ) E _ {v} = E _ {e} . $$

A branch (edge) of a network in which the current is given as an (input) function of time is called a current source, and a branch over which there is given an voltage is called a voltage source. A branch which is either a voltage or a current source is called a source branch. An electrical network with $ n $ specified source branches is called an $ n $- port.

If the currents in and the voltages across the (non-source) branches are related by

$$ E _ {e} = \sum _ {e ^ \prime } z _ {e e ^ \prime } i _ {e ^ \prime } $$

or

$$ i _ {e} = \sum _ {e ^ \prime } y _ {e e ^ \prime } E _ {e ^ \prime } , $$

where the $ z _ {e e ^ \prime } $ or $ y _ {e e ^ \prime } $ are linear integro-differential operators, one speaks of a linear electrical network. It is called reciprocal if $ z _ {e e ^ \prime } = z _ {e ^ \prime e } $ or $ y _ {e e ^ \prime } = y _ {e ^ \prime e } $. The network is called passive if

$$ \int\limits _ {- \infty } ^ { t } \sum _ {e \in S } i _ {e} ( \tau ) E _ {e} ( \tau ) d \tau \leq 0 $$

for all choices of the current sources and voltage sources for which the current/voltage relations are satisfied. Here $ S $ denotes the set of source branches.

Under certain non-singularity conditions for the currents in and voltages across the source branches one has the relations

$$ i _ {e} = \sum _ {e ^ \prime \in S } Y _ {e e ^ \prime } E _ {e ^ \prime } ,\ e \in S, $$

$$ E _ {e} = \sum _ {e ^ \prime \in S } Z _ { e e ^ \prime } i _ {e ^ \prime } ,\ e \in S. $$

The matrices $ Z $ and $ Y $ are, respectively, called the port-impedance matrix and the port-admittance matrix of the network.

Synthesis of electrical networks, or realizability theory, refers to the problem of finding an electrical network with (partly) given port-impedance and port-admittance matrices. Every passive linear one-port network can be realized using as branches positive resistors $ ( E _ {e} = R _ {e} i _ {e} ) $, positive capacitators $ ( i _ {e} = c _ {e} ( d E _ {e} / dt ) ) $ and positive inductors $ ( E _ {e} = L _ {e} ( d i _ {e} / dt ) ) $. Every linear passive $ n $- port with $ n > 1 $ can be synthesized using in addition ideal transformers (a pair of branches $ e _ {1} , e _ {2} $ such that $ i _ {2} = - n e _ {1} $, $ i _ {1} = n e _ {2} $) and ideal gyrators (a pair of branches $ e _ {1} , e _ {2} $ such that $ i _ {2} = E _ {1} $, $ E _ {2} = - i _ {1} $).

References

[a1]	L. Weinberg, "Network analysis and synthesis" , McGraw-Hill (1962)
[a2]	O. Brune, "Synthesis of a finite two-terminal network whose driving-point impedance is a prescribed function of frequency" J. Math. Phys. , 10 (1931) pp. 191–236
[a3]	C.H. Papadimitriou, K. Steiglitz, "Combinatorial optimization. Algorithms and complexity" , Prentice-Hall (1982)
[a4]	D.R. Fulkerson, "Flow networks and combinatorial operations research" D.R. Fulkerson (ed.) , Studies in graph theory , I , Math. Assoc. Amer. (1975) pp. 139–171
[a5]	C. Berge, "Graphs" , North-Holland (1985) pp. Chapt. 5
[a6]	G.I. Atebekov, "Linear network theory" , Pergamon (1965)
[a7]	P. Slepian, "Foundations of network analysis" , Springer (1968)
[a8]	N.K. Bose, "Applied multidimensional system theory" , v. Nostrand-Reinhold (1982) pp. Chapt. 5
[a9]	A. Budak, "Circuit theory. Fundamentals and applications" , Prentice-Hall (1978)
[a10]	M. Gondran, M. Minoux, "Graphs and algorithms" , Wiley (1986) pp. Chapt. 5 (Translated from French)
[a11]	S.A. Burr (ed.) , The mathematics of networks , Amer. Math. Soc. (1982)
[a12]	C.W. Cox, "Circuits, signals and networks" , Macmillan (1969)
[a13]	B. Carré, "Graphs and networks" , Clarendon Press (1979)
[a14]	R.G. Busacker, T.L. Saaty, "Finite graphs and networks" , McGraw-Hill (1965)