Metraipolis › archive › dc_2b5f85ed71ce
Graph bandwidth — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Graph_bandwidth
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T23:09:22.597Z
- SHA-256 of the archived text
00489dff4c02d67477d68f85e924fa57a50f1810ea8ec3688ca2425d043f207e- Stable URL of this page
https://metraipolis.com/documento/dc_2b5f85ed71ce
How to cite
Graph bandwidth — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Graph_bandwidth (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_2b5f85ed71ce (Metraipolis archive dc_2b5f85ed71ce, sha256 00489dff4c02d67477d68f85e924fa57a50f1810ea8ec3688ca2425d043f207e)
BibTeX
@misc{dc2b5f85ed71ce,
title = {Graph bandwidth — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Graph_bandwidth},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_2b5f85ed71ce; sha256 00489dff4c02d67477d68f85e924fa57a50f1810ea8ec3688ca2425d043f207e},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Graph_bandwidth. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 {\displaystyle n} vertices v i {\displaystyle v_{i}} of a graph G {\displaystyle G} with distinct integers f ( v i ) {\displaystyle f(v_{i})} so that the quantity max { | f ( v i ) − f ( v j ) | : v i v j ∈ E } {\displaystyle \max\{\,|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}} is minimized, where E {\displaystyle E} is the edge set of G {\displaystyle G} . The weighted graph bandwidth problem is a generalization wherein the edges are assigned weights w i j {\displaystyle w_{ij}} and the cost function to be minimized is the product of weight with length, max { w i j | f ( v i ) − f ( v j ) | : v i v j ∈ E } {\displaystyle \max\{\,w_{ij}|f(v_{i})-f(v_{j})|:v_{i}v_{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.
Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Graph bandwidth» — https://en.wikipedia.org/wiki/Graph_bandwidth
Wikidata Q5597073: «graph property» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5597073
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Graph_bandwidth?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1352725665, consultata il 2026-10-07T22:47:33.203Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 511a35dec0c6fc5d8618bd3ed335e02aede2f05ca7f47ad93a1f19ae77e166cc