A graph consists of a set of nodes or vertices together with a set of edges or arcs where each edge joins two vertices.
graph is a data structure that consists of the following two components:
1. A finite set of vertices also called as nodes.
2. 2. A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered because (u, v) is not the same as (v, u) in case of a directed graph(di-graph). The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v.
Representation of Graph
1. Adjacent graph
In a graph, two vertices are said to be adjacent, if there is an edge between the two vertices. Here, the adjacency of vertices is maintained by the single edge that is connecting those two vertices. In a graph, two edges are said to be adjacent, if there is a common vertex between the two edges.
Types of Graph:
•Finite Graphs: A graph is said to be finite if it has finite number of vertices and finite number of edges.
•Infinite Graph: A graph is said to be infinite if it has infinite number of vertices as well as infinite number of edges.
•Trivial Graph: A graph is said to be trivial if a finite graph contains only one vertex and no edge.
•Simple Graph: A simple graph is a graph which does not contains more than one edge between the pair of vertices. A simple railway tracks connecting different cities is an example of simple graph.
•Multi Graph: Any graph which contain some parallel edges but doesn’t contain any self-loop is called multi graph. For example A Road Map.
~~Parallel Edges: If two vertices are connected with more than one edge than such edges are called parallel edges that is many roots but one destination.
~~Loop: An edge of a graph which join a vertex to itself is called loop or a self-loop.
•Null Graph: A graph of order n and size zero that is a graph which contain n number of vertices but do not contain any edge.
Application of Graphs:
•Computer Science: In computer science, graph is used to represent networks of communication, data organization, computational devices etc.
•Physics and Chemistry: Graph theory is also used to study molecules in chemistry and physics.
•Social Science: Graph theory is also widely used in sociology.
•Mathematics: In this, graphs are useful in geometry and certain parts of topology such as knot theory.
•Biology: Graph theory is useful in biology and conservation efforts
