A Category of “Undirected Graphs”

Abstract

In this paper, a category of undirected graphs is introduced where the morphisms are chosen in the style of mathematical graph theory rather than as algebraic structures as is more usual in the area of graph transformation.

A representative function, ${\omega }$, within this category is presented. Its inverse, ${\omega }^{-1}$, is defined in terms of a graph grammar, ${\varepsilon }$.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 The Abstract Category

Hartmut Ehrig was one who helped introduce the graph grammar community (GraGra) to the concept of categories [6]. In this short paper we apply some of his vision to develop a category of undirected graphs. A graph (V, E) is undirected if its edge set E consists of sets $\{x, y\}$, not ordered pairs. It is not hard to characterize one version of this category. It consists of obj = UG, the collection of all finite undirected graphs, together with hom = all functions, $f:G \rightarrow G',$ where $G, G' \in UG$, with composition, that is $f:G \rightarrow G', g:G' \rightarrow G''$ implies $f {{ \cdot }}g: G \rightarrow G'' \in hom$. Let $G = (V, E)$ and $G' = (V', E')$. By $f:G \rightarrow G'$ we actually mean $f:2^V \rightarrow 2^{V'}$ subject to appropriate constraints with respect to the edge sets E and $E'$.¹ But, without specifying these constraints this kind of category conveys little information.

More interesting is the subcategory whose functions f, g are continuous (see below). Continuity in the familiar continuous manifolds, such as R or C, is defined in terms of open sets. With discrete, or finite, graphs it can be better defined in terms of closed sets.

Let $\varphi$ denote an arbitrary closure operator on an arbitrary collection, $2^V$, of sets, that is for all subsets $X, Y, \in 2^V$, $\varphi$ is expansive ($Y \subseteq Y.\varphi$), monotone ($X\subseteq Y$ implies $X.\varphi \subseteq Y.\varphi$) and idempotent ($Y.\varphi .\varphi = Y.\varphi$).² Such closure systems $(2^V, \varphi )$ are rather well studied, since they include matroids and antimatroids [2,3,4,5, 8]. More importantly, we can now define what we mean by a continuous, discrete, set-valued function f. A function $f:(2^V, \varphi ) \rightarrow (2^{V'}, \varphi ')$ is said to be continuous [11, 12] if for all $Y \subseteq V$,

$$\begin{aligned} Y.\varphi .f \subseteq Y.f.\varphi ' \end{aligned}$$

We observe that the closure operator, $\varphi '$ on $V'$ need not be the same as $\varphi$ on V. To obtain a category, we must now show that the composition of continuous functions $f {{ \cdot }}g$ is continuous. But, they need not be. The composition $f {{ \cdot }}g$ of continuous, set-valued functions will be continuous provided f and g are also monotone [12]. To create a subcategory, we need both properties.

Suppose the functions f and g are also “closure preserving”, that is the image of any set Y, closed with respect to $\varphi$ will be closed with respect to $\varphi '$. In this case,

$$\begin{aligned} Y.f.\varphi ' \subseteq Y.\varphi .f \end{aligned}$$

so $Y.\varphi .f = Y.f.\varphi '$, yielding the categorical diagram.

Fig. 1.

A typical categorical diagram

The preceding discussion creates a subcategory of continuous set-valued functions. But as yet, it has nothing to do with undirected graphs!

As before, let obj be the set of all undirected graphs, $G = (V,E)$ where V is a set of vertices, points, or nodes and E is a symmetric binary relation on V, commonly called the edge set. Now, we consider hom to be the collection of all continuous, monotone, set-valued functions mapping subsets of the vertex (point, node) set, V of G into subsets of the vertex set $V'$ of $G'$. We expect, somehow, that the closure operator on these graphs should reflect their edge structure. Let ${\eta }$ be an operator on $2^V$ such that $y \in \{x\}.{\eta }$ and $x \in \{y\}.{\eta }$ if and only if $\{x, y\}$ is an edge in G. It is convenient if ${\eta }$, a neighbor operator is reflexive, that is $x \in \{x\}.{\eta }$. We, now, extend ${\eta }$ to subsets $Y \subseteq V$ by $Y.{\eta }= \cup _{y \in Y} \{y\}.{\eta }$. Some texts call these “closed neighborhoods”.³ In the case of undirected graphs we prefer to use neighborhood closure ${\varphi _{\eta }}$, defined below

$$\begin{aligned} Y.{\varphi _{\eta }}= \{ z |\{z\}.{\eta }\subseteq Y.{\eta }\} \end{aligned}$$

(1)

Because ${\eta }$ is reflexive, ${\varphi _{\eta }}$ is expansive; it is monotone by construction; and idempotency is not hard to prove [14, 15].

Now we have the makings of a category, UG, of undirected graphs consisting of $obj =$ the collection of all undirected graphs, and $hom =$ all monotone, set-valued functions $f:2^V \rightarrow 2^{V'}$ that are continuous with respect to ${\varphi _{\eta }}$. It is worth observing that this development allows us to continuously enlarge graphs by a function $f:2^V \rightarrow 2^{V'}$ in which ⁴ and to contract graphs with $g:2^{V'} \rightarrow 2^{V''}$ where . It is convenient to employ the notation $f:G \rightarrow G'$ with the understanding that f is really defined on the power sets of V and $V'$ and that f is continuous with respect to a closure operator $\varphi$ on the edge set/relation E.

Is UG anything more than an abstract category? Are there really functions in hom?

In the next section we present two graph transformations which define ${\omega }\in hom$ and ${\varepsilon }\in hom$. Both have been implemented as algorthmic computer programs.

2 Two Functions in hom(UG)

Let G be a graph (V, E), with a neighborhood operator ${\eta }$. Suppose $z \in \{y\}.{\varphi _{\eta }}$, implying by (1) that $\{z\}.{\eta }\subseteq \{y\}.{\eta }$. Since $\{z\}.{\varphi _{\eta }}= \{y\}.{\varphi _{\eta }}$, the set $\{z\}$ contributes nothing to the closure structure of G; it can be removed from G with little loss of information. We define the transformation ${\omega }_z: G \rightarrow G'$ by where ${\omega }_z$ is the identity map on $V - \{z\}$, $Y \subseteq V$, and $\{u', v'\} \in E'$ if and only if $\{u, v\} \in E$, $u, v \ne z$. We say z has been subsumed by y. It is not hard to show that ${\omega }_z$ is both monotone and continuous since $z \in \{y\}.{\varphi _{\eta }}$.

2.1 Reduction, ${\omega }$

A computer procedure, reduce implements ${\omega }$. It repeatedly sweeps through all vertices $y \in V$, deleting any vertices $z_i \in \{y\}.{\varphi _{\eta }}$, together with all edges incident to $z_i$, until no such z remain in V.⁵ That is, ${\omega }= {\omega }_{z_1} {{ \cdot }}{\omega }_{z_2} {{ \cdot }}\ldots {{ \cdot }}{\omega }_{z_n}$. Since each ${\omega }_{z_i}$ is monotone and continuous, ${\omega }$ is as well, that is $Y.{\varphi _{\eta }}.{\omega }\subseteq Y.{\omega }.{\varphi _{\eta }}'$. The process terminates when every singleton subset $\{y\} \subseteq V$ is closed. Such a graph is said to be irreducible.

It can be shown that $G' = G.{\omega }$ is unique (up to isomorphism) regardless of the order in which the vertices $y \in V$ are visited by ${\omega }$ or the order in which vertices $z \in \{y\}.{\varphi _{\eta }}$ are deleted [14,15,16]. So ${\omega }$ is a well defined function in hom(UG). Because every singleton set (vertex) in $G'$ is closed, ${\omega }$ must also be closure preserving, with $Y.{\omega }.{\varphi _{\eta }}' \subseteq Y.{\varphi _{\eta }}.{\omega }$, so the diagram of Fig. 1 is applicable when $f = {\omega }$.

In Fig. 2, the graph G of 18 vertices is reduced to $G' = G.{\omega }$ with 10 remaining vertices. In G, the dashed lines encircle the vertices that were subsumed by $2', 3', 15'$ and $17'$.

Fig. 2.

Reduction, ${\omega }$, of a graph G

Irreducible graphs, such as $G'$, have a number of interesting properties. It is not hard to show that $G'$ consists of a collection of chordless cycles of length $\ge$   4. By a “chordless cycle” we mean a sequence of vertices $<y_1, y_2, \ldots$ $y_n, y_1>$, where $\{y_i, y_{i+1}\} \in E$, $1 \le i \le n-1$, and where $\{y_{i}, y_{i+k}\} \not \in E$ for $k \ge 2$. Of course, we also require $\{y_n, y_1\} \in E$. It’s a “pearl necklace” without cross connections. Because there can be no cross connecting edges of the form $\{y_i, y_{i+k}\}, k \ge 2$, each cycle $C_{\alpha }$, when considered strictly as a “set” of vertices, is a member of a Sperner set [7]. That is, given a ground set V, for all cycles $C_{\alpha }, C_{\beta } \subset V$, $C_{\alpha } \not \subseteq C_{\beta }$. Besides the interesting combinatorics associated with Sperner sets, this permits various computer algorithms to process irreducible graphs solely as set systems without regard to individual edges. This reduction, $G.{\omega }$, of G to an irreducible graph $G'$ has a number of other intriguing properties [16], such as the preservation of paths, of the graph “centers”, but this is not relevant to this paper.

2.2 Expansion, ${\varepsilon }$

It is fairly easy to define the treatment of edges in a function, such as ${\omega }$, that contracts a graph. If , then all edges $\{y, z\}$ such that $y \in Y, z \in Y.{\eta }$ can be deleted. Expanding a graph, , presents more problems. How is $Y'$ to be embedded in $G'$? One option is to employ an expansion grammar ${\varepsilon }$, such as explored in [13]. Expansion grammars are quite different from phrase-structured grammars in which a non-terminal symbol A is expanded with a rewrite rule of the form $A \rightarrow \sigma$ [19]. The problematic aspect of a phase-structured grammar, explored by Ehrig in [6], is how will the right side $\sigma$ of the rewrite rule be embedded in the growing, non-linear structure.

In an expansion grammar, a subset Y of a growing structure is first identified to be the neighborhood of a new element $p'$. That is $\{p'\}.{\eta }' = Y \subseteq V$ in the rewritten structure. More precisely, ${\varepsilon }_i:(V_i, E_i) \rightarrow (V_{i+1}, E_{i+1})$ where $V_{i+1} = V_i \cup \{p'_i\}$, $E_{i+1} = E_i \cup \{\{y_k, p'_i\}, y_k \in Y \subset V_i\}$ and .

The set-valued procedure, ${\varepsilon }$ can then be defined as a graph grammar with any set of specified rewrite rules, or productions. The following example of an expansion grammar is also given in [13]. Consider the rewrite rule r1 below,

$$\begin{aligned} r1: K_n {{\ {\mathop {\longrightarrow }\limits ^{\varepsilon }}\ }}: p' \quad n \ge 1 \end{aligned}$$

which specifies that any complete subgraph, $K_n$, (or clique) of order n in V can serve as the neighborhood of a new point $p'$ provided $n \ge 1$.⁶ Every point in $K_n'$ will be adjacent to $p'$ in $G'$. Call the application of a rewrite rule a step, ${\varepsilon }_i$, in the process ${\varepsilon }$. It is a well defined operation in which . The left side of the rewrite rule defines its embedding neighborhood. The right-most part defines any conditions on this neighborhood.

Fig. 3.

A sequence of neighborhood expansions generating chordal graphs

Application of r1 is illustrated in Fig. 3. Each expanded neighborhood (in this case clique) has been made bold; and the expansion point, $p'$, circled. The dashed edges indicate those links which define the clique as the neighborhood of the expansion point $p'$. It is not hard to see that any graph generated in this fashion must be chordal.⁷

A more relaxed version of the rewrite rule r1 above, will allow Y, the new neighborhood of $p'$, to be any subset of the neighborhood of an existing vertex $y \in V_i$. Specified as a rewrite rule r2 it is,

$$\begin{aligned} r2: Y {{\ {\mathop {\longrightarrow }\limits ^{\varepsilon }}\ }}: p' \ \ \exists y \in V_i, Y \subseteq \{y\}.{\eta }\end{aligned}$$

Fig. 4 shows one possible application of this expansion grammar ${\varepsilon }$ to the graph $G'$ of Fig. 2. Here, the rewrite rule r2 has been used 8 times, to create $a, b, \dots h$. The vertex d is generated by r2 using the neighborhood $\{17\}.{\eta }= \{15, 17,18\}= \{d\}.{\eta }'$. The new vertex c was attached to $\{1, 15\} \subset \{1, 2, 3, 15\} = \{1\}.{\eta }$; and f was later attached to $\{1, c\} \subset \{1\}.{\eta }$.

Fig. 4.

A member of $G'.{\varepsilon }$ where $G' = G.{\omega }$ in Fig. 2.

Fig. 5.

Another graph $G'.{\varepsilon }$ in $G'.{\omega }^{-1}$.

2.3 The Inverse Set, ${\omega }^{-1}$

The two procedures ${\omega }$ and ${\varepsilon }$ are intertwined. The requirement in the second rewrite rule r2 that $\{p'\}.{\eta }= Y \subseteq \{y\}.{\eta }$ ensures that if ${\omega }$ is applied to $G'.{\varepsilon }$, $p'$ will at some iteration be subsumed by y. Thus, if $G'$ is irreducible, $G'.{\varepsilon }.{\omega }= G'$ This characteristic is evident in Fig. 4 where b will be subsumed by 3, etc. It is also true for the graph $G'.{\varepsilon }$ of Fig. 5 as well. Consequently, ${\omega }$ is a right-inverse of ${\varepsilon }$ over the subspace of irreducible undirected graphs. The inverse of ${\omega }$, that is $G.{\omega }.{\omega }^{-1}$ is the collection of all undirected graphs $\{G_k\}$ such that $G_k.{\omega }= G' = G.{\omega }$. Each invocation of the non-deterministic procedure ${\varepsilon }$ is single-valued; but ${\varepsilon }$ is not a function. The execution of ${\varepsilon }$ will yield a graph, $G_k \in G.{\omega }.{\omega }^{-1}$.

In the rewrite rule r2 the choice of $y \in V_i$ and the choice of $Y \subseteq \{y_i\}.{\eta }$ are completely arbitrary. Given different choices for y and Y yields Fig. 5 which seems to be a far more interesting graph. Both Figs. 4 and 5 were generated by a computer version of ${\varepsilon }$ using a random number generator.

This is not the only category of undirected graphs, but it is a promising one [17]. Unfortunately, undirected graphs, and mappings between such graphs, have little of the regular structure seen in the different abstract algebras that gave rise to the categorical approach of [1, 10, 18], or that of [2] which was applied to general closure operators. Yet, the rudiments are there, as this short treatise shows. In the early 70’s, Hartmut Ehrig urged us to view graph grammars and graph manipulation through a categorical lens. He was ahead of his time.