GRAPH THEORY
| Collection | International Encyclopedia of Systems and Cybernetics |
|---|---|
| Year | 2004 |
| Vol. (num.) | 2(1) |
| ID | ◀ 1466 ▶ |
| Object type | Methodology or model |
A branch of mathematics dealing with the properties of the Template:Ency term between points or Template:Ency term in a Template:Ency term.
Graph theory, introduced by Template:Ency person in 1936, is practically a formalized taxonomy in qualitative mathematical terms of the multiple possible types of Template:Ency term between discrete Template:Ency term.
There is a close relation between graphs and Template:Ency term: A graph can be represented by a Template:Ency term, and vice-versa.
Template:Ency person writes: “The interest of graphs is that they do not only produce a pictorical Template:Ency term, but that moreover their logical properties allow for an Template:Ency term writing — i.e. automatic — of the Template:Ency term equations of a system”.
Template:Ency person even proposes a “graph Template:Ency term” 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 “Template:Ency term systems” (1989, p.66).
According to Template:Ency person, graph theory is “… that field of Template:Ency term concerned with the Template:Ency term of a Template:Ency term with itself, admiting that the Template:Ency term is countable. This theory is not autonomous in relation to the other developments of the Template:Ency term, 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 Template:Ency term, in certain artistic domains, etc…” (1970, p.1).
As such, it is undoubtedly a quite basic tool for general system Template:Ency term 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 Template:Ency person (1967), Template:Ency person (1967), Template:Ency person (1970), Template:Ency person (1972), Template:Ency person (1976) and Template:Ency person (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 Template:Ency term. It is however possible, although much more difficult, to conceive 3- , 4- or n-dimensional Template:Ency term, as for example the 4-dimensional Template:Ency term with 16 Template:Ency term, which can be associated, for instance, with Template:Ency term sequences along connecting Template:Ency term.
To begin with, Template:Ency person observes the rampant terminologic confusion that affects the field and establishes the following equivalences (1967, p.4):
- “point É vertex É Template:Ency term É junction É 0-simplex
- “line É Template:Ency term É arc É branch É 1-simplex
- “cycle É circuit É elemantary cycle É circuit path É Template:Ency term
- “path É Template:Ency term É elementary path É simple path É chain
We have selected the ulined 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. Template:Ency person, 1993), the oriented edge ? We start thus with these four basic definitions:
Template:Ency term : A discrete Template:Ency term in a graph
Template:Ency term : A direct Template:Ency term between two Template:Ency term
Template:Ency entity : An oriented Template:Ency term between two Template:Ency term.
Template:Ency term : A closed succession of Template:Ency term such as the last Template:Ency term is the same as the first one.
The principal types of graphs are:
Template:Ency term , or directed graph, which consists of:
- a Template:Ency term of Template:Ency term (Template:Ency term)
- a Template:Ency term of Template:Ency term (directed Template:Ency term). The Template:Ency term define relations, sometimes also called “influences”.
Digraphs can be labeled, i.e. affected with some kind of Template:Ency term. “Such graphs are frequently used to picture dynamic Template:Ency term” (Template:Ency person, 1976, p.119).
A digraph “is strongly connected or strong if each point (Template:Ency term) is reachable from each other point (Template:Ency term)…(it) is unilateraly connected or unilateral if, for any two points (Template:Ency term), at least one is reachable from the other… (it) is weakly connected, or weak if, for any division of its Template:Ency term of points (Template:Ency term) into two non-empty Template:Ency term, there is a line (Template:Ency term) from a point (Template:Ency term) of one Template:Ency term to a point (Template:Ency term) of the other” (Template:Ency person, 1967, p.l8).
Finally, it is disconnected if at least one Template:Ency term cannot be reached from any other.
- “A Template:Ency term (Template:Ency term) of a digraph is a point (Template:Ency term) from which all other points (Template:Ency term) are reachable” (Ibid).
In this sense, a source or Template:Ency term is the inverse equivalent of a Template:Ency term.
Template:Ency person advocates extensive use of digraphs to map Template:Ency term of Template:Ency term as a way to what he calls “Template:Ency term” (1989b, Chapter 10).
He writes: “A graphically integrated Template:Ency term offers advantages in representing Template:Ency term. Such a Template:Ency term can have well-defined graphic Template:Ency term, and Template:Ency term of Template:Ency term of differing sophistications” (1995,e).
Template:Ency term: “A finite connected graph with no cycles (Template:Ency term)” (Template:Ency person, 1976, p.87).
- “The tree consisting of a single vertex (Template:Ency term) with no Template:Ency term is called the degenerate tree” (Ibid, p.105).
A tree starts from a Template:Ency term R, i.e. a Template:Ency term which does not receive any Template:Ency term. Any other Template:Ency term in the tree receives only one Template:Ency term. The tree may bifurcate at any successive Template:Ency term, including A and these Template:Ency term can be multiple (Template:Ency person, 1970, p.90).
As a result, there is a unique Template:Ency term from R to any Template:Ency term in the tree and the length of the Template:Ency term from R to any Template:Ency term N is made of n Template:Ency term, whose number characterizes the depth of N.
The end Template:Ency term in any Template:Ency term is called a Template:Ency term and the Template:Ency term from the Template:Ency term to a Template:Ency term is a Template:Ency term.
Trees are very useful for the description of hierarchical Template:Ency term.
A Template:Ency term is a graph containing multiple Template:Ency term connecting the same Template:Ency term and specially, Template:Ency term, which are Template:Ency term whose end Template:Ency term is the original Template:Ency term itself. According to Template:Ency person: :“The definition of a graph does not permit such multiple Template:Ency term or Template:Ency term. In other words, we may define a graph to be a multigraph without multiple Template:Ency term of Template:Ency term” (1976, p.82).
Furthermore: “A multigraph is said to be finite if it has a finite number of vertices (Template:Ency term) and a finite number of Template:Ency term” (Ibid., p.83).
A Template:Ency term of a graph is a distinguishable Template:Ency term of the graph which is itself a graph. A good example is the Template:Ency term of the local roads on a Template:Ency term 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 Template:Ency term.
Numerous types of more specific graphs have been defined, as for instance:
- The Template:Ency term, which has no Template:Ency term (Template:Ency term): “A finite connected graph whith no cycles is called a Template:Ency term” (Template:Ency person, 1976, p.87).
- The Template:Ency term, in which the Template:Ency term may be connected by uni-directional Template:Ency term only. Examples are a genealogical Template:Ency term, or the military hierarchical command order
- The Template:Ency term, whose Template:Ency term can be partitioned into two complementary Template:Ency term in such a way that each Template:Ency term of one Template:Ency term is connected at least to a Template:Ency term of the other.
- The Template:Ency term which, by combination with another graph, constitutes a complete graph.
- The Template:Ency term of which any Template:Ency term is connected to every other Template:Ency term. If the Template:Ency term are merely Template:Ency term, the graph represents a Template:Ency term. It can be dynamized by the replacement of the Template:Ency term by Template:Ency term.
- The Template:Ency term in which there is always at least one Template:Ency term between any two Template:Ency term. However, even a unconnected graph may contain connected Template:Ency term.
- The Template:Ency term would be, after Template:Ency person, the central Template:Ency term within a graph, in which all possible Template:Ency term between all Template:Ency term do exist.
- The Template:Ency term in which there is which there is a complete Template:Ency term (Template:Ency term) traversing the whole graph by a non-repetitive succession of Template:Ency term or Template:Ency term. The typical non-Eulerian graph is the famous Koenigsberg bridges example studied by Template:Ency person (1736) and showing that no possible totally non-repetitive Template:Ency term did exists for crossing the seven city's bridges once only in the same Template:Ency term.
- The Template:Ency term is that one wherein all Template:Ency term are reciprocally connected one to one by two Template:Ency term of opposite direction (Template:Ency person, 1970, p.16).
- The Template:Ency term is the graph in which a closed Template:Ency term includes every Template:Ency term once and only once.
- The Template:Ency term in which “…Template:Ency term and/or Template:Ency term) are assigned Template:Ency term of one kind or another” (Template:Ency person, 1976, p.89).
- The Template:Ency term in which there is no closed route between Template:Ency term. If such a graph is connected by Template:Ency term and if there is a circulation of Template:Ency term entering by one Template:Ency term only, the graph becomes more or less definitively disconnected if the Template:Ency term is interrupted, even briefly.
- The Template:Ency term whose all Template:Ency term are Template:Ency term.
- The Template:Ency term in which an increasing number of randomly introduced oriented Template:Ency term (arrows) lead to critical Template:Ency term at which the Template:Ency term properties change abruptly (St. Template:Ency person, 1993, p.423). The condition is that the ratio of the number of arrows to the number of Template:Ency term must surpass a certain Template:Ency term.
- The Template:Ency term in which each Template:Ency term joining one Template:Ency term A with another Template:Ency term B is complemented by a reciprocal Template:Ency term BA.
\it Graphs of different Template:Ency term can be compared.
Template:Ency term “can be represented by the same abstract graph… if there is a one to one correspondence between their Template:Ency term which preserves the incidence relation” (Template:Ency person, 1967, p.50).
Template:Ency term are merely Template:Ency term in relation to some specific property of their Template:Ency term. A square is Template:Ency term to a diamond or a rectangle.
These different types of graphs can be used for different Template:Ency term Template:Ency term.
\it Hereafter, some more definitions related to graph theory are given (or repeated).
Template:Ency term: In a Template:Ency term, the Template:Ency term from the Template:Ency term to a Template:Ency term.
Template:Ency term: A continuous sequence of Template:Ency term.
Template:Ency term:The length of the longest Template:Ency term (or Template:Ency term).
Template:Ency term : In a Template:Ency term, any point (Template:Ency term) whose removal results in a disconnected graph.
Template:Ency person: A graph with no Template:Ency term, i.e. whose all Template:Ency term are Template:Ency term with interconnected Template:Ency term.
Template:Ency person: The length of the shortest possible Template:Ency term (Template:Ency termTemplate:Ency person 1989b, p.338Template:Ency term).
Template:Ency term: In an Template:Ency term, the first Template:Ency term in a Template:Ency term
Template:Ency term: An Template:Ency term or Template:Ency term whose origin and extremity coincide
Template:Ency term (Connection): The matrix which represents in a Template:Ency term numerical form the Template:Ency term or Template:Ency term and the connected Template:Ency term
Template:Ency term (Unreachable): A node not connected by any Template:Ency term or Template:Ency term. Template:Ency person calls it an “isolated vertex”.
Template:Ency term (Degree of a): The number of Template:Ency term that are incident on it. This is the sum of the number of incoming and outgoing Template:Ency term. Template:Ency person calls it the “valency” of the node
Template:Ency term (Distance between): The total length of the shortest Template:Ency term connecting them.
Template:Ency term: A Template:Ency term with distinct Template:Ency term. A path is simple if it does not use twice the same Template:Ency term. It is elemental if it does not use twice the same Template:Ency term (Hamiltonian path).
Template:Ency term: A Template:Ency term from which all other Template:Ency term can be reached. Template:Ency person calls it “source”. In a Template:Ency term the root emits but does not receive.
Template:Ency term: A Template:Ency term which receives but does not emit, i.e. the opposite of a Template:Ency term.
Template:Ency term: In an oriented graph, the last Template:Ency term in a Template:Ency term.
Template:Ency term: A Template:Ency term with distinct Template:Ency term (Eulerian trail)
Template:Ency term: According to Template:Ency person: “… an alternating sequence of vertices (Template:Ency term) and Template:Ency term… The number of Template:Ency term is called the length of the walk” (p.83).
Template:Ency term (Self-avoiding): A walk in which all Template:Ency term are distinct, with the possible exception of the first and the last ones (Template:Ency person, p.51).
Template:Ency term (Spanning): A walk which “… contains all the vertices (Template:Ency term) of the Template:Ency term (Ibid., p.120).
Template:Ency term (Steps of a): The Template:Ency term included in the walk. (Ibid, p.51).
A last mention should refer to the Template:Ency term.(Template:Ency term Evaluation and Review Tasks“, a method to rationally order subtasks in a complex project. A P.E.R.T Template:Ency term is a graph extended into the Template:Ency term dimension, in which the shortest possible temporal Template:Ency term is sought by an optimal ordering of tasks.