Lesson plan
Graph bandwidth
In graph theory, the graph bandwidth problem may be visualized as placing the vertices of a given graph at distinct integer positions along the number line so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement. It may be formalized as labeling the n vertices v_i of a graph G with distinct integers f(v_i) so that the quantity \max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\} is minimized, where E is the edge set of G . The weighted graph bandwidth problem is a generalization wherein the edges are assigned weights w_{ij} and the cost function to be minimized is the product of weight with length, \max\{\, w_{ij} |f(v_i) - f(v_j)| : v_iv_j \in E \,\} . In terms of matrices, the (unweighted) graph bandwidth is the minimal bandwidth of a symmetric matrix which is an adjacency matrix of the graph. The bandwidth may also be defined as one less than the maximum clique size in a proper interval supergraph of the given graph, chosen to minimize its clique size.
Article summary
In graph theory, the graph bandwidth problem may be visualized as placing the vertices of a given graph at distinct integer positions along the number line so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement. It may be formalized as labeling the n vertices v_i of a graph G with distinct integers f(v_i) so that the quantity \max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\} is minimized, where E is the edge set of G . The weighted graph bandwidth problem is a generalization wherein the edges are assigned weights w_{ij} and the cost function to be minimized is the product of weight with length, \max\{\, w_{ij} |f(v_i) - f(v_j)| : v_iv_j \in E \,\} . In terms of matrices, the (unweighted) graph bandwidth is the minimal bandwidth of a symmetric matrix which is an adjacency matrix of the graph. The bandwidth may also be defined as one less than the maximum clique size in a proper interval supergraph of the given graph, chosen to minimize its clique size.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.