Graphs and Graph Models

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

  1. each edge connects two different vertices
  2. and all edges connect different vertices

is called a Simple graph.

A Simple Graph
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.

A Multi-graph
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.

A Directed Multigraph
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.


Rate this post