International Encyclopedia of Systems and Cybernetics

A branch of mathematics dealing with the properties of the links between points or nodes in a network.

Graph theory, introduced by D. KÖNIG in 1936, is practically a formalized taxonomy in qualitative mathematical terms of the multiple possible types of interconnections between discrete elements.

There is a close relation between graphs and matrixes: A graph can be represented by a matrix, and vice-versa.

H. ATLAN writes: "The interest of graphs is that they do not only produce a pictorical representation, but that moreover their logical properties allow for an algorithmic writing – i.e. automatic – of the state equations of a system ".

D. GERNERT even proposes a "graph grammar" as "a formalism which allows the derivation of a new graph from an old one by a sequence of consecutive derivation steps" by the use of "graph rewriting systems" (1989, p.66).

According to A. KAUFMANN, graph theory is "… that field of set theory concerned with the binary relations of a set with itself, admitting that the set is countable. This theory is not autonomous in relation to the other developments of the set theory, but is possesses a specific vocabulary, very extensive and specialized, it opens a very large field of applications in physics, in economy, in psychology, in telecommunications, in organic chemistry, in organizations, in certain artistic domains, etc…" (1970, p.1).

As such, it is undoubtedly a quite basic tool for general system modeling and deserves in itself a complete study. Hereafter, a host of coordinated – and, as far as possible, standardized – definitions are given, with short comments. This material is essentially based on references from F. HARARY (1967), pw. KASTELEYN (1967), A. KAUFMANN (1970), G. KREWERAS (1972), S. LIPSCHUTZ (1976) and A. SACHE (1974). Generally no precise references are given hereafter, as the following is a blended synthesis of these authors views.

According to the general character of graphs, few references are made to any specific properties in particular disciplines.

Definitions given correspond to 2-dimensional representations. It is however possible, although much more difficult, to conceive 3-, 4- or n-dimensional representations, as for example the 4-dimensional hypercube with 16 nodes, which can be associated, for instance, with time sequences along connecting edges.

see figure page 174

To begin with, F. HARARY observes the rampant terminologic confusion that affects the field and establishes the following equivalences (1967, p.4):

"point _ vertex _ node _ junction _ O-simplex

"line _ edge _ arc _ branch _ 1-simplex

"cycle _ circuit _ elemantary cycle _ circuit path _ polygon

"path _ arc _ elementary path _ simple path _ chain

We have selected the underlined terms, but this is merely a more or less arbitrary decision, based on the necessity to avoid ambiguities. We would not dream to add still more confusion, but had it not been nice to call "arrow" (used by St. KAUFFMAN, 1993), the oriented edge ? We start thus with these four basic definitions:

NODE: A discrete element in a graph

EDGE: A direct connection between two nodes

ARC: An oriented edge between two nodes.

POLYGON: A closed succession of arcs such as the last node is the same as the first one.

The principal types of graphs are:

DIGRAPH, or directed graph, which consists of:

- a set of elements (nodes)

- a set of arcs (directed edges). The arcs define relations, sometimes also called "influences".

Digraphs can be labeled, i.e. affected with some kind of data. "Such graphs are frequently used to picture dynamic situations" (LIPSCHUTZ, 1976, p.119).

A digraph "is strongly connected or strong if each point (node) is reachable from each other point (node)…(it) is unilateraly connected or unilateral if, for any two points (nodes), at least one is reachable from the other… (it) is weakly connected, or weak if, for any division of its set of points (nodes) into two non-empty subsets, there is a line (edge) from a point (node) of one subset to a point (node) of the other" (HARARY, 1967, p.18).

Finally, it is disconnected if at least one node cannot be reached from any other.

"A source (root) of a digraph is a point (node) from which all other points (nodes) are reachable" (Ibid).

In this sense, a source or root is the inverse equivalent of a sink.

J. WARFIELD advocates extensive use of digraphs to map structural models of complex systems as a way to what he calls "Interpretive Structural Modeling" (1989b, Chapter 10).

He writes: "A graphically integrated language offers advantages in representing complexity. Such a language can have well-defined graphic symbols, and layers of representation of differing sophistications" (1995,e). TREE: "A finite connected graph with no cycles (polygons)" (LIPSCHUTZ, 1976, p.87).

"The tree consisting of a single vertex (node) with no edges is called the degenerate tree" (Ibid, p.105).

A tree starts from a root R, i.e. a node which does not receive any arc. Any other node in the tree receives only one arc. The tree may bifurcate at any successive node, including A and these bifurcations can be multiple (A. KAUFMANN, 1970, p.90).

As a result, there is a unique path from R to any node in the tree and the length of the path from R to any node N is made of n arcs, whose number characterizes the depth of N.

The end node in any path is called a leaf and the path from the root to a leaf is a branch.

Trees are very useful for the description of hierarchical organizations.

A MULTIGRAPH is a graph containing multiple edges connecting the same nodes and specially, loops, which are edges whose end node is the original node itself. According to S. LIPSCHUTZ: :"The definition of a graph does not permit such multiple edges or loops. In other words, we may define a graph to be a multigraph without multiple edges of loops" (1976, p.82).

Furthermore: "A multigraph is said to be finite if it has a finite number of vertices (nodes) and a finite number of edges" (Ibid., p.83).

