Directed Graphs

Degree of Vertex

The degree of vertex is the total number of vertices in the graph minus 1 or we can say that the number of vertices adjacent to a vertex V is the degree of vertex.

Degree of vertex can be considered under two cases of graphs:

  • Directed Graph
  • Undirected Graph

Directed Graph

A directed graph or digraph is a pair (V, E), where V is the vertex set and E is the set of vertex pairs as in “usual” graphs. The graph in which each vertex has its indegree and outdegree is known as directed graph.

Indegree of vertex V is the number of edges which are coming towards the vertex V.

Outdegree of vertex V is the number of edges which are going away from the vertex V.

For example :

Indegree of (a) -1
Outdegree of (a) – 2

Undirected Graph

The graph in which there is no directed edges is known as undirected graph.

For example:

deg(a) = 2 there are 2 edges meeting at ‘a’
deg(b) = 3 there are 3 edges meeting at ‘b’
deg(d) = 2 there are 2 edges meeting at ‘d’

Types of directed graph

  1. Symmetric directed graphs: The graph in which all the edges are bidirected is called as symmetric directed graph.
  2. Simple directed graph: The directed graph that is without loops is called as simple directed graph.
  3. Loop directed graph: The directed graph that has loops is called as loop directed graph or loop digraph.
  4. Complete directed graph: When each pair of vertices of the simple directed graph is joined by a symmetric pair of directed arrows, this graph is called as complete directed graph.
  5. Oriented graphs: The directed graph that has no bidirected edges is called as oriented graph.
  6. Weighted directed graph: The directed graph in which weight is assigned to the directed arrows is called as weighted graph.

For example:

Flow networks: These are the weighted graphs in which the two nodes are differentiated as source and sink.

Rooted directed graph: These are the directed graphs in which vertex is distinguished as root.

Signal flow graphs: The directed graph in which system variable is represented by nodes and connection between pairs and nodes is represented by branches are called as signal flow graphs.

Leave a Comment