Question

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

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top