Graphs

Question 1

What is a graph?

Answer 1

This is a collection of distinct vertices and edges.

Question 2

What is a subgraph?

Answer 2

This is a portion of a graph, which is also a graph itself.

Question 3

What is the difference between a directed graph and an undirected graph?

Answer 3

A directed graph represents one-way connections, while an undirected graph represents two-way connections.

Question 4

What is a path?

Answer 4

This is a sequence of edges between two nodes.

Question 5

What is the length of a path?

Answer 5

This is the number of edges a path comprises.

Question 6

What is a cycle?

Answer 6

This is a path that begins and ends at the same vertex.

Question 7

What is an acyclic graph?

Answer 7

This is a graph which has no cycle.

Question 8

What is a weighted graph?

Answer 8

This is a graph which has weights on its edges.

Question 9

What is a connected graph?

Answer 9

This is a graph which has a path between each pair of distinct nodes.

Question 10

What is a completed graph?

Answer 10

This a graph that not only has a path, but an edge between each pair of distinct vertices.

Question 11

What are neighbors?

Answer 11

In an undirected graph, these are nodes connected by an edge. In a directed graph, these are only the nodes that are related by a one-way connection.

Question 12

How many edges at most, can a directed graph with n vertices have?

Answer 12

n(n-1) vertices

Question 13

How many vertices, at most, can a directed graph with n vertices have?

Answer 13

n(n-1]/2 vertices

Question 14

What is a sparse graph?

Answer 14

This is a graph that has relatively few edges; O(n) edges

Question 15

What is a dense graph?

Answer 15

This is a graph that has relatively many edges O(n^2) edges.

Question 16

What is a topological order?

Answer 16

This is a graph where, when there is a directed edge between two nodes a and b, node a precedes node b.

Question 17

What is a depth-first traversal?

Answer 17

This is a type of traversal where we go as deep as possible into the graph before searching the paths of other nodes.

Question 18

What is a breadth-first traversal?

Answer 18

This is a type of traversal that visits the neighbors of a node before visiting neighbors’ neighbors.

Question 19

What is the origin vertex?

Answer 19

This is the vertex where a traversal begins.