Graph Theory is a very important concept in mathematics and computer science. A lot of algorithms are based on graphs. The graph is a non-linear data structure, though it look like a tree, it is not the same. A graph is made of nodes and edges. We are now ready to define graphs.
Definition 1: A graph denoted as G = (V, E) consists of V, a non-empty set of vertices or nodes and E, a set of edges. The edges have one or two endpoints associated with it.
Definition 2: A graph with infinite edges or vertices is called Infinite graph.
Definition 3: A graph with finite edges and finite number of nodes is called Finite graph.
Definition 4: A graph in which
- each edge connects two different vertices
- and all edges connect different vertices
is called a Simple graph.
In the above figure, each edge connects two different pair and its not repeated again.
Definition 5: A graph containing at least one pair of vertices, {u, v} that have multiple edges is called a Multi-graph.
In the above multi-graph, there are three edges between the node pair, {B,D}. So, we can say that the node pair, {B,D} has edge multiplicity of 3.
Definition 6: A graph that allows loops and possibly a multi-graph is called a Pseudo-graph.
Directed Graphs
You can check the above graphs, there are no direction to the edges. Such a graph is called a Undirected graph. Now, you will learn about another type of graph called a Directed graph.
Definition 7: A Directed graph (Digraph) (V,E) consists of a non-empty set of vertices V and a set of directed edges E. Each directed edge is associated with an ordered pair of vertices.
Suppose there is an ordered pair of vertices, {u, v} then the directed edge starts at u and end at v.
Definition 8: A directed edge graph that has no loops and has no multiple directed edges, it is called a Simple directed graph.
The above figure show that all the node pairs have directed edges. Such a graph is called a Simple Directed Graph. Directed graphs that have multiple directed edges from a vertex to a second vertex are called Directed Multi-graphs. The node pair with multiple directed edges has a multiplicity of m, where m equals number of edges.