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