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.
Thank you, this helped alot. 🙂
Thanks a bunch. This was very helpful
THANKS..
Thanks.
Is this a typo?: “Edges in an undirected graph are ordered pairs.”