Skip to content

WA3. Graph Analysis

Statement

Although this assignment doesn’t technically require any ‘development’ in terms of Java programming or programming in any other language, it is development in terms of developing a solution and a data structure. Consider the following picture representation of a graph:

Graph

This graph can be implemented using the following data structure.

  • V = {1, 2, 3, 4}
  • E = { (1, 2), (2, 4), (4, 2) (4, 1)}

Create a data structure to represent the graph detailed in the following picture:

Graph2

As part of your assignment you must also determine (and include as part of the discussion in your assignment) if the graph is:

  • Acyclic or not
  • Directed or undirected
  • Connected or not
  • Simple or not

Please explain all of your answers.

Answer

Introduction

Graph is a data structure that consists of nodes and edges that connect those nodes, and it covers some common data structures like trees. Graphs are useful to represent many real-world problems, such as social networks, maps, and networks (Shaffer, 2011).

Data Structure

The graph can be represented using the following data structure:

V={ 1, 2, 3, 4, 5, 6, 7, 8 }
E={
    (1, 2), (1, 3),
    (2, 3), (2, 4),
    (3, 5),
    (4, 7),
    (5, 4), (5, 6),
    (6, 7),
    (7, 8),
}

Acyclic or not

A cyclic graph is a graph that contains a cycle, which is a path that starts and ends at the same node. The graph is acyclic if it doesn’t contain any cycles.

Although, 2-->3-->5-->4 may seem like a cycle, it is not a cycle because there no path from 4 back to 2. The same goes for 1-->2-->3. Therefore, the graph is acyclic.

Directed or undirected

A directed graph is a graph where the edges have a direction; that is 1-->2 is different from 2-->1. An undirected graph is a graph where 1--2 and 2--1 are the same; hence, it cane traversed in both directions.

The graph is directed because we can see the direction of the arrows in the image.

Connected or not

A graph is connected if there is a path between every pair of nodes; that is, from any node, you can reach any other node. The graph is connected as we see that all the nodes are connected to each other (ignoring the direction of the edges). However, if we consider the direction, then the connection is weak because there is no path from 2-->1 or 3-->1 (Rosen, 2015).

Simple or not

A simple graph is a graph that doesn’t contain any self-loops or multiple edges between the same pair of nodes. The graph is simple as it is not cyclic nor there are multiple edges between the same pair of nodes.

Conclusion

Here is a summary of the graph:

Property Value
Acyclic Yes
Directed Yes
Connected Yes, weakly connected
Simple Yes

References

‌