Compare the Difference Between Similar Terms

Difference Between

Home / Technology / IT / Programming / Difference Between Directed and Undirected Graph

Difference Between Directed and Undirected Graph

May 26, 2011 Posted by Indika

Directed vs Undirected Graph

A graph is a mathematical structure that is made up of set of vertices and edges. A graph represents a set of objects (represented by vertices) that are connected through some links (represented by edges). Using mathematical notations, 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 the edges that connect the vertices. In a directed graph there is a direction associated with the edges that connect the vertices.

Undirected Graph

As mentioned earlier, an undirected graph is a graph in which there is no direction in the edges that link the vertices in the graph. Figure 1 depicts an undirected graph with set of vertices V= {V1, V2, V3}. Set of edges in the above graph can be written as V= {(V1, V2), (V2, V3), (V1, V3)}. It can be also noted that there is nothing preventing writing the set of edges as V= {(V2, V1), (V3, V2), (V3, V1)} since the edges do not have a direction. Therefore edges in an undirected graph are not ordered 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. The cities can be represented by the vertices in the graph and the edges represent the two way roads that connect the cities.

Directed Graph

A directed graph is a graph in which the edges in the graph that link the vertices have a direction. Figure 2 depicts a directed graph with set of vertices V= {V1, V2, V3}. Set of edges in the above graph can be written as V= {(V1, V2), (V2, V3), (V1, V3)}. Edges in an undirected graph are ordered pairs. Formally, edge e in a directed graph can be represented by the ordered pair e = (x, y) where x is the vertex that is called the origin, source or the initial point of the edge e, and vertex y is called the terminus, terminating vertex or terminal point. For example, a road network that connects a set of cities using one way roads can be represented using an undirected graph. The cities can be represented by the vertices in the graph and the directed edges represent the roads that connect the cities considering the direction that the traffic flows in the road.

What is the difference between Directed Graph and Undirected Graph?

In a directed graph an edge is an ordered pair, where the ordered pair represents the direction of the edge that links 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 each node in an undirected graph is equal but this is not true for a directed graph. When using a matrix to represent an undirected graph, the matrix always becomes a symmetric graph, but this is not true for a directed graphs. An undirected graph can be converted to a directed graph by replacing each edge with two directed edges going in opposite direction. However, it is not possible to convert a directed graph to an undirected graph.

Related posts:

Difference Between Graph and Tree Difference between Java and J2EE Difference Between Integer and Pointer Difference Between Java and C language Difference Between Hashtable and Hashmap

Filed Under: Programming Tagged With: directed graph, edges, graph, ordered pair, origin, source, symmetric graph, terminus, undirected graph, unordered pair, use of undirected graph, vertices

About the Author: Indika

Indika, BSc.Eng, MSECE Computer Engineering, PhD. Computer Science, is an Assistant Professor and has research interests in the areas of Bioinformatics, Computational Biology, and Biomedical Natural Language Processing.

Comments

  1. Ahmad Waseem Ghauri says

    June 19, 2012 at 11:36 am

    Thank you, this helped alot. 🙂

    Reply
  2. Terry Nduta says

    July 20, 2013 at 8:01 am

    Thanks a bunch. This was very helpful

    Reply
  3. Shebi K Shebu says

    October 28, 2013 at 8:37 am

    THANKS..

    Reply
  4. james says

    February 23, 2016 at 10:03 am

    Thanks.
    Is this a typo?: “Edges in an undirected graph are ordered pairs.”

    Reply

Leave a Reply Cancel reply

Request Article

Featured Posts

Difference Between Coronavirus and Cold Symptoms

Difference Between Coronavirus and Cold Symptoms

Difference Between Coronavirus and SARS

Difference Between Coronavirus and SARS

Difference Between Coronavirus and Influenza

Difference Between Coronavirus and Influenza

Difference Between Coronavirus and Covid 19

Difference Between Coronavirus and Covid 19

You May Like

Difference Between Hydroponics and Aeroponics

Difference Between Hydroponics and Aeroponics

Difference Between Load and Stress Testing

Difference Between Cover Letter and Covering Letter

Difference Between Group 1 and Group 2 Elements

Difference Between Group 1 and Group 2 Elements

Difference Between Fullmetal Alchemist Brotherhood and Fullmetal Alchemist

Latest Posts

  • Difference Between Ising and Heisenberg Model
  • Difference Between E and N Cadherin
  • Difference Between Camphor and Menthol
  • Difference Between Aminocaproic Acid and Tranexamic Acid
  • Difference Between Nitronium Nitrosonium and Nitrosyl
  • Difference Between Trichloroacetic Acid and Trifluoroacetic Acid
  • Home
  • Vacancies
  • About
  • Request Article
  • Contact Us

Copyright © 2010-2018 Difference Between. All rights reserved. Terms of Use and Privacy Policy: Legal.