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 =&gt; 4
2 =&gt; 6
3 =&gt; 5, 6
4 =&gt; 7
5 =&gt; 3
6 =&gt; 2, 3, 7
7 =&gt; 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.