Directed vs. Undirected Graph

Difference Between Directed and Undirected Graph

A graph is a mathematical structure that consists of all vertices and edges. A graph represents a set of objects (represented by the vertices) that are connected by some links (represented by the edges). Using mathematical notation, a graph can be represented by G, where G = (V, E) and V is the set of vertices and E is the set of edges. In an undirected graph there is no direction associated with edges that connect the vertices. In a directed graph there is a direction associated with edges that connect the vertices.

Undirected graph

As mentioned earlier, undirected graph is a graph in which there is no direction in the edges that connect vertices in the graph. The diagram 1 represents an undirected graph with all vertices V = {V1, V2, V3}. The set of edges in the above graph can be written as V = {(V1, V2) (V2, V3) (V1, V3)}. It can also be noted that there is nothing preventing the writing of all edges as V = {(V2, V1) (V3, V2) (V3, V1)}, since the edges do not have direction. So the banks in an undirected graph are unordered pairs. This is the main characteristic of an undirected graph. Undirected graphs can be used to represent symmetric relationships between objects that are represented by vertices. For example, a two-way road network that connects a set of cities can be represented using an undirected graph. Cities can be represented by the vertices in the graph and the edges represent the two- way roads that connect cities.

Directed Graph

A directed graph is a graph in which edges in the graph that connect the vertices have a direction. The figure 2 shows a directed graph along with all vertices V = {V1, V2, V3}. The set of edges in the above graph can be written as V = {(V1, V2) (V2, V3) (V1, V3)}. The undirected graph edges are not ordered pairs. Properly, the edge e in a directed graph can be represented by the ordered pair e = (x, y) where x is the vertex called origin, source or starting point and the edge e is known as terminus, terminal point  or terminate vertex. For example, a road network that connects a set of cities with one- way roads can be symbolized using an undirected graph. Cities can be represented by the vertices in the graph and directed edges represent the roads that connect cities considering the direction that traffic flows in the road.

What is the difference between the Undirected Graph and Directed Graph?

In a directed graph an edge is an ordered pair, where the ordered pair represents the direction of the edge connecting the two vertices. On the other hand, in an undirected graph, an edge is an unordered pair, since there is no direction associated with an edge. Undirected graphs can be used to represent symmetric relationships between objects. In-degree and out-degree of every node in an undirected graph is equal but it is not true for a directed graph. While using a matrix to represent an undirected graph, the matrix ​​always turns into symmetric graph, but it is not true for directed graphs. Undirected graph can be converted to a directed graph by replacing each edge with two directed edges coming in the opposite direction. However, it is not possible to convert a graph directed graph into undirected one.

 

Category: VS  |  Tags: