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.

Advertisements

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.

Advertisements
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.

 

Advertisements

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.