Graph

A graph G,consists of two sets V and E. V is a finite non-empty set of vertices.E is a set of pairs of vertices,these pairs are called as edges V(G) and E(G) will represent the sets of vertices and edges of graph G.

Undirected graph - It is a graph with V vertices and E edges where E edges are undirected.In undirected graph, each edge which is present between the vertices Vi and Vj,is represented by using a pair of round vertices (Vi,Vj).

Directed graph - It is a graph with V vertices and E edges where E edges are directed.In directed graph,if Vi and Vj nodes having an edge.than it is represented by a pair of triangular brackets Vi,Vj.

Simple graph - It is a graph, in which each edge occurs only once.

Multiple graph - It is a graph, in which each edge may occur multiple times.

Complete graph - A graph with maximum possible edges is called as complete graph.

Incident edge - If (V1,V2) is an edge between the vertices V1 and V2, then it is incident on the vertices V1 and V2.

Adjacent Vertices - If (V1,V2) is an edge , then the vertices V1 and V2 are said to be the adjacent vertices.

Path - A path from vertex Vp to Vq in graph G is a sequence of vertices Vp,Vi1,Vi2----Vin,Vq such that (Vp,Vi1),(Vi1,Vi2)----(Vin,Vq) are the edges in E(G).

Path Length - It is the number of edges on it.

Connected Vertices - In an undirected graph G, two vertices V1 and V2 are said to be connected if there is a path in G from V1 to V2

For eg,V1--P--Q--R--S--V2

In a directed graph G, two vertices V1 and V2 are said to be connected if a directed path is there in G from V1 to V2.

Note - The adjacent nodes are always the connected nodes but the connected vertices or nodes may not be the adjacent nodes. This is because the adjacent nodes do not allow a path containing many nodes.

For eg, V1---V2 Adjacent and connected

V1--P--Q--V2 Connected and not adjacent

Connected graph - An undirected graph is said to be connected if for every pair of distinct vertices Vi,Vj in V(G) there is a path from Vi to Vj in G.

Connected component - A connected component or simply a component of a undirected graph is a maximal connected subgraph.

Strongly connected directed graph - A directed graph G is said to be strongly connected if for every pair of distinct vertices Vi,Vj in V(G) there is a directed path from Vi to Vj and also from Vj to Vi.

Vertex degree - The degree of a vertex is the number of edges incident to that vertex.