In this paper we investigate the existence and uniqueness of solution to a real gas flow pipeline network by representing the network by graph. A directed graph is an efficient way to represent a gas network. The pipelines and compressors are represented as edges of the graph and the interconnecting points are represented as nodes of the graph representing the network. In a directed graph representation of a gas network, each edge has been assigned a flow direction. Existence and Uniqueness of Solutions to the Generalized Riemann Problem for Isentropic Flow is discussed in . In that paper a gas flow in networks of pipelines is considered. Their models are based on the generalized Riemann problem formulation, where the flow in each connected pipe section is described by the hyperbolic conservation law supplemented by initial conditions within each section of the flow network. In our case, we consider a steady state and isothermal flow in the pipelines, which enables us to simplify the three conservation laws (mass, momentum, and energy) into a single equation for each pipeline, see (3.1). The flow equation of the gas in a compressor is given in (3.2). As we are employing graph theory to study the gas flow network, reviews of some preliminary concepts from graph theory are presented in the first section of this paper. In the second section we present the mathematical model for steady state real gas flow in a pipeline network. Section three contains the discussion about existence and uniqueness of solution for a real gas flow network.
A graph is a structure consisting of a finite set V of elements called vertices or nodes and a set E whose elements are called edges . A directed graph or digraph is a graph in which each edge has a direction from one node to another. A walk of a graph G is defined as a finite alternating sequence of vertices and edges, beginning and ending with vertices, such that each edge is incident with the two vertices immediately preceding and following it. A walk in which no vertex appears more than once is called a path. A path beginning and ending with the same vertex is called a cycle.
A graph G is said to connected if there is at least one path between every pair of vertices in G. A tree is a connected graph with no cycles. A spanning tree T of G is a tree consisting of all vertices in G. For a given spanning tree T of G, any edge in G which is not in the tree T is called a chord. A basic result from graph theory states that adding a chord to a spanning tree T will create exactly one cycle. Such a cycle formed by adding a chord to a spanning tree is called a fundamental cycle.
Theorem 1: A tree with n vertices has edges.
Proof: The theorem will be proved by induction. on the number of vertices. It is easy to see that the theorem is true for . Assume that the theorem holds true for all trees with fewer than n vertices. Let us now consider a tree T with n vertices. In T let be an edge with end vertices and . Since there is one and only one path between every pair of vertices in a tree, there is no other path between and other than . Therefore, deletion of from T will disconnect the graph. Furthermore, consists of exactly two components, and there are no cycles in T, each of these components is a tree. Both of these trees ahve fewer than n vertices each, and therefore, by the induction assumption, each contains one less edge than the vertices in it. Thus has edges. Hence T has exactly vertices.
Theorem 2: Let n and e be the number of vertices and edges, respectively, in a connected graph G. Let T be a spanning tree of G. Then
1) The number of edges in T is and the number of chords corresponding to the spanning tree T is chords.
2) The number of the fundamental cycles corresponding to the spanning tree T is exactly the number of chords, .
1) Since a spanning tree is a tree, theorem 1 can be used to show the first part of 1). Since a chord is an edge in G which is not in the given spanning tree T, the number of chords corresponding to T is the total number of edges e in the graph G minus those edges which belong to the spanning tree T, i.e. .
2) From part 1), we know that we have only chords. Each chord creates a fundamental cycle, and hence the number of the fundamental cycles with respect to the given spanning tree is .
Incidence matrix of a digraph
Let G be a directed graph with n vertices and e edges, with no circuits (cycles). The node-edge incident matrix A of G is an n × e matrix, defined as
Theorem 3: If A is the incident matrix of a connected graph with n nodes, the rank of A is
Proof: Since there are exactly one −1 and one 1 in every column of the incidence matrix A, the sum of all these row vectors is 0. Thus the n vectors are not linearly independent. Therefore, the rank of A is less than n. Since the graph G is connected, it cannot be partitioned like
such that is with m rows and with rows. In other words, no m by m sub matrix of A can be found, for , such that the sum of those m rows is equal to zero. Since there are only three constants −1, 0, and 1 in this field, the additions of all vectors taken m at a time for exhausts all possible linear combinations of row vectors. Thus we have just shown that no linear combination of m row vectors of A, for can be equal to zero. Therefore, the rank of A must be at least . Since the rank of A is no more than and no less than , it must be exactly equal to .
A matrix , which is by e obtained from A by deleting one of its rows is called reduced incident matrix.
Theorem 4: The reduced incidence matrix of a tree is invertible.
Proof: A is the incidence matrix of a tree means, by theorem 2, it has n rows and columns. Hence, is an by matrix. By theorem 3, A has rank implies that is of rank . Since is a square matrix of order and has rank , is invertible.
Cycle (circuit) matrix of a digraph
Let be the un-directed version of a digraph G, i.e., is the graph G with out considering the directions. Each cycle in , after being assigned an arbitrary orientation, can be represented by a vector whose components are are −1, 1, or 0 according to whether and how the edge is included in the cycle. A cycle matrix B is a matrix where each row corresponds to a cycle vector, and is defined by
A cycle is also called circuit.
A set of fundamental cycles with respect to any spanning tree in a connected digraph are the only independent cycles in the digraph, since each contains an edge not in any of the others. The rest of cycles can obtained as linear combinations of these fundamental cycles. A sub matrix of the matrix B in which all rows correspond to the fundamental cycles is called Fundamental Cycle matrix. If n is the number of vertices and e the number of edges in a connected digraph, then is an by e matrix, because the number of fundamental cycles is , each fundamental cycle being produced by one chord. Since the fundamental cycles are linearly independent the rank of is .
Theorem 5: Let B and A be, respectively, the circuit matrix and incidence matrix of a digraph such that the columns in B and A are arranged using the same order of edges. Then
Proof: Consider the mth row in B and the kth row in A. If the cycle m does not include any edge incident on vertex K, the product of the two rows is clearly zero. If, on the other hand, vertex k in cycle m, there are exactly two edges (say x and y) incident on K that are also in cycle m. This situation can occur in only four different ways. The possible entries in row k of A and row m of B in column positions x and y are tabulated in Table 1 for each of these four cases. In each case, the dot product is zero.
3. Mathematical Model of a Steady State Gas Flow in Pipeline Networks
A typical gas network consists of one or more gas sources, one or more gas deliveries, pipelines, compressors, and other devices, such as valves and regulators  . The compressors are installed in the network to increase the gas pressure so that the gas can flow through the pipeline to the locations where it is consumed. Valves and regulators provide control of the gas flow rate, prevent excessive growth of pressure in the network.
Table 1. Possible entries in row k of A and row m of Bin column positions x and y.
We consider the three basic components of a gas network to model the gas flow in pipeline networks:
2) compressors, and
3) nodes (interconnection points).
A directed graph is an efficient way to represent a gas network. The pipelines and compressors are represented as edges of the graph and the interconnecting points are represented as nodes of the graph representing the network. In a directed graph representation of a gas network, each edge has been assigned a flow direction. If the actual direction of the gas flow coincides with the direction of the edge, the flow rate is positive, otherwise the flow rate is negative.
3.1. Gas Flow in Pipes
Gas flow in a pipe is described by the three conservation laws (mass, momentum, and Energy) closed by an equation of state. If we consider the flow to be steady state and isothermal, the gas flow can be described by the following equations
where is the gas density, u is the average flow velocity, P is the pressure, T is the temperature, f is friction factor, x is position, and D is the diameter of the pipe. If we use the volumetric flow rate Q and pressure P as flow variables, and
use the substitution the above equations can be written as:
If we consider that c is the average of its values at the two end points of the pipe, we can integrate the above equation to get
The logarithmic terms are because of the inertia term included in eqn which is neglected by many authors.
3.2. Compressor Equations
Compressors are installed in the gas network to transport gas and compensate for the loss of energy due to frictional resistance which results in a loss of pressure at the downstream of the pipe. The flow rate through the compressor and pressures at the upstream and downstream of the compressor are related by the following equation.
is inlet pressure.
is outlet pressure.
is flow rate through the compressor.
W is power of the compressor.
is compressor efficiency.
is ratio of specific heats.
is compressibility factor at entry.
3.3. Node Equations
We can categorize the nodes in the network as source nodes (where gas is supplied to the system), junction nodes (where two or more edges are connected), and sink nodes (where gas is delivered for consumption). At a source nodes either the pressure or the flow rate is specified. While at junction or a sink node a flow rate balance is made.
3.3.1. Pressure Node
If the pressure value is specified at a node of the network, then we get the equation
at this node.
3.3.2. Flow Node
The node at which we balance the flow rates coming into and going out of the is called flow node. Suppose a flow node connects N edges (pipes or compressors) and has a nodal flow rate . is positive if gas is added in to the network, negative if gas is tapped out of the network, and zero if there is no gas entering or leaving the network at this node.
Then balancing the flow rate at this node gives us
is the set of incoming flows in to the ith Flow Node.
is the set of outgoing flows from the ith Flow Node.
Therefore, the steady state, isothermal gas flow in pipeline networks is described by a non-linear simultaneous equation containing (3), (4), (5), and (6).
This system of equations can be written as
4. Existence and Uniqueness of the Solution to a Network Which Can Be Represented by a Tree
In the present section, proofs for existence and uniqueness of solutions to a gas flow network will be given. First, we present a proof of uniqueness of solutions which is based on a monotonicity property of a mapping. Existence is then proved with the help of the contraction mapping theorem (4.2). Assume the gas flow network of n nodes can be represented by a tree. Suppose the pressure value , of one node, say node 1 is given. By theorem (1) this tree has edges. Let and A be, respectively, the pipe-node incidence matrix and the edge-node incidence matrix of the tree. Let be the reduced incidence matrix. Now the network equations can be written as:
where and are, respectively, pipe flows and compressor flows. Since is obtained from A by deleting the row corresponding to the reference node, it is by matrix and is invertible. Hence, there is a unique solution for the last Equation in (8). If we have t compressors involves 2 pressures, there fore the t pressures can be determined if the values of the other t pressures are known. Assuming the t pressures from the compressor equations and one pressure from the reference node are known, we have only unknown pressures. By substituting the known flow rates and the known pressures in to the pipe equations we get equations for unknown pressures. Since the rows of are rows of the reduced incidence matrix , they are linearly independent. This implies is invertible and we get the unique solution for the first Equation of (8). This gives us unique P as is one-to-one.
4.1. Uniqueness of the Solution to a Gas Flow Network
In this section, let us assume we have a network of pipes, with no compressor, which can be represented by directed graph. Suppose the gas flow network has n nodes. Assume the pressure is given at a reference node, say at node 1. Then our network system of Equations (7) takes the form:
Let be the reduced cycle matrix with respect to some spanning tree. The size of is by e, and its rank is . The above system is equivalent to
Now let us consider the system
The system (11) contains only the flow variable Q. The first equation contains equations and the second contains equations. Hence, system (11) consists of e equations for e unknown flwo rate variables. First, we show that the solution of the system (11) is unique, and then it can be shown that the first two equations of system (10)
give unique P. System (12) consists of equations for n unknowns. But, we can eliminate equations as they are linar combinations of the others, since are expressed in terms of the others in the equation .
Now let us show that the solution of system (11) is unique.
Definition: A mapping is said to be strictly monotonic if for every we have
and equality holds if and only if .
Theorem 6: Let , for some positive integer d, is given by
with . Then is strictly monotonic.
Proof: For every ,
The function is a strictly increasing function for all s. Hence, each term on the right-hand side is non-negative. Thus,
Equality holds if and only if every term at the right hand side is zero, so , for every j. There fore, is strictly monotonic.
Definition: Let , be two integers, and . We say an matrix A and a matrix B are perpendicular to each other if they satisfy
1) , ;
Let and . Then we have M perpendicular to N and
Theorem 7: Let matrices A and B be perpendicular to each other. Suppose is strictly monotonic, then foe every , the solution to the system of equations
Proof: Suppose both u and v are solutions of system (13), then
Hence, , and . Thus . Since is strictly monotonic, the above equation implies that . Hence, the solution is unique.
By applying the above theorem, and taking , ,and , it is shown the solution of the system (11) is unique.
4.2. Existence of the Solution for a Gas Flow Network
In this section, we discuss the existence of solution to a general gas flow network that contains pipes and compressors. Let us consider a network of m pipes, t compressors, and n nodes. Assume the pressure is given, say at node 1, i.e. . We use the The Contraction Mapping Theorem to show existence of a solution for such gas flow network.
Definition: Let be a metric space. A function is called a contraction mapping if there exists such that and
for any .
Theorem 8: (The Contraction Mapping Theorem): If is a complete metric space and is a contraction mapping, then T has one and only one fixed point, (i.e., there exists exactly one such that ).
Sketch of the proof of the Contraction Mapping Theorem. The complete proof is found in . The proof proceeds in several steps:
1) starting from an arbitrary , construct the sequence by taking ;
2) prove that , and therefore for any natural numbers with ;
3) conclude that is a Cauchy sequence, and thus, since X is complete, converges;
4) prove that is a fixed point of T;
5) prove that x is the only fixed point of T.
Now, we want to show that the equation
has locally unique solution. The Contraction Mapping Theorem can be applied as follows: If we can find such that the jacobian determinant, J, of T at is different from zero, then we can introduce
The equation is equivalent to . If G is a contraction mapping, then G has a unique fixed point and thus .
The jacobian is expressed in the following form
Choose such that , and
Example: Let us consider the following network with 3 pipes, 1 compressor, and 5 junctions.
The Jacobian of the matrix of the system of equations of the gas flow network dipicted in Figure 1 is given by
By performing elementary row and column operations on J
For our example given above
Figure 1. Example of a gas flow network.
Let be the matrix obtained by deleting the rows and columns containing the Pressure Nodes, then
Properties of are
1) Diagonally dominant (column), strictly dominant at column j, where node j is connected to a Pressure Node( there is at least one Pressure Node).
Hence, is invertible.
J is invertible.
Since is continuous at
Choose such that
If , then
G is a contraction in
G has a unique fixed point.
has a unique solution in
In this paper, we discussed the existence and uniqueness of solution to the real gas flow network. A review of some basic concepts from graph theory is given as we discussed the flow network as a graph. The flow network is represented by a graph in which pipes and compressors are represented as edges and the junction points as nodes of the graph. The flow is assumed to be steady state and isothermal. The Contraction Mapping Theorem is applied to show the existence of the solution to the considered gas flow network, and its uniqueness is proved using monotonicity property of a mapping.
u Flow velocity
Pu Upstream pipe inlet pressure
Pd Downstream pipe outlet pressure
Q Volumetric flow rate in a pipe
D Pipe diameter
L Pipe length
W Compressor power
Zcu Comprehensibility factor of a gas at compressor entry
R Gas constant
Qc Flow rate through the compressor
Ratio of specific heats
Pcu Inlet compressor pressure
Pcd Outlet compressor pressure
 Reigstad, G.A. (2015) Existence and Uniqueness of Solutions to the Generalized Riemann Problem for Isentropic Flow. SIAM Journal on Applied Mathematics, 75, 679-702.