Spatial Network Generation Tool for Performance Analysis of Water Distribution Networks - Pattern Recognition for Reliability Assessment of Water Distribution Networks - page 69

A graph can be complete, tree or fractal, as shown in Figure 4.4. A complete graph contains
every possible pair of vertices connected by an edge. It is therefore impossible to add an edge
to a complete graph without creating duplications or self-connected vertices. Graphs where
this is not done are called simple graphs . Where multiple connections between the same pair
of vertices or self-connected vertices are possible, the graphs are called pseudo graphs or
degenerated graphs . The complete graph of n vertices will have total n ( n -1)/2 edges. A tree
graph is a graph without loops where any two vertices are connected by unique single path.
Finally, a fractal graph specifies a geometric shape that can be split into parts, each of which
is a reduced size copy of it (Möderl et al., 2009). Hence, the fractal is a geometric pattern that
is composed of equal smaller shapes.
Furthermore, graph can be planar or non-planar. A planar graph has edges that only touch
each other at vertices. If the edges cross, as is the case in Figure 4.4a, the graph will have
non-planar representation . Non-planar graphs are rare, although not impossible in water
distribution practice. It is therefore common to place a node at the intersection of pipes,
which implies that network generation tool should avoid non-planar graphs.
Figure 4.5 Spanning sub-graphs
Graph normally consists of spanning sub-graphs, as shown in Figure 4.5. A graph is a
spanning sub-graph or a factor of another graph if both share the same vertex set. Moreover,
the sub-graph will be induced in case it only contains the edges also available in the original
graph.
Both simple graphs and pseudo graphs can be represented by an adjacency matrix . For graphs
with n nodes, this matrix has n x n elements where A ij is equal to the number of links
connecting nodes i and j (for i ≠ j ). Diagonal elements A ii will count twice the number of self-
connecting links attached to node i, because each endpoint of the link is to be counted once.
Applying the terminology of graph theory for the simple network shown in Figure 4.6, an
undirected graph G (V, E) is the object consisting of set V (vertices) and set E (edges) such