Chapter 3

Question 1

What is the difference between a directed and undirected graph?

Answer 1

The order of the nodes being connected matters for directed. i.e an edge from u to v exists but not v to u

Question 2

What is the definition of a path for an undirected graph?

Answer 2

we define a path in an undirected graph G=(V,E) to be a sequence P of nodes v1,v2,…,vk−1,vk with the property that each consecutive pair vi , vi+1 is joined by an edge in G.

Question 3

What is a simple path?

Answer 3

A path is called simple if all its vertices are distinct from oneanother.

Question 4

What is a cycle?

Answer 4

A path with more than 2 nodes where all nodes are distinct except for the first and last node which are the same. i.e it cycles back.

Question 5

What does it mean for an undirected graph to be connected?

Answer 5

We say that an undirected graph is connected if, for every pair of nodes u and v, there is a path from u to v.

Question 6

What does it mean for a directed graph to be strongly connected?

Answer 6

We say that a directed graph is strongly connected if, for every two nodes u and v, there is a path from u to v and a path from v to u.

Question 7

define distance between nodes u and v

Answer 7

minimum number of edges between u and v

Question 8

when is an undirected graph considered a tree?

Answer 8

Trees We say that an undirected graph is a tree if it is connected and does not contain a cycle.