Graph Partitioning

释义 Definition

图划分：把一个图（由节点与边构成）分成若干个“部分/子图”，通常目标是让部分之间的连边尽量少（减少通信/耦合），同时每个部分的规模尽量均衡（负载均衡）。在并行计算、分布式系统、VLSI 布局、社交网络分析等场景很常见。

发音 Pronunciation (IPA)

/ɡræf pɑːrˈtɪʃənɪŋ/

例句 Examples

Graph partitioning helps distribute a large network across multiple servers.
图划分有助于把大型网络分配到多台服务器上。

Using spectral methods for graph partitioning, the team minimized cross-partition edges while keeping each cluster roughly the same size.
团队使用谱方法进行图划分，在保持各簇规模大致相同的同时，把跨分区的边尽量降到最少。

词源 Etymology

graph 源自希腊语 graphein（“书写、描画”），在数学与计算机科学中指“由点和线表示关系的结构”；partitioning 来自动词 partition（“分割、划分”），源自拉丁语 partitio（“分配、分割”）。组合起来即“对图进行划分”的技术与过程。

相关词 Related Words

• Bisection
• Clustering
• Community
• Cut
• Edge
• Graph
• K-way
• Load
• Min-cut
• Node
• Partition
• Spectral

文学作品 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）中在图与网络相关章节会提及与“划分/切割”相关的概念，用于讨论算法设计与复杂度。
• Graph Theory（Reinhard Diestel）中在图论框架下涉及割（cut）、分割与相关结构，为理解图划分提供理论背景。
• Networks, Crowds, and Markets（Easley & Kleinberg）在网络分析语境下讨论社群结构与聚类等内容，与图划分的思想密切相关。