Although this assignment doesn’t technically require any ‘development’ in terms

Question

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:

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:

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.

Explanation / Answer

v={1,2,3,4,5,6,7,8}

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

Acyclic :this graph is acyclic because there is no cycle in the graph. if there is edge (4,2) then there will be cycle now the graph is acyclic.

Directed or undirected: this graph is directed. In this edges point in a direction then graph is directed. otherewise undirected. in undirected graph the edge can take from any node.

example: (1,3)(3,1)

connected graph: this graph is not connected because there is no path from node 2 to node1

in connected graph there must be a path from one node to another node.

simple graph because there is no self loop or multiple edge

example: if there is edge from node 1 to node 1 then it is self loop if there is edge from node1 to node 2 and node 2 to node1 then it called multiple edge.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.