# Graph Flashcards

What is a real-world example of a Graph?

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).

What is a formal definition of a Graph?

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.

What is the difference between a Tree and a Graph.

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.

How are the vertices represented notationally?

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

How are Edges represented notationally?

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.

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

They are considered ADJACENT to each other.

What is an UNDIRECTED Graph?

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

What are two examples of an UNDIRECTED Graph?

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

What is an DIRECTED Graph?

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

What is an example of an DIRECTED Graph?

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.

Can a DIRECTED Graph’s Edges go both ways?

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

Define a CYCLIC Graph?

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

Are all UNDIRECTED Graphs CYCLICAL?

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

Define an ACYCLIC Graph?

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

What is a WEIGHTED Graph?

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.