In graph theory, the graph bandwidth problem is to label the n vertices v_i of a graph G with distinct integers f(v_i) so that the quantity is minimized (E is the edge set of G). 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. The weighted graph bandwidth problem is a generalization wherein the edges are assigned weights w_ij and the cost function to be minimized is . 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 . For several families of graphs, the bandwidth is given by an explicit formula. The bandwidth of a path graph Pn on n vertices is 1, and for a complete graph Km we have . For the complete bipartite graph Km,n, assuming which was proved by Chvátal. As a special case of this formula, the star graph on k + 1 vertices has bandwidth . For the hypercube graph on vertices the bandwidth was determined by to be Chvatálová showed that the bandwidth of the m × n square grid graph , that is, the Cartesian product of two path graphs on and vertices, is equal to min{m,n}. The bandwidth of a graph can be bounded in terms of various other graph parameters. For instance, letting χ(G) denote the chromatic number of G, letting diam(G) denote the diameter of G, the following inequalities hold: where is the number of vertices in . If a graph G has bandwidth k, then its pathwidth is at most k , and its tree-depth is at most k log(n/k) . In contrast, as noted in the previous section, the star graph Sk, a structurally very simple example of a tree, has comparatively large bandwidth. Observe that the pathwidth of Sk is 1, and its tree-depth is 2.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.