第一章图谱理论导引

作者: 花雪白芷 | 来源:发表于2022-01-11 10:14 被阅读0次

第一章图谱理论导引
30函数实现
锦绣蓝图:怎样规划令人流连忘返的网站（1）
《传播理论导引：分析与应用》
《计算理论导引》学习指南
计算理论导引阅读笔记-1
计算理论导引阅读笔记-2
机器学习算法与Python实践 - 知识图谱
中医推拿术
计算机理论导引（一）

令图 $G$ 为一个有限简单图，用数字 $1,2,\cdots,n$ 标记 G 的顶点，若点 $u,v$ 由一条边相连，则记 $u\sim v$ 。于是，人们可以得到 $G$ 的 $(0,1)$ - 邻接矩阵 $A=(a_{ij})_{n\times n}$ ，其中当 $i\sim j$ ， $a_{ij}=1$ ,否则 $a_{ij}=1$ 。由于 A 为对称矩阵，不妨令 $\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$ 为 $A$ 的特征值。

命题 1 记图 $G$ 中的点的最大度数为 $\Delta(G)$ ,则矩阵 $A$ 的任何特征值 $\lambda$ 满足 $\left| \lambda \right|\leq\Delta\left( G\right)$ 。

证明：令 $AX=\lambda X$ ，设 $\left| x_{i}\right|=max\left\{ \left| x \right|_{1},\dots\left| x \right|_{n}\right\}>0$ ，则 $\lambda x_{i}=\sum_{j\sim i}x_{j}$ ，两边取绝对值，有

$\left|\lambda\right|\left| x _{i}\right|\leq\sum_{j\sim i}\left| x_{j} \right| \leq\Delta\left( G \right)\left| x_{u} \right| \Rightarrow\left|\lambda\right|\leq\Delta\left( G\right) 。$

注： $\forall u\in V$ ， $d(u)=\sum_{v:v\sim u}1$ 成为 $u$ 的度数。

正则图的一些性质

定义2 若图 $G$ 每个点的度数相同，则称 $G$ 为一个正则图。

命题 3（正则图的判定） $G$ 为正则图当且仅当每个分量元素为1的列向量为 $A$ 的特征向量。

证明：充分性，记 $j=(1,1,\cdots,1)^{T}$ ，则 $Aj=\lambda j$ ，即， $\forall u\in V,d(u)=\sum_{v:v\sim u}1=\lambda$ ，那么 $G$ 为一个正则图。

必要性，倒推即可。

第一章图谱理论导引
令图为一个有限简单图，用数字标记 G 的顶点，若点由一条边相连，则记。于是，人们可以得到的 - 邻接矩阵...
30函数实现
计算理论导引作业2020/7/9交。递归函数30个程序的实现。
锦绣蓝图:怎样规划令人流连忘返的网站（1）
信息架构的首要目的就是实现可查找性。第一章、八个基本原则（经验与规则）原则一：标识导引设计利用标识导引，人们...
《传播理论导引：分析与应用》
第8章期望违背理论 20世纪70年代朱迪.伯贡提出期望违背理论，自此该理论已经成为研究非语言传播对行为影响的主要...
《计算理论导引》学习指南
本文尚在草稿状态，很难在短期内完成写作。发布出来旨在为初学者提供一些指引：书籍、资料、简介、历史还有我在不同年代的...
计算理论导引阅读笔记-1
图灵机与可计算性理论在介绍图灵机前先来简略了解一下哥德尔完备性：哥德尔完备性定理成立。它声称对于任何一阶理论T...
计算理论导引阅读笔记-2
图灵机的形式化一台图灵机是一个七元组[2]，{Q，Σ，Γ，δ，q0,qaccept,qreject}，其中 Q，...
机器学习算法与Python实践 - 知识图谱
机器学习/人工智能知识图谱可以为自己建立一个机器学习的知识图谱，并争取掌握每一个经典的机器学习理论和算法，简单...
中医推拿术
中医推拿，又称“按摩”、“按跷”、“导引”、“案”、“摩消”等，是依据中医理论对体表特定部位施以各...
计算机理论导引（一）
第一节导引计算机的发明是为了解决难以计算的问题（很显然），它建立在复杂性理论的基础上（我的理解是复杂度这个概念...

第一章图谱理论导引

正则图的一些性质

相关文章