Graph facts & stats

Question 1

What is a graph called when its edges have a direction, shown as arrows?

Accepted Answer

A directed graph. In a directed graph, or digraph, each edge goes from one vertex to another in a set direction.

Question 2

In a graph, what is a 'loop'?

Accepted Answer

An edge that connects a vertex to itself. A loop starts and ends at the same vertex.

Question 3

Breadth-first search usually uses which data structure to track vertices to visit?

Accepted Answer

A queue. A queue handles vertices first in, first out, so the search explores layer by layer.

Question 4

Which mathematician solved the Seven Bridges of Königsberg problem in 1736?

Accepted Answer

Leonhard Euler. Euler showed no walk could cross each bridge exactly once, an early result in graph theory.

Question 5

What does Dijkstra's algorithm find?

Accepted Answer

Shortest paths from a starting vertex in a graph with non-negative weights. Dijkstra's algorithm repeatedly settles the closest unvisited vertex to build shortest paths.

Question 6

In any undirected graph, the sum of all vertex degrees equals what?

Accepted Answer

Twice the number of edges. Each edge adds one to the degree of both of its endpoints, so it counts twice in the total.

Question 7

How many edges does the complete graph on 5 vertices, K5, have?

Accepted Answer

10. A complete graph on n vertices has n(n - 1)/2 edges: 5 x 4 / 2 = 10.

Graph facts & stats

The basics