What are the properties of a Graph?

If you are just starting out with Graphs, you may want to read the first article What is a Graph Data Structure?. This article focuses on the properties of a graph. They include whether a graph is directed or undirected, does it have multiple edges, and whether or not it has loops. Let's understand what these properties are with examples.

A graph is undirected when it connects either one or two vertices. All of the graphs below are undirected graphs. The edge connecting the vertices do not indicate any order, start or end.

Figure 1.a represents an undirected phone network graph. An edge between two phone numbers exists if there is a call communication between the two. But the graph does not represent who called whom.

Figure 2.a represents that Amy and Dave are friends but in no particular order.

Figure 3.a represents a flight route graph containing undirected edges between Delhi - SFO and SFO - NYC. An edge exists if there is a flight route between the pair of cities represented as vertices.

To understand what a Directed graph is, let's try to modify the examples we have seen so far and answer slightly different questions. What if we want to

1. Create a phone network graph that model calls between phone numbers in a network. The graph should represent which phone number initiated the call to which other phone number in the network.

We can re-construct the phone network graph (shown below) with directed edges between the phone numbers represented as vertices.

A directed edge from 123-001 to 323-006 indicates that there exists a call communication between the two but most importantly it also indicates that call initiated from 123-001 to 323-006.

2. We need a graph that represents the influence of one person on another.

We can re-construct the social graph (shown below) and introduce directed edges between the people represented as vertices.

A directed edge from vertex "a" to vertex "b" exists when the person represented by vertex "a" can influence the person represented by vertex "b". So, a directed edge from Amy to Dave represents that Amy can influence Dave but not vice-versa. An undirected graph is not capable of providing this information.

3. We need a graph representing the flights from one city to another.

Flight route graph (shown below) can be re-constructed with directed edges to represent this problem.

In this graph, cities are vertices and a directed edge from Delhi to SFO indicates that there is a flight departing from Delhi to San Francisco.

A graph is said to be directed when it contains edges connecting an ordered pair of vertices such that an edge starts from a vertex and ends at a vertex. Here ordered means there is a strict ordering between vertices indicating where the edge starts and where it ends.

As soon as we introduce directed edges in the graph, we can answer different kinds of questions. For example:

• How many calls were made from 123-001?

• Which phone numbers made a call to 323-006?

• Is there a flight from Delhi to SFO and SFO to Delhi?

• Which city has most flights coming in?

• Is Kim influenced by anyone?

• Who can be influenced most?

A graph can have more than one edge connecting the same pair of vertices. This kind of graph is known to have multiple edges.

Multiple Edges in a directed graph lets us discover even more information. From the above illustration you could easily observe

1. There were two phone calls initiated from 123-001 to 456-002.

2. There were three incoming calls to the phone number 456-002.

Though we only looked at the directed graph in this case, multiple edges connecting the same pair of vertices may also exist in an undirected graph as well, as depicted in the figure below.

A graph is said to have a loop if it contains an edge that starts and ends at the same vertex.

The above figure illustrates a loop in a directed graph. It may not make sense that there is a loop at the New York City representing a flight that starts from NYC and lands at NYC. However this loop is a perfect example of flight tours (for sightseeing) that takes off and lands at NYC.

Even undirected graphs can have loops as shown below. A loop at vertex representing NYC in this case represents a flight route that exists on NYC vertex.