A SUBGRAPH of a graph is a distinguishable part of the graph which is itself a graph. A good example is the set of the local roads on a map giving also the national roads. A subgraph may be or not be connected to the general graph. Subgraphs are generally more strongly and specifically connected than the graph as a whole.

Numerous types of more specific graphs have been defined, as for instance:

- The acyclic graph, which has no cycle (polygon): "A finite connected graph whith no cycles is called a tree" (LIPSCHUTZ, 1976, p.87).

- The anti-symmetric graph, in which the nodes may be connected by uni-directional arcs only. Examples are a genealogical tree, or the military hierarchical command order

- The bipartite graph, whose edges can be partitioned into two complementary subgraphs in such a way that each node of one subgraph is connected at least to a node of the other.

- The complementary graph which, by combination with another graph, constitutes a complete graph.

- The complete graph of which any node is connected to every other node. If the connections are merely edges, the graph represents a structure. It can be dynamized by the replacement of the edges by arcs.

- The connected graph in which there is always at least one path between any two nodes. However, even a unconnected graph may contain connected subgraphs.

- The strongly connected graph would be, after KAUFMANN, the central subgraph within a graph, in which all possible arcs between all nodes do exist.

- The Eulerian graph in which there is which there is a complete trail (walk) traversing the whole graph by a non-repetitive succession of edges or arcs. The typical non-Eulerian graph is the famous Koenigsberg bridges example studied by EULER (1736) and showing that no possible totally non-repetitive trail did exists for crossing the seven city's bridges once only in the same walk.

- The full graph is that one wherein all nodes are reciprocally connected one to one by two arcs of opposite direction (KAUFMANN, 1970, p.16).

- The Hamiltonian graph is the graph in which a closed walk includes every node once and only once.

The labeled graph in which "… edges and/or vertices (nodes) are assigned data of one kind or another" (LIPSCHUTZ, 1976, p.89).

- The non-polygonal graph in which there is no closed route between nodes. If such a graph is connected by arcs and if there is a circulation of flows entering by one node only, the graph becomes more or less definitively disconnected if the flow is interrupted, even briefly.

- The oriented graph whose all edges are arcs.

- The random isotropic directed graph in which an increasing number of randomly introduced oriented edges (arrows) lead to critical thresholds at which the connectivity properties change abruptly (St. KAUFFMAN, 1993, p.423). The condition is that the ratio of the number of arrows to the number of nodes must surpass a certain limit.

- The symmetric graph in which each arc joining one node A with another node B is complemented by a reciprocal arc BA.

Graphs of different networks can be compared. Isomorphic graphs "can be represented by the same abstract graph… if there is a one to one correspondence between their elements which preserves the incidence relation" (KASTELEYN, 1967, p.50).

Homeomorphic graphs are merely isomorphic in relation to some specific property of their structure. A square is homeomorphic to a diamond or a rectangle.

These different types of graphs can be used for different network situations.

Hereafter, some more definitions related to graph theory are given (or repeated).

BRANCH: In a tree, the path from the root to a leaf.

CHAIN: A continuous sequence of arcs.

CIRCUNFERENCE: The length of the longest polygon (or cycle).

CUT POINT (or OUTPOINT): In a connected graph, any point (node) whose removal results in a disconnected graph.

FOREST A graph with no polygons, i.e. whose all subgraphs are trees with interconnected roots.

GIRTH: The length of the shortest possible polygon (In J. WARFIELD 1989b, p.338: geodetic cycle).

HEAD: In an oriented graph, the first node in a chain

LOOP: An edge or arc whose origin and extremity coincide

MATRIX (Connection): The matrix which represents in a binary numerical form the edges or arcs and the connected nodes

NODE (Unreachable): A node not connected by any edge or arc. LIPSCHUTZ calls it an "isolated vertex".

NODE (Degree of a): The number of edges that are incident on it. This is the sum of the number of incoming and outgoing edges. BRYANT calls it the "valency" of the node

NODES (Distance between): The total length of the shortest path connecting them.

PATH: A walk with distinct edges. A path is simple if it does not use twice the same edge. It is elemental if it does not use twice the same node (Hamiltonian path).

ROOT: A node from which all other nodes can be reached. HARARY calls it "source ". In a tree the root emits but does not receive.

SINK: A node which receives but does not emit, i.e. the opposite of a root.

TAIL: In an oriented graph, the last node in a chain.

TRAIL: A walk with distinct arcs (Eulerian trail).

WALK: According to LIPSCHUTZ: "… an alternating sequence of vertices (nodes) and edges… The number of edges is called the length of the walk" (p.83).

WALK (Self-avoiding): A walk in which all nodes are distinct, with the possible exception of the first and the last ones (KASTELEYN, p.51).

WALK (Spanning): A walk which "… contains all the vertices (nodes) of the digraph (Ibid., p.120).

WALK (Steps of a): The edges included in the walk. (Ibid, p.51).

A last mention should refer to the P.E.R.T.(Process Evaluation and Review Tasks", a method to rationally order subtasks in a complex project. A P.E.R.T model is a graph extended into the time dimension, in which the shortest possible temporal path is sought by an optimal ordering of tasks.