割宽
图论中，无向图的割宽（cutwidth）是能满足下列性质的最小整数k：图存在顶点排序，使得将顶点划分为排序的前后子集所得的割至少跨过k条边。具体点说，若将顶点编上号v_1,v_2,\dots v_n，则\forall\ell=1,2,\dots n-1，使i\le\ell,\ j>\ell的边v_iv_j最多有k条。 图的割宽也叫做其耐折数（folding number）。产生割宽的顶点排序以及计算这种排序与割宽的问题，统称为最小割线性…
标签：#图常量
共 9 篇文章
度分布
度分布是图论和网络理论中的概念。一个图（或网络）由一些顶点（节点）和连接它们的边（连结）构成。每个顶点（节点）连出的所有边（连结）的数量就是这个顶点（节点）的度。度分布指的是对一个图（网络）中顶点（节点）度数的总体描述。对于随机图，度分布指的是图中顶点度数的概率分布。 定义 度分布是图论和（复杂）网络理论中都存在的概念。首先介绍图的概念。一个图G=G(V, E)是一个由两个集合V和E构成的二元组。集合V一般由有限个元素构成：V = \{…
团宽
。顶点标签用颜色表示。]] 图论中，图G的团宽（clique-width）是描述图的结构复杂性的参数，与树宽密切相关，但对稠密图来说可以很小。 团宽的定义是通过以下4种操作，构造G所需的最少标号数： 创建标签为i的新顶点v，记作i(v)； 两有标图G、H的不交并，记作G \oplus H； 用边连接标i的每个顶点与标j的每个顶点，记作\eta(i,\ j),\ i\ne j； 将标签i改为标签j，记作\rho(i,\ j) 团宽有界图包…
径宽
图论中，图G的径分解（path decomposition）是G的“加粗”路径图表示，G的径宽（pathwidth）是衡量形成G的路径被加粗的程度。更正式地说，径分解是G的顶点子集序列，使每条边的端点出现在某一子集中，并使每个顶点都出现在子集连续子序列中，径宽等于这样的分解中最大集的大小减一。 径宽也叫做区间厚度（interval thickness，等于G的区间父图中的最大团大小减一）、顶点分隔数（vertex separation …
介数中心性
。]] 在图论中，介数中心性（，又译作中间中心性）是基于最短路径针对网络图中心性的衡量标准之一。针对全连接网络图，其中任意两个节点均至少存在一个最短路径，在无权重网络图中该最短路径是路径包含边的数量求和，加权网络图中该最短路径则是路径包含边的权重求和。每个节点的介数中心性即为这些最短路径穿过该节点的次数。 介数中心性在网络理论中有广泛的应用：它代表了某节点与其他节点之间的互动程度。 例如，在通信网络中，一个有更高介数中心性的节点在网络中…
带宽 (图论)
图论中，图带宽问题是用不同整数f(v_i)给图G的n个顶点v_i贴上标签，使得量\max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\}最小化的问题（其中E是G的边集）。 这问题可以形象理解为，将图的顶点置于沿x轴的不同整数点上，使最长边最短的问题。这种放置称作线性图排列（linear graph arrangement）、线性图布局（linear graph layout）或线性图放置（linear…
刻宽
图论中，图的刻宽（carving width）是由图定义的数，描述了图顶点的层次聚类中，分隔聚类的边数。 定义与例子 刻宽是根据给定图顶点的分层聚类（称作“刻”，carving）定义的。刻可以描述为无根二叉树，其叶上标有给定图的顶点。从树上移除任意一条边，都会将树分为两子树，并相应地将树上顶点分为两簇。这样形成的顶点簇构成了层状集合族（Laminar set family）：任意两顶点簇（不仅是移除同一条边形成的两互补簇）或不交，或是包…
树宽
图论中，无向图的树宽（treewidth）是描述图与树的距离的正整数。树宽为1的图就是树或森林。树宽不大于2的图叫做系列并行图。树宽恰为k的最大图称作k树，树宽不大于k的图称作部分k树。很多有充分研究的图族的树宽也是有界的。 树宽可用几种等价方式正式定义：图的树分解中最大顶点集的大小、图的弦补全中最大团的大小、描述图上追逃对策的港的最大阶数、刺藤（bramble，相互接触的连通子图的集合）的最大阶数。 树宽常用作图算法的参数复杂性分析中…
特征向量中心性
在图论中，特征向量中心性(eigenvector centrality)是测量节点对网络影响的一种方式。针对连接数相同的节点，相邻节点分数更高的节点会比相邻节点分数更低的节点分数高，依据此原则给所有节点分配对应的分数。特征向量得分较高意味着该节点与许多自身得分较高的节点相连接。 谷歌的PageRank和Katz中心性是特征向量中心性的变体。 利用邻接矩阵求特征向量中心性 给定一个节点集合为|V|的图G=(V,E)，定义其邻接矩阵为A =…