大家好，欢迎来到IT知识分享网。
目录
一、邻接谱、邻接代数与图空间
（一）图的邻接谱
1、图的邻接谱定义
图的邻接矩阵A（G）的特征值及其重数，称为G的邻接谱。
为什么长这样？哪个是特征值哪个是重数？
邻接谱的第一行是特征值，第二行是特征值对应的重数。
同谱图定义：若两个非同构的n阶图具有相同的谱，则称它们是同谱图。
2、邻接谱的两个性质
s是特征值个数
用简单图的点数和边数估计了模的上界
（二）、图的邻接代数
图的邻接代数是一个向量空间，它是以邻接矩阵的多项式为元素构成的复数域上的向量空间。
1、图的邻接代数的定义
邻接矩阵是针对无环图定义的。
2、图的邻接代数的维数特征
不等式的界是紧的，意味着不可修改。
（三）、图空间
二、托兰定理
极值图论的早期结果
（一）、l部图的概念与特征
很明显偶图就是2部图呀
完全l部图
完全l部图的总边数是各个部的边数两两相乘的和
n阶完全l几乎等部图
可以看到完全l几乎等部图一共有l个部，各个部的顶点数要么为k要么为k+1,即只相差1，几乎是相等的，
一共有r个顶点数为k+1的部，剩下的是顶点数为k的部。所以总顶点数为（k+1）*r+k（l-r）=kl+r
如果每个部的顶点数都为k，那就不是完全l几乎等部图了，那就是完全l等部图。
定理5 完全l部图边数极大
，全等符号代表同构。
一个n阶l部图，当它同构于完全l几乎等部图的时候，图中边数最多。
（二）、托兰定理
1、度弱于的定义
如果有G中点到H中点的一一对应，且刚好G中的点的度小于等于对应的H中的点的度，则称G度弱于H，或H度优于G
且G度弱于H，则G的边数一定小于等于H的边数
托兰定理的引理
托兰定理
托兰定理指出，不含l+1阶完全图的极值图是完全l几乎等部图，开启了极值图论研究的先河！
（三）、托兰定理的应用
工兵排雷问题
这就跟托兰定理联系起来了。当且仅当距离大于1/根号2，两点之间才连线，即这样的图连线越多，
安全的人就越多，即图论的极值问题，求边最多的情况。
4=3+1，所以边数最多的情况是完全3几乎等部图
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/134854.html
