Undirected graphs

Bron C and J Kerbosch 1973. Algorithm 475. Finding All Cliques of an Undirected Graph. Communia tions of the ACM 16 575-577. 

Intuitively, a graph can be realized geometrically in a three-dimensional Euclidean space vertices arc represented by points and edges are represented either by lines (in the case of undirected graphs) or arrows (in the case of directed graphs). In this book, we will be concerned with both kinds of graphs multiple edges i.e. when vertices arc connected by more than one line or arrow), however, are not allowed. 

A graph G is connected if for every pair of distinct vertices in G there exists at least one path along existing edges. The connected (undirected) graph of order N which has the smallest size is called a tree. In fact, a tree T is equally well characterized by any of the following properties ... 

Conventional CA models are defined on particular lattice-networks, the sites of which are populated with discrete-valued dynamic elements evolving under certain local transition functions. Such a network with N sites is simply a general (undirected) graph G of size N and is completely defined by the NxN) connectivity matrix... 

Whereas the propagation of conditions through the modeling relationships always produces consistent completions in the definition of the initial state, this may not be true with the user-driven specifications. It is possible that a valve specified by the user to be OPEN, is found by the propagation of other conditions to be CLOSED. To detect such potential inconsistencies, we have developed a dependency network (Steele, 1980) to keep track of the flow of computations during constraint propagation. The dependency network is built on the undirected graph that represents the... 

In the foregoing discussion the properties of the incidence matrix and the cycle matrix were illustrated in terms of a cyclic digraph, but the results on the ranks of these matrices actually hold true for any connected digraph with N vertices. For an undirected graph, M and C contain only 0 and 1 (sometimes referred to as binary matrices), mathematical relations of identical form are obtained except that modulo 2 arithmetic2 is used instead of ordinary arithmetic. The ranks of M and defined in terms of modulo 2 arithmetic are JV — 1 and C, as before, and Eqs. (10) and (11) are modified to read... 

M Incidence matrix. M refers to a digraph (6b), and fil refers to an undirected graph (6a)... 

Figure 2. Periodic orbit with one intersection on undirected graphs two different paths exist having the same length following either the black or blue orbit.

The topography of the plant is represented by an undirected graph and consists of nodes and undirectional edges. The paths through the plant are represented by node lists, which are chronologically sorted by the point of time an AGV reaches the center of a node. Additionally the nodes include attributes which specify the points of time an AGV enters and leaves a node and the period of time which the AGV waits at the center of a node. These additional attributes are needed during the conflict resolution to model waiting, acceleration and deceleration of an AGV. 

Generally, a chemical plant is composed of several units with several streams and components. The set of material and energy balances constitutes a set of linear/nonlinear equations, which can be represented by an undirected graph. However, when the number of units and streams is large, the graphical representation becomes cumbersome. An alternative representation of the topological structure of the balances in a chemical process is achieved using the occurrence matrix. 

The output set assignment assigns to any unmeasured process variable one equation, or to two or more variables the same number of equations. This is equivalent to transforming the original undirected graph to a directed one. 

Bron, C. and Kerbosch, J. Finding all cliques of an undirected graph [Hj. Commun. Assoc. Comput. Machinery. 1973, 16, 575-577. 

G. Levi, A Note of the Derivation of Maximal Common Subrgaphs of Two Directed or Undirected Graphs, Calcolo, 9 (1972) 341-352. 

The code contains consecutively the number of cycles (routes) and vertices (intermediates) N, the supergraph type S. the classes (A,, C, and 2) the subclasses (the subscripts /, L, and /O. and the number of vertices in each cycle Nf. (The full code actually includes a more detailed class notation which lists the connections between the pairs of cycles in increasing order, as seen from Table 2.4.) The code provides a one toK>ne correspondence with the undirected kinetic graph described above. Some examples now follow for mechanisms described by undirected graphs. 

---