Graph facts & stats

Question 1

What makes a graph 'weighted'?

Accepted Answer

Each edge has a number, such as a distance or cost. Weights often stand for distances, travel times or costs, as on a road map.

Question 2

What is a square table that records which pairs of vertices are connected called?

Accepted Answer

An adjacency matrix. Entry (i, j) of an adjacency matrix shows whether there is an edge from vertex i to vertex j.

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

A tree with n vertices has how many edges?

Accepted Answer

n - 1. A tree is connected with no cycles, which always needs exactly one fewer edge than vertices.

Question 6

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.

Question 7

A connected graph has an Euler circuit exactly when what is true?

Accepted Answer

Every vertex has even degree. An Euler circuit uses each edge once and returns to the start, which requires entering and leaving each vertex equally.

The basics