Graph Trans-morphism Algorithm 

Get Complete Project Material File(s) Now! »

Chapter 2 Graph Theory

Introduction

Graphs are a well known and well researched branch of mathematics with applications in many areas. Graphs are used to model systems and the relationships between system parts. Graphs are particularly well suited for systems that require the modeling of rules [Andries et al., 1999] and require a structure of the system to be maintained [Heckel, 2006], conceptually, behaviourally or both.
The graph theory presented in this chapter is by no means complete. It provides an overview of the fundamentals of graphs and basic denitions so that the topics can be discussed or expanded on in later chapters. The chapter is divided into three sections devoted to discussing types, matching and the transformation of graphs. Graph types, Section 2.2, introduces the notation to be used in the dissertation when specifying graphs. Section 2.3 discusses graph matching techniques. These techniques fall into two categories, they are either exact or inexact. The exact matching technique that solves the subgraph isomorphism problem is of particular interest later in the thesis and therefore the denition of a subgraph isomorphism is discussed. A denition and example for graph transformation is given in Section 2.4.

Graph types

All graphs can be seen as having vertices and edges connecting the vertices. How these vertices and edges are specied dictate the properties the dened graphs have. In this section, three basic graph types are presented, beginning with the most general form of a graph, the undirected graph where edges are bidirectional. More specialised graph types, with directional edges are also dened, namely the directed graph and the directed acyclic graph.

Undirected graph

Many mathematics-based denitions for (undirected) graphs have been published. These graph denitions vary in detail, but each denition essentially relies on the fact that a graph comprises of a set of vertices, a set of edges and a way of specifying the edges between the vertices. As illustration, two denitions are presented with a publication span of just under 30 years between them. The rst denition, reproduced in Denition 2.1, was published in 1976 by Bondy and Murty. The denition views a graph as a 3-tuple (or triple). The rst element of the triple represents a set of vertices. According to the denition, a graph is dened by at least 1 vertex. The second triple element represents the set of edges. Each edge is dened using the third element of the triple, which associates an edge with a pair of vertices. According to the denition, this is an unordered pair. However, since a pair is normally regarded as ordered, it would probably be better to regard the incidence function as mapping to a set of cardinality 2.

Denition 2.1 (Graph denition 1 – Bondy and Murty, 1976)

A graph G is dened as an ordered triple (V (G);E(G); G), where:
i V (G) is a non-empty set of vertices
ii E(G) is a set disjoint from V (G) of edges, and
iii G is an incidence function that associates with each edge of G an unordered pair of vertices of G.
An example of a specication of a graph using the denition presented in Denition 2.1 is given by:
V (G) = fa; b; c; d; e; fg
E(G) = fe1; e2; e3; e4; e5; e6; e7; e8g
(e1) = (a; b);
(e2) = (a; c);
(e3) = (a; f);
(e4) = (b; c);
(e5) = (c; d);
(e6) = (d; e);
(e7) = (b; f);
(e8) = (b; e)
From the specication, it should be noted that the denition implicitly labels the edges using the elements of the set E(G) to represent the labels The label for the edge between vertices c and d, is e5. The second denition of a graph, dened by Diestel in his book on Graph Theory, is reproduced in Denition 2.2. In this case a graph is dened as a pair comprising of a set of vertices and a set of edges. Each element in the set of edges is a subset of V comprising of two elements. In this denition it is possible to have an empty set of vertices, which implies an empty set of edges.

Denition 2.2 (Graph denition 2 – Diestel, 2005)

A graph G is dened as a pair of the form (V;E), where V is a set of vertices of graph G and E a set of edges. The set E is a 2-element subset of V (E [V ]2). It is further assumed that V \ E = ;.
The assumption that V \E = ; ensures that the graph does not contain loops. A loop is dened by Denition 2.3. To illustrate the need for this assumption, consider the following specication for a graph that adheres to this denition:
V = fa; b; cg
E = ffa; bg; fb; bg; fb; cgg
The edge fb; bg 2 E, according to set theory, will reduce to fbg 2 E, which is in V resulting in V \ E = fbg.

Denition 2.3 (Loop)

