标签：#NP困难问题

带宽 (图论)

图论中，图带宽问题是用不同整数f(v_i)给图G的n个顶点v_i贴上标签，使得量\max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\}最小化的问题（其中E是G的边集）。 这问题可以形象理解为，将图的顶点置于沿x轴的不同整数点上，使最长边最短的问题。这种放置称作线性图排列（linear graph arrangement）、线性图布局（linear graph layout）或线性图放置（linear…