Umesh Chandra

A graph named G can be defined as ordered set G(V,E) where V(G) represents the set of vertices and E(G) represents the set of Edges which are used to connect these vertices.

If n is the number of vertices, then total number of edges can be calculated with the formula n(n-1)/2

Types of Graphs:

Basically, Graphs are categorized into two types:

• Directed Graph
• Undirected Graph

Undirected Graph

In the above picture, that graph is defined as an Undirected Graph. A graph can be of two types, one is Directed graph and the other one is Undirected graph. Undirected graph means the edges are not associated with the directions with them. Since in the above example the edges of the graph is not associated with any directions, so it is called a Undirected graph. I there exists an edge between A and D then the vertices can be traversed from A to D as well as D to A.

Directed Graph

In a directed graph, edges form an ordered pair, Edges represent a specific path from some vertex A to another vertex B. Node A is called initial Node while B is called Terminal Node.

Example:

Basic Terminologies of the Graph

1) Path

A path can be defined as the sequence of nodes that are followed in order to reach some terminal node V from the initial node U.

2) Closed Path

If Initial node of the graph is same as Terminal node of that graph, then that is called as Closed path. A path will be closed if V₀=V_N.

3) Loop

An edge that is associated with the similar end points can be called as Loop.

4) Cycle

A cycle can be defined as the path which has no repeated edges or vertices except the first and last vertices.

5) Connected Graph

A connected graph is the one in which some path exists between every two vertices (u, v) in V. There are no isolated nodes in connected graph.

6) Complete Graph

A complete graph is the one in which every node is connected with all other nodes.

7) Weighted Graph

Each edge of a graph is assigned with some data such as cost or weight. The weight of an edge e can be given as w(e) which must be a positive (+) value indicating the cost of traversing the edge.

8) Digraph

Digraph is a graph in which each edge of the graph is associated with some direction and the traversing can be done only in the specified direction.

9) Adjacent Nodes

If two nodes A and B are connected via edge e, then the nodes A and B are called as Adjacent nodes or neighbors.

10) Degree of the Node

A degree of the Node is the number of edges that are connected with that Node. A node with degree 0 is called an isolated node