A loop is an edge that connects a vertex to itself.
An example of a specication of a graph using the denition presented in Denition 2.2 that results in the same graph as the specication given for Denition 2.1 is given by:
V = fa; b; c; d; e; fg
E = ffa; bg; fa; cg; fa; fg; fb; cg; fc; dg;
fd; eg; fb; fg; fb; egg
From the example above, it can be seen that the denition does not make provision for labeling of the edges. Both denitions presented by Denition 2.1 and 2.2 have a similar structure. Both dene a set of vertices and a set of edges and in both the set of edges is dened in terms of a function that is applied to the set of vertices. Denition 2.1 allows for loops, but not an empty graph. Denition 2.2 does allow for a graph to be dened as empty, it does not allow for loops or the explicit labeling of edges. For the thesis, a graph is required to have the following properties:
A graph can be empty implying that there are no vertices for the graph, yet the graph is dened to exist. This property is necessary for the discussion of the algorithm proposed in Chapter 5.
A graph edge must be able to carry a label along with the possibility of additional meta-data associated with the edge.
The graph does not contain loops.
A denition, which takes the above properties into account for an undirected graph, is given by Denition 2.4 using a notation that represents operations which take parameters. These operations are analogous to functions in computer programming languages. Assigning the result of an operation to a variable indicates that the execution of the operation will give a resultant value that will be assigned to the variable. The general form of an operation is given by: var = operation(parameterlist)

Denition 2.4 (Undirected graph)

A graph, dened by G = G(V;E), comprises of:
i V = V (G), a set of elements, called vertices of G.
ii E = E(G), a set of edge pairs of G. Each edge pair, (E;L), comprises
an edge (E) and a label (L). E is a two element subset of V (i.e. E = fv1; v2g, where v1 6= v2 and v1; v2 2 V ) and L is an n-tuple of which the rst element enumerates the label (label; :::) of the corresponding edge.
Denition 2.4 satises all the desired properties,
V = ; is valid. It follows that if V = ; then E = ;.
Edge pairs in E incorporate an n-tuple representation for a label.
The denition of the edge as a two element subset of V ensures that the elements in the subset cannot be the same with v1 6= v2, otherwise it would reduce the subset to one element making it invalid.
A graph dened using Denition 2.4 is represented by two sets, a set of vertices (V ), and a set of edges (E). Each pair in E comprises of a set of two elements of V and an n-tuple representing the label. The following is a textual representation of a graph G comprising of 5 vertices and 8 edges that represents the same graph as for the specications used to illustrate Denitions 2.1 and 2.2.

Directed graph

A directed graph (also referred to as a digraph) G, is a graph in which the edges have direction. Each edge begins at a source vertex and ends at a destination vertex [Diestel, 2005]. For there to be an edge in the opposite direction it needs to be specically dened as an edge of the graph. It is permissible to have an edge in the opposite direction as well so that the source of one edge is the destination of the other, and vice versa. A formal denition, in the notation of the Denition 2.4 of a graph, is given by Denition 2.5.
Identical graphs will have the same diagrammatic representation [Bondy and Murty, 1976]. Non-identical graphs may have the same diagrammatic representation and may be found to be isomorphic if the graph matching property of the number of vertices of the two graphs are the same and there exists a bijective mapping function F.
When the graph matching property of j VA j=j VB j does not hold, no graph isomorphism can be determined and the problem changes from nding exact matches between vertices to nding the best match between vertices. These problems belong to the class of problems known as inexact graph matching. In such cases, a non-bijective relationship between GA and GB is sought [Bengoetxea, 2002], also referred to as a graph homomorphism. In the sections that follow, the graph matching techniques are discussed in more detail. The graph comparing algorithm presented in Chapter 5 makes use of the notions presented by these techniques for building a subgraph isomorphism.

Graph isomorphism

