带宽 (图论) 图论中图带宽问题是用不同整数 f  v i  displaystyle fvi 给图G的n个顶点 v i displaystyle vi 贴上标签使得量 max   f  v i   f  v j    v i v j  E  displaystyle maxfvifvjvivjin E 最小化的问题其中E是G的边集 这问题可以形象理解为将图的顶点置于沿x轴的不同整数点上使最长边最短的问题这种放置称作线性图排列linear graph arrangement线性图布局linear graph layout或线性图放置linear graph placement 加权图带宽问题是广义化其中边被赋权 w i j displaystyle wij 需要最小化的损失函数为 max  w i j  f  v i   f  v j    v i v j  E   displaystyle maxwijfvifvjvivjin E 就矩阵而言无权图带宽是对称矩阵图的邻接矩阵的最小带宽带宽也可定义为比给定图的紧合区间超图的最大团大小小其中超图最小化了团大小Kaplan  Shamir