# Graph Flashcards

1
Q

What is a real-world example of a Graph?

A

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

2
Q

What is a formal definition of a Graph?

A

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.

3
Q

What is the difference between a Tree and a Graph.

A

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.

4
Q

How are the vertices represented notationally?

A

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

5
Q

How are Edges represented notationally?

A

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.

6
Q

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

A

They are considered ADJACENT to each other.

7
Q

What is an UNDIRECTED Graph?

A

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

8
Q

What are two examples of an UNDIRECTED Graph?

A
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.
9
Q

What is an DIRECTED Graph?

A

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

10
Q

What is an example of an DIRECTED Graph?

A

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.

11
Q

Can a DIRECTED Graph’s Edges go both ways?

A

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

12
Q

Define a CYCLIC Graph?

A

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

13
Q

Are all UNDIRECTED Graphs CYCLICAL?

A

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

14
Q

Define an ACYCLIC Graph?

A

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

15
Q

What is a WEIGHTED Graph?

A

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.

16
Q

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

A

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.

17
Q

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?

A
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.
18
Q

Bipartite graphs (digraphs)

A

A graph G is bipartite if V(G) can be partitioned into two nonempty disjoint subsets V0, V1 such that each edge of G has one endpoint in V0 and one in V1.
[Similar for digraphs.]

19
Q

k-colorable graphs

A

Let k be a positive integer. A graph G has a k-coloring if V(G) can be partitioned into k nonempty disjoint subsets such that each edge of G joins two vertices in different subsets (colors)

20
Q

What is the girth of a graph?

A

the length of the shortest cycle is called the girth of the graph.
If the graph has no cycles then the girth is undefined but may be viewed as +∞

21
Q

What is the diameter of a digraph?

A

maximum distance between any two vertices

diameter: maxu,v∈V [d(u, v)]

22
Q

What is a graph?

A

A graph G = (V, E) is a finite nonempty set V of vertices together with a (possibly empty) set E of unordered pairs of vertices of G called edges

23
Q

What is a digraph?

A

A digraph G = (V, E) is a finite nonempty set V of nodes together with a (possibly empty) set E of ordered pairs of nodes of G called arcs

24
Q

Differentiate among cycle, path, and circuit?

A

Path: A Path is the sequence of adjacent vertices connected by the edges with no restrictions.

Cycle: A Cycle can be defined as the closed path where the initial vertex is identical to the end vertex. Any vertex in the path can not be visited twice

Circuit: A Circuit can be defined as the closed path where the intial vertex is identical to the end vertex. Any vertex may be repeated.

25
Q

Mention the data structures which are used in graph implementation.

A

or the graph implementation, following data structures are used.

In sequential representation, Adjacency matrix is used.