Chapter 9. Graphs

Question 1

What is a list?

Answer 1

A linear data structure, where the elements are ordered in: A_1, A_2, A_3, … A_n. Order may or may not be relevant in this data structure.

Question 2

What is a tree?

Answer 2

A generalization of a list, each branch is composed of lists.

Question 3

What is a graph?

Answer 3

Essentially a graph is a collection of vertices (V) and edges (E).

Question 4

What are the two main variations that we can have for a graph?

Answer 4

We can have a directed graph or an undirected graph.

Question 5

What is an edge in a directed graph?

Answer 5

An edge from a directed graph is, a pair (v,w). Where v is the starting vertex and w is the ending vertex.

Question 6

What is an edge in an undirected graph?

Answer 6

A pair (v,w) belonging to the set of edges. Such that v or w is the starting vertix and v or w but not both is the ending vertix.

Question 7

What is the weight of an edge in a graph?

Answer 7

The cost associated with each edge. The cost of getting from one vertex to another.

Question 8

Why are graph algorithms so important?

Answer 8

Because the algorithms can be used to solve many real world applications.

Question 9

What is an edge?

Answer 9

A single path (v,w) from one vertex v to another vertex w.

Question 10

What is the in-degree of a vertex v?

Answer 10

Indicates how many vertices go into v.

Question 11

What is the out-degree of a vertex u?

Answer 11

Number of edges that go out of the vertex u.

Question 12

When do we say that vertex w is adjacent to vertex v?

Answer 12

If and only if (v,w) is an element of the set of edges.

Question 13

What is a path in a graph?

Answer 13

A sequence of vertices w_1, w_2, w_3, … w_n such that each pair (w_i, w_(i+1)) forms an edge.

Question 14

What is the length of a path?

Answer 14

This is proportional to the number of edges in the path. Or to the number of vertices visited: N - 1.

Question 15

What is a simple path?

Answer 15

Path in which all vertices are distinct, except that the first and last vertices can be the same. We don’t cross the same vertex more than once, unless that same vertex is the first and last one.

Question 16

What is a cycle in a directed graph?

Answer 16

Path in a directed graph, of length at least 1 such that the starting and ending vertices are the same.

Question 17

When is a cycle in a directed graph simple?

Answer 17

When all vertices are distinct except for possibly the first and last ones can be the same.

Question 18

What is a cycle in an undirected graph?

Answer 18

Cycle such, that the first and last vertices are equal except that all edges must be distinct. Because for every (v,u), (u,v) is essentially the same edge.

Question 19

When is a directed graph acyclic?

Answer 19

When the directed graph has no cycles.

Question 20

What is a loop?

Answer 20

edge (v,v) such that it is a path from a vertex v to itself.

Question 21

When is an undirected graph said to be connected?

Answer 21

When there is a path from every vertex to every other vertex.

Question 22

When is a directed graph said to be strongly directed?

Answer 22

Whenever there is a path from every vertex to every other vertex

Question 23

When is a directed graph said to be weakly connected?

Answer 23

When the underlying graph (graph with no arrows) is connected.

Question 24

What is a complete graph, for an undirected graph?

Answer 24

If there is an edge for every pair of distinct vertices (v, w).

Question 25

What is a real life example of where we would see graphs?

Answer 25

Airport systems with graphs, where each airport is a vertex.

Question 26

What are the two methods that we utilize to represent graphs?

Answer 26

Adjacency matrix as well as adjacency list.

Question 27

What is an adjacency matrix?

Answer 27

A two dimensional array, if an edge (u,v) exists then A[u][v] is set too true and false otherwise.

Question 28

How do we represent graphs with weights with adjacency matrices?

Answer 28

Set A[u][v] equal to the weight, and we utilize a sentinel value to indicate that an edge does not exist.

Question 29

When do we consider a graph to be dense?

Answer 29

For every vertex, we have an edge going to every other vertex.

Question 30

What is an adjacency list?

Answer 30

Standard way to represent graphs which are “sparse” in other words not dense.

Question 31

Why is an adjacency list better than an adjacency matrix?

Answer 31

Because, we don’t need to worry about creating space for edges that don’t even exist.

Question 32

What do we store in an adjacency list?

Answer 32

For every vertex, we store the adjacent vertices.

Question 33

What is a subgraph?

Answer 33

Denoted as G’, vertex and edge set of a subgraph are a subset of the set of vertices and edges of G.