Understanding the bandwidth problem on graphs

I'm trying to understand the bandwidth problem on graphs. Consider the following tree given as an adjacency list:

1 => 4
2 => 6
3 => 5, 6
4 => 7
5 => 3
6 => 2, 3, 7
7 => 4, 6

It is claimed an optimal ordering of the vertices is 1 4 5 7 3 6 2, but I don't see how.

When I draw the graph, 5 is 4 edges away from 4, and 3 edges away from 7... yet we jump back to 7 anyways? I don't understand how this problem works.

Wouldn't the ordering be 1, 4, 7, 6, 2, 3, 5 because everything is one node apart, with a maximum bandwidth of 2, because 2 is 2 edges away from 3? With 1 edge separating everything else.

Bandwidth problem explained in homework assignment:


The bandwidth problem takes as input a graph G, with n vertices and m edges (ie. pairs of vertices).
The goal is to find a permutation of the vertices on the line which minimizes the maximum length of any
edge. This is better understood through an example. Suppose G consists of 5 vertices and the edges (v1, v2),
(v1, v3), (v1, v4), and (v1, v5). We must map each vertex to a distinct number between 1 and n. Under the
mapping vi → i, the last edge spans a distance of four (ie. 5-1). However, the permutation {2, 3, 1, 4, 5} is
better, for none of the edges spans a distance of more than two. In fact, it is a permutation which minimizes
the maximum length of the edges in G, as is any permutation where 1 is in the center

I think you got the definition of bandwidth wrong. Here is your definition of the bandwidth of an ordering of the vertices:


The bandwidth is the maximum distance in the graph between adjacent nodes in the ordering.

The correct definition is:


The bandwidth is the maximum distance in the ordering between adjacent nodes in the graph.

Your problem is equivalent to the usual one – just take the inverse of the ordering permutation to get from one to the other.

StackExchange Computer Science Q#65901, answer score: 3