4.2.4 Graphs

Question 1

Define Graphs.

Answer 1

An abstract data structure consisting of a set of values/nodes connected by a set of edges.

Question 2

Define Abstraction.

Answer 2

The removal of unnecessary detail, reducing the problem to essential features.

Question 3

What is the vertex/node in graph?

Answer 3

The representation of an object on a graph that is capable of being related to other such objects.

Question 4

What is the edge in graph?

Answer 4

A connection that represents a relationship between two nodes.

Question 5

What are the 4 types of graphs?

Answer 5

• weighted
• unweighted
• directed
• undirected

Question 6

What is a weighted graph?

Answer 6

A graph where each edge/arc has an associated value (weight).

Question 7

What is an unweighted graph?

Answer 7

A graph where edges have no values.

Question 8

What is a directed graph?

Answer 8

A graph where the order of the vertices paired in an edge matter. The edges are one way.

Question 9

What is an undirected graph?

Answer 9

A graph where the order of the vertices paired in an edge does not matter. The edges are bidirectional.

Question 10

What are some examples of graphs in real life?

Answer 10

• human networks
• transport networks
• internet and the web
• computer science
• medical research
• project management
• game theory

Question 11

What is an Adjacency List?

Answer 11

A representation of a graph by storing a list of connected nodes to each node.

Question 12

What is an Adjacency Matrix?

Answer 12

A matrix representation of a graph that stores the edges connecting all possible nodes.
Where 1 is connected, and 0 is not connected.

Question 13

Adjacency List VS Adjacency Matrix

Answer 13

List:
- suitable for sparse graphs (little edges)
- less memory required (as only stores data when there is an edge)
- increases processing time (has to be analyzed before adjacencies can be identified)

Matrix:
- suitable for dense graphs (lots of edges)
- more memory required (as stores value for every combination)
- faster processing time (adjacencies can be identified more quickly, matrix is used as a lookup)