強正則圖
圖論中，強正則圖（，SRG）是一個正則圖 G=(V,E)，有 v 個頂點和 k 度，並且滿足以下條件：對於給定的整數 \lambda, \mu \ge 0， 任意兩個相鄰頂點都有 \lambda 個共同鄰居 任意兩個不相鄰頂點都有 \mu 個共同鄰居 這樣的強正則圖通常記作 \text{srg}(v,k,\lambda,\mu)。它的補圖也是一個強正則圖，記作 \text{srg}(v,v-k-1,v-2-2k+ \mu,v-2k+\l…
标签：#代数图论
共 10 篇文章
模块度
模块度也称模块化度量值，是目前常用的一种衡量网络强度的方法，最早由提出。模块度的定义为： Q = \frac{1}{2m}\sum_{ij}\left[A_{ij}-\frac{k_ik_j}{2m}\right]\delta(C_i,C_j) 模块度值的大小主要取决于网络中结点的社区分配C，即网络的社区划分情况，可以用来定量的衡量网络社区划分质量，其值越接近1，表示网络划分出的社区结构的强度越强，也就是划分质量越好。因此可以通过最大化…
代数连通度
，直径3，连通度1，代数连通度0.722。]] 图G的代数连通度（algebraic connectivity）是G的拉普拉斯矩阵的第二小的特征值（重特征值要重复计算）。这个特征值大于0当且仅当G是连通图。这是一个简单的推论，因为拉普拉斯矩阵的特征值0的重数就是图的连通分支的个数。这个值的大小反映了整个图的连通程度。它可以用于分析网络的稳定性与可同步性。 性质 图G的代数连通度大于0当且仅当G是连通图。而且，图的代数连通度的值不大于（顶…
谱聚类
在多元变量统计中，谱聚类（）技术利用数据相似矩阵的谱（特征值），在对数据进行降维后，以较少的维度进行聚类。相似矩阵作为输入，提供了对数据集中每一对点相对相似性的定量评估。 在图像分割中，谱聚类被称为基于分割的物体分类。 算法 ; 基本算法 计算拉普拉斯矩阵 L （或归一化的拉普拉斯矩阵） 计算前 k 个特征向量（这些特征向量对应 L 的 k 个最小的特征值） 考虑由这 k 个特征向量组成的矩阵，矩阵的第 l 行定义了图节点 l 的特征 …
譜圖論
數學上，譜圖論（）是圖論的分支，研究图的性質與其邻接矩阵、调和矩阵等的特徵多項式、特征值和特征向量有何關聯。n個頂點的圖，其鄰接矩陣是n\times n矩陣，各分量分別以0或1表示對應的兩頂點之間是否有連邊。簡單無向圖的鄰接矩陣是實對稱矩陣，從而可，其特徵值皆是實代數整數。 雖然鄰接矩陣取決於如何標記頂點以作排序，但是矩阵的谱是圖不變量，不取決於標記方式。（不過也不是完備不變量，不足以完全刻畫圖的全部性質。） 譜圖論亦關注藉圖的矩陣特徵…
度数矩阵
在数学领域图论中，无向图的度数矩阵（）是一个对角矩阵 ，其中包含的信息为的每一个顶点的度数，也就是每个顶点相邻的边数。 它可以和邻接矩阵一起使用以构造图的拉普拉斯算子矩阵（拉普拉斯矩阵是度数矩阵和邻接矩阵的差值）。 定义 给定一个图 G=(V,E) 与 |V|=n， G的度数矩阵 D是一个 n \times n的对角线矩阵，其定义为 : d_{i,j}:=\left\{ \begin{matrix} \deg(v_i) & \mbox{…
调和矩阵
在图论中，调和矩阵（harmonic matrix），也称拉普拉斯矩阵或拉氏矩阵（Laplacian matrix）、离散拉普拉斯（discrete Laplacian），是图的矩阵表示。 调和矩阵也是拉普拉斯算子的离散化。换句话说，调和矩阵的缩放极限是拉普拉斯算子。它在机器学习和物理学中有很多应用。 定义 若G是简单图，G有n个顶点，A是邻接矩阵，D是度数矩阵，则调和矩阵是 E(f) = \sum w(uv)(f(u)-f(v))^2…
邻接代数
在代数图论中，图G的邻接代数（adjacency algebra）是这个图的邻接矩阵A(G)的多项式所组成的代数。它是一种矩阵代数，是A的各次幂的线性组合所组成的集合。 其他一些类似的数学对象也被称为“邻接代数”。 性质 G的邻接代数的性质与G的图论性质相关，例如各种谱、邻接性、连通性。 命题：顶点i,j之间长度为d路径的数目等于A^d的(i,j)元。 命题：对于直径为d的连通图，其邻接代数的维数至少是d+1。 推论：直径为d的连通图至…
图自同构
在图论中，图自同构（graph automorphism）是保持自身的顶点与边的连接关系的对称。 正式地说，图G=(V,E)的自同构是顶点集的置换\sigma，使得顶点对(u,v)组成一条边当且仅当(\sigma(u),\sigma(v))也组成一条边。也就是说，\sigma是G到自身的图同构。自同构的这个定义对有向图和无向图都适用。两个自同构的复合仍是自同构，并且给定一个图，其所有自同构的集合在复合运算下构成群，称为这个图的自同构群。…
代数图论
，一种高度对称的图。它的直径为2。其自同构群有120个元素，事实上就是对称群S_5。]] 代数图论（algebraic graph theory）是用代数方法处理图论问题的数学分支。这不同于几何、组合或算法的方法。代数图论有三个主要分支，分别使用线性代数，使用群论，以及研究图不变量。 代数图论的分支 使用线性代数 代数图论的第一个分支用线性代数来研究图，特别是研究图的邻接矩阵或拉普拉斯矩阵的谱（这部分代数图论也被称为谱图理论）。以佩特森…