Graph

Question 1

What is a real-world example of a Graph?

Answer 1

Imagine plotting your favourite restaurants on a map and then drawing lines between all those restaurants. That’s basically a graph. Pieces of information (The restaurants) and the Paths that run between them (The lines).

Question 2

What is a formal definition of a Graph?

Answer 2

A Graph is a non-linear Data Structure consisting of Nodes/Vertices and Edges/Paths.

They have a finite set of Nodes(Vertices)
Nodes are connected by the Edges.

Question 3

What is the difference between a Tree and a Graph.

Answer 3

Tree’s have a specific starting point (Root Node) and multiple branches. A Graph still has multiple branches but there is no specified starting point (Multiple starting points). We can begin from any node and traverse to any node. Like in our restaurant example you could start at any restaurant.

Question 4

How are the vertices represented notationally?

Answer 4

E.g. { 1,2,3,4,5,6} Where each value represents a Node.

Question 5

How are Edges represented notationally?

Answer 5

E.g. { (6,4), (4,5), (4,3), (3,2), (5,2), (2,1), (5,1) } These are the EDGE SETS. They represent the connections/paths/edges between the nodes.

Question 6

What is it called when two nodes are connected to each other?

Answer 6

They are considered ADJACENT to each other.

Question 7

What is an UNDIRECTED Graph?

Answer 7

A Graph in which the DIRECTION you traverse the Nodes IS NOT important. This is usually indicated by a lack of arrow.

Question 8

What are two examples of an UNDIRECTED Graph?

Answer 8

1. Our restaurant example. You can travel between restaurants in any direction, even back and forth if you want.
2. Facebook Friendships. Each Edge indicates a Friendship. The friendship goes both ways and the direction is unimportant.

Question 9

What is an DIRECTED Graph?

Answer 9

A Graph in which the DIRECTION you traverse the Nodes IS important. This is usually indicated by arrows representing direction.

Question 10

What is an example of an DIRECTED Graph?

Answer 10

Following someone on Instagram. E.g. I can follow Elon Musk but he doesn’t necessarily follow me back. I will have a one-way arrow edge pointing towards him.

Question 11

Can a DIRECTED Graph’s Edges go both ways?

Answer 11

Yes. E.g. I follow someone on Instagram and they also follow me back.

Question 12

Define a CYCLIC Graph?

Answer 12

A Graph which contains a path from at least one Node back to itself.

Question 13

Are all UNDIRECTED Graphs CYCLICAL?

Answer 13

Yes. The bi-directional nature of Nodes within an UNDIRECTED Graph forms a cycle between any two nodes.

Question 14

Define an ACYCLIC Graph?

Answer 14

A Graph which contains NO PATH from any one Node which leads back in on itself.

Question 15

What is a WEIGHTED Graph?

Answer 15

A Graph whose edges are associated with a NUMERICAL VALUE. This is the COST.
Each weight represents some property of the information you’re trying to convey.

Question 16

For our restaurant example, what would be a good WEIGHT for each EDGE if we wanted to plot a travel route amongst the restaurants?

Answer 16

The Edges’ weight could be the distance between each restaurant (Node/Vertex). This is used in route-mapping software (Google Maps) to calculate the path of LEAST-COST or WEIGHT between Nodes.

Question 17

Directed or undirected, cyclical or acyclical, weighted or unweighted can all be used to form many different variations of Graphs. What are two popular variations and their use cases?

Answer 17

1. Undirected Cyclical Graph with Weighted Edges.
   Dijkstra’s (Dye-kstra) shortest path algorithm.
   This compiles a list of the shortest possible paths from a source vertex to all other Nodes within the Graph. Google Maps, IP Routing, Game Engines for movement.
2. Unweighted Cyclical Graph (Undirected and Directed)
   Used in the follower/friendship system of social media websites.