3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think both orderings you suggest work. Yet a third solution is 1, 4, 7, 5, 6, 3, 2 and the bandwidth is indeed two. So note that in general, there can be several optimal solutions. $\endgroup$ – Juho Nov 11 '16 at 22:21
  • $\begingroup$ Thanks for the response @Juho and the edit to make it clearer. However how does my solution work? The minimum bandwidth in my solution is 1, when my professor claims it is 2. How does he jump from 7 to 5 or why? $\endgroup$ – Steven Nov 12 '16 at 3:07
  • $\begingroup$ (Edits are exactly the right solution for adding big chunks of text to a question!) $\endgroup$ – Raphael Nov 12 '16 at 7:17
  • $\begingroup$ @Steven But the graph is not a path, so the bandwidth has to be at least two. $\endgroup$ – Juho Nov 12 '16 at 8:06
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So what does that mean exactly by ordering? Does the ordering mean it is just 1, 2, 3, 4, 5, 6, 7? If this is the case, wouldn't the bandwidth start with 7 and 6? If the solution starts with 1 and 4, they are 3 numbers away from one another, while 7 and 6 are a number apart. Wouldn't that also mean the minimum bandwidth is 3? Since we can't have a number greater than 3? $\endgroup$ – Steven Nov 12 '16 at 17:42
  • $\begingroup$ Is this what you mean by ordering? Assuming I understand the question wiki page correctly(not my original comment of 1,2 3, 4, 5, 6, 7)...I actually don't see what's the point. It just seems like we are recreating the graph, and I feel like leaving the graph as is, would be redundant to remake the graph and almost meaningless... I mean couldn't 1, 6, 5, 2, 3, 7, 4 also be a possible permutation? $\endgroup$ – Steven Nov 12 '16 at 17:57
  • $\begingroup$ By ordering I mean a permutation of the vertices. For example, 2,4,1,5,7,6,3. $\endgroup$ – Yuval Filmus Nov 12 '16 at 17:58
  • $\begingroup$ How did you end up getting 2, 4, 1, 5, 7, 6, 3? Assuming I am understanding the wiki page I linked, let me see if I understand this. I started at 1, 4 is a parent of 1, so 7 is 1 node away from 4, 2 nodes away from 6, and 3 nodes away from 2 and 3, and 4 from 5. So trying to keep the distance small as possible, I went to 6, then I went to 4 because 7 would be the parent and then we need to connext to 4, then I went to 4, then 3, then 5, then 2 So I got 1, 6, 4, 3, 7, 2, 5 I am not really sure what this is doing. $\endgroup$ – Steven Nov 12 '16 at 18:11
  • $\begingroup$ Does 2, 4, 1, 5, 7, 6, 3 have minimal bandwidth (and another optimal solution)? What was your thought process when going through it? Thanks for helping me try to understand this. $\endgroup$ – Steven Nov 12 '16 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.