A graph isomorphism (iso – equal, morphism – shape), which holds for both undirected and directed graphs, is a 1-to-1 mapping of the vertices in the graph GA onto the vertices in the graph GB such that the edges of the vertices are preserved. The denition for exact graph matching (Denition 2.9) is equivalent to the denition of a graph isomorphism [Bondy and Murty, 1976; Diestel, 2005; Bang- Jensen and Gutin, 2007].
The notation used to denote that graph GA is isomorphic to graph GB is given by GA =GB.
Consider the following two textual representations and their respective graphical representations (given in Figures 2.4 and 2.5) of graphs GA and GB.
VA = fa; b; c; d; eg
EA = f(fa; bg; ()); (fb; cg; ()); (fc; dg; ()); (fd; ag; ()); (fa; eg; (); (fe; dg; ())g
VB = fg; h; i; j; kg
EB = f(fk; gg; ()); (fg; hg:()); (fh; ig; ()); (fi; jg; ()); (fj; kg; ()); (fk; ig; ())g
From their respective gures, GA and GB look dierent. By applying Denition 2.9 it can be shown that GA and GB are isomorphic. The rst part of the denition states that the number of vertices in each of the graphs must be equal, GA has 5 vertices and so does GB. The second requirement of the denition requires that some mapping F between the vertices can be found such that the edges of GA are preserved in GB and vice versa. There exists such a mapping, F(a) = i;F(b) = h;F(c) = g;F(d) = k and F(e) = j. The set of edges extracted from GA is given by:
E0 A = ffa; bg; fb; cg; fc; dg; fd; ag; fa; eg; fe; dgg
By applying the mapping F to E0A , the following set of edges result:
E0 B = ffF(a);F(b)g; fF(b);F(c)g; fF(c);F(d)g; fF(d);F(a)g;
fF(a);F(e)g; fF(e);F(d)gg = ffi; hg; fh; gg; fg; kg; fk; ig; fi; jg; fj; kgg
The edges of E0A map directly onto E0B ; therefore GA = GB.
A graph isomorphism therefore compares the structures of graphs. The vertex \names » and labels of the edges are merely used for referral purposes. Subgraphs and graph isomorphisms The denition of a subgraph is given by the Denition 2.11 [Diestel, 2005; Bondy and Murty, 1976].

1 Introduction 
1.1 Research proposal
1.2 Research approach
1.3 Research description
1.4 Signicance of the study
1.5 Scope of the study
1.6 Structure of the document
I Theory 
2 Graph Theory 
2.1 Introduction
2.2 Graph types
2.2.1 Undirected graph
2.2.2 Directed graph
2.2.3 Directed acyclic graph
2.3 Graph matching
2.3.1 Graph isomorphism
2.3.2 Graph homomorphism
2.4 Graph transformation
2.5 Conclusion
3 Complexity Theory 
3.1 Introduction
3.2 Big-O notation
3.3 Decision problems
3.4 Turing machines
3.5 Complexity classes
3.6 Conclusion
4 Implementing Digraphs 
4.1 Introduction
4.2 Implementation techniques
4.3 Problems and algorithms
4.4 Conclusion
5 Graph Trans-morphism Algorithm 
5.1 Introduction
5.2 Terminology
5.3 Algorithm
5.4 Explanation of the algorithm using a toy application
5.5 Conclusion
6 Graph Comparison Framework 
6.1 Introduction
6.2 Framework overview
6.3 Comparison component
6.4 Visualisation component
6.5 Applying the framework to the toy application
6.6 Conclusion
7 Analysis of the Outcomes of T 
7.1 Introduction
7.2 Outcome 1 – Parallel edges
7.3 Outcome 2 – Disjoint digraphs
7.4 Outcome 3 – Empty resultant digraph
7.5 Outcome 4 – Exact copy of the ideal
7.6 Outcome 5 – Subgraph of the ideal
7.7 Conclusion
II Application 
8 Computing Curricula Specications 
8.1 Introduction
8.2 ACM/IEEE Computing Curricula series
8.3 ACM/IEEE curriculum structure
8.4 ACM/IEEE Computer Science Curriculum
8.5 Conclusion
9 University Degree Programme Requirements 
9.1 Introduction
9.2 Qualication structures
9.3 Accreditation structures
9.4 Institutional requirements
9.5 Challenges
9.6 Conclusion
10 Modelling Curricula using Digraphs 
10.1 Introduction
10.2 Curricula volumes as digraphs
10.3 Real-word curricula as digraphs
10.4 Capturing topic data
10.5 Modelling equivalences
10.6 Improving representations
10.7 Conclusion
11 Application of the Framework to Computing Curricula 
11.1 Introduction
11.2 Scenario 1: Comparing the core aspects of the curricula volumes
11.3 Scenario 2: Details regarding the Human Computer Interaction KA
11.4 Scenario 3: Application to a real-world curriculum
11.5 Conclusion
III Future Work and Conclusion 
12 Future Work
12.1 Introduction
12.2 Digraph related projects
12.3 Knowledge representations
12.4 Framework extensions
12.5 Computer Science curriculum development
12.6 Conclusion
13 Conclusion 
13.1 Attainment of objectives
13.2 Summary of contributions
13.3 Suggestions for applications
Bibliography 
IV Appendices
GET THE COMPLETE PROJECT