Content deleted Content added
Not really about drawing |
fix mathmode |
||
Line 1:
In [[graph theory]], the '''graph bandwidth problem''' to label the ''n'' vertices ''v<sub>i</sub>'' of a graph ''G'' with distinct integers ''f''(''v<sub>i</sub>'') so that the quantity <math>\max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\}</math> is minimized (''E'' is the edge set of ''G'').<ref>{{harv|Chinn|Chvátalová|Dewdney|Gibbs|1982}}</ref>
The problem may be visualized as placing the vertices of a graph at distinct integer points along the ''x''-axis so that the length of the longest edge is minimized. Such placement is called '''linear graph arrangement''', '''linear graph layout''' or '''linear graph placement'''.<ref name=feige/>
The '''weighted graph bandwidth problem''' is a generalization wherein the edges are assigned weights ''w<sub>ij</sub>'' and the [[cost function]] to be minimized is <math>\max\{\, w_{ij} |f(v_i) - f(v_j)| : v_iv_j \in E \,\}</math>.
In terms of matrices, the (unweighted) graph bandwidth is the [[bandwidth (matrix theory)|bandwidth]] of the [[symmetric matrix]] which is the [[adjacency matrix]] of the graph.
| |||