Graph Theory

Question 1

Who is the birth of graph theory attributed to?

Answer 1

Euler and the Seven Bridges of Konigsberg problem

Question 2

Examples of real world problems formulated as graphs

Answer 2

• What is the fastest way to get from city A to city B? or
• What is the cheapest way to get from city A to city B?
• Are all the circuits in a computer connected?
• Social Connections

Question 3

What is a graph?

Answer 3

• A graph is a collection of vertices (nodes) and edges (arcs)
• G = (V,E)
• Vertices (V) are objects that have properties associated with them
• Edges (E) normally do not have properties (values) but they may have.
• Graphs that have valued edges are called weighted graphs

Question 4

Where might the shape of the graph matter?

Answer 4

For instance, if we’re representing cities as they appear in the map we may
not want to change the shape of the graph
• We may want a more realistic representation for the cities’ locations.

Question 5

What is a graph path?

Answer 5

A path from node A to node B in a graph is a list of nodes where successive nodes are connected in the graph

Question 6

What is a simple path?

Answer 6

• A simple path is a path in which no node is repeated

Question 7

What is a cycle?

Answer 7

A cycle is a path that is simple except that the first and the last nodes are the same.
It is a path from a node back to itself.

Question 8

Difference between a directed and undirected graph

Answer 8

• A connected (undirected) graph with no cycles is called a tree

Question 9

What is a spanning graph?

Answer 9

A spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G, with minimum possible number of edges.

Question 10

How many edges can be in a graph?

Answer 10

• The number of edges in a graph can range from 0 (zero) to V(V-1)/2.

V = Vertices

Question 11

What is a sparse graph?

Answer 11

• We call a sparse graph a graph in which E is much less than V2
• In general we say that in a sparse graph E = O(V)

Question 12

What is a dense graph?

Answer 12

We call a dense graph one in which E is close to V2

• Or we say that in a dense graph E = Θ(V2)

Question 13

What is a complete graph?

Answer 13

• We call a complete graph a graph in which E is exactly V(V-1)/2
• A complete graph with k nodes is also called a k-clique.

Question 14

What is an adjacency list?

Answer 14

A way to represent a graph (usually sparse).
Consists of an array, adj, of all nodes in the graph.
For each node, i, adj[i] is a list of all other nodes i is connected to.

Question 15

What is an adjacency matrix?

Answer 15

Preferred when representing dense graphs.
i x i matrix, where there are 1s between connected nodes.
Always symmetrical in undirected graphs.

Question 16

Breadth first search

Answer 16

Practise this (its easy)
Graph search algorithm, results in a tree of searched nodes. Useful for algorithms like Dijkstra’s algorithm.
Uses a queue.

Question 17

Depth first search

Answer 17

Graph search algorithm, follows a node until it has no unexplored child nodes, and then backtracks.
Uses a stack.

Question 18

Minimum spanning tree

Answer 18

Spanning tree for a weighted graph such that the total weight of each edge is minimum. Found using a priority queue DFS.

Question 19

Dijkstra’s Algorithm

Answer 19

Priority queue of the cheapest paths from the start node to each node.

Question 20

What happens if 2 weights are the same in dijkstra’s algorithm?

Answer 20

Longer paths are rejected in favour of shorter paths (when the weight of the paths are the same)