目录

一、邻接谱、邻接代数与图空间

（一）图的邻接谱

1、图的邻接谱定义

2、邻接谱的两个性质

（二）、图的邻接代数

1、图的邻接代数的定义

2、图的邻接代数的维数特征

（三）、图空间

二、托兰定理

（一）、l部图的概念与特征

    完全l部图

    n阶完全l几乎等部图

    定理5  完全l部图边数极大

（二）、托兰定理

1、度弱于的定义

     托兰定理的引理

     托兰定理

（三）、托兰定理的应用

   工兵排雷问题

    图的邻接矩阵A（G）的特征值及其重数，称为G的邻接谱。

    为什么长这样？哪个是特征值哪个是重数？

    邻接谱的第一行是特征值，第二行是特征值对应的重数。

    同谱图定义：若两个非同构的n阶图具有相同的谱，则称它们是同谱图。

    s是特征值个数

    用简单图的点数和边数估计了模的上界

图的邻接代数是一个向量空间，它是以邻接矩阵的多项式为元素构成的复数域上的向量空间。

    邻接矩阵是针对无环图定义的。

     不等式的界是紧的，意味着不可修改。

极值图论的早期结果

    很明显偶图就是2部图呀

    完全l部图的总边数是各个部的边数两两相乘的和

    可以看到完全l几乎等部图一共有l个部，各个部的顶点数要么为k要么为k+1,即只相差1，几乎是相等的，

    一共有r个顶点数为k+1的部，剩下的是顶点数为k的部。所以总顶点数为（k+1）*r+k（l-r）=kl+r

    如果每个部的顶点数都为k，那就不是完全l几乎等部图了，那就是完全l等部图。

    ，全等符号代表同构。

     一个n阶l部图，当它同构于完全l几乎等部图的时候，图中边数最多。

       如果有G中点到H中点的一一对应，且刚好G中的点的度小于等于对应的H中的点的度，则称G度弱于H，或H度优于G

       且G度弱于H，则G的边数一定小于等于H的边数

       托兰定理指出，不含l+1阶完全图的极值图是完全l几乎等部图，开启了极值图论研究的先河！

    这就跟托兰定理联系起来了。当且仅当距离大于1/根号2，两点之间才连线，即这样的图连线越多，

    安全的人就越多，即图论的极值问题，求边最多的情况。

    4=3+1，所以边数最多的情况是完全3几乎等部图