GRAPH THEORY

Graph theory offers important methods for addressing these issues since XML trees and RDF graphs will flow naturally toward graphical evaluation and resolution. In addition, First Order Logics have been successfully represented and evaluated as logic-oriented directed graphs for many years.

Nets can use traditional reliability tools, such as reachability, minimum path sets, and modularization XML uses graphs (trees) to partition, organize, and manipulate data. RDF used directed graphs to represent simple statements of fact.

A graph consists of a non-empty set of points or vertices, and a set of edges that link the vertices together. A simple real-world example of a graph could be your house and your workplace. Where the house and the workplace are the vertices and the road between them is the edge connecting the two vertices. A graph can be either directed or undirected. A directed graph is one in which the direction of any given edge is defined. Conversely, an undirected graph indicates motion in both directions between vertices

Although graphs are usually shown diagrammatically, this is only possible when the number of vertices and edges is reasonably small. Graphs can also be represented in the form of matrices. The major advantage of matrix representation is that the calculation of paths and cycles can easily be performed using well known operations of matrices.

Consider in Figure 1 with directed graph G (with vertices as v1, v2, v3, v4, and v5), and its equivalent adjacency matrix, A, representation (see Figure 12-3).

ADJACENCY MATRIX
An adjacency matrix, A, is defined as follows: Let G be a graph with "n" vertices that are assumed to be ordered from v1 to vn. The n x n matrix A, in which: aij= 1 if there exists a path from vi to vj aij = 0 otherwise is called an adjacency matrix.

PATHS
As shown in the previous example, the existence of an edge between two vertices vi and vj is shown by an entry of 1 in the ith row and jth column of the adjacency matrix. This entry represents a path of length 1 from vi to vj. To compute a path of length 2, the matrix of length 1 must be multiplied by itself, and the product matrix is the matrix representation of path of length 2. To compute a path of length n, the matrix of length 1 must be multiplied by itself to the nth power.

REACHABILITY
Reachability is an important characteristic of a directed logic graph which finds all paths from every node nj, to any node nj within the graph.

Reachability R can be found using the Adjacency Matrix A with V vertices where the ij location will be 0 if there is no path from vertex i to vertex j and one otherwise

       V-1
R = ∑ A^i
      i=1

TREES
RDF constructs graphs without cycles or trees and is thus processed.

REFERENCE:
Developing Semantic Web Services