Tuesday, April 19, 2016

Define graphs, directeed graph and trees

Graphs : A graphs denoted G = (V, E), consists of a finite set of vertices V and a set of pairs of n vertices E called edges.

Example : graph is shown in figure-6(a).
Here, V = {1, 2, 3, 4} and E = {(n, m)} | n+m = 4 or n+m = 7}
A path in a graph is a sequence of vertices v1, v2...........vk, k 1, such that

there is an edge (vi, vi+1) for each i, 1<=i<k. The length of the path is k-1. if v1 = vk, the path is a cycle.

Directed graph : A directed graph also denoted G = (V,E), consist of finite set of vertices V and a set of ordered pairs of vertices E called ares. We denote an are from v to w by v w.

Example : A directed graph appears in figure-6(b).

A path is directed graph is a sequence of vertices, v1, v2...........vk, k 1 such that vi, vi+1 is an are for each i, 1<=i<k. We say the path in from v1 to vk

Trees : A tree is a directed graph with the following properties :

1) There is one vertex called the root, that has no predecessors and from which there is a path to every vertex.

2) Each vertex others than the root has exactly one predecessor

3)  THe successors of each vertex are ordered "from the left"