How Monographs Unify Graph Structures

Table of Links

Abstract and 1 Introduction

2 Basic Definitions and Notations

2.1 Sets

2.2 Sequences

2.3 Signatures and Algebras and 2.4 Categories

3 Monographs and their Morphisms

4 Limits and Colimits

5 Drawing Monographs

6 Graph Structures and Typed Monographs

7 Submonographs and Partial Morphisms

8 Algebraic Transformations of Monographs

9 Attributed Typed Monographs

10 Conclusion and References

3 Monographs and their Morphisms

It is easy to see that for any set of monographs there exists a common ordinal for all its members.

Since any ordinal is a set of ordinals, we see that an ordinal α is for a monograph iff this is an α-monograph. Hence all edges of a monograph have finite length iff it is an ω-monograph.

The running example A has no nodes and is therefore not standard. Since Apxq “ x y x then x is adjacent to y and to itself. Similarly, Apyq “ y x y yields that y is adjacent to x and to itself. In this case the adjacency relation is symmetric, but this is not generally the case, e.g., a node is never adjacent to any edge, while edges may be adjacent to nodes.

Definition 3.5 (categories of monographs, functor E). Let Monogr be the category of monographs and their morphisms. Let SMonogr *be its full subcategory of standard monographs. For any set O of ordinals, let O-*Monogr (resp. O-SMonogr) be the full subcategory of O-monographs (resp. standard O-monographs). Let FMonogr be the full subcategory of finite ω-monographs.

Let E be the forgetful functor from Monogr to Sets*, i.e., for every monograph A let EA be the set of edges of A, and for every morphism f : A → B let Ef : EA → EB be the underlying function, usually denoted f.*

There is an obvious similitude between standard t0, 2u-monographs and graphs. It is actually easy to define a functor M : Graphs Ñ t0, 2u-SMonogr by mapping any graph G “ pN, E, s, tq to the monograph MG whose set of edges is the coproduct N `E, and that maps every edge e P E to the sequence of nodes speqtpeq (and of course every node x P N to ε). Similarly graph morphisms are transformed into morphisms of monographs through a coproduct of functions. It is easy to see that M is an equivalence of categories.

It is customary in Algebraic Graph Transformation to call typed graphs the objects of GraphszG, where G is a graph called type graph, see e.g. [2]. We will extend this terminology to monographs and refer to the objects of MonogrzT as the monographs typed by T and T as a type monograph.