百科问答小站 logo
百科问答小站 font logo



如何解决这个图的特征值问题? 第1页

  

user avatar   the-areas 网友的相关建议: 
      

定理. 设 是连通图,最大顶点度数是 ,邻接矩阵 的最小特征值是 。那么 当且仅当 是每个顶点度数都是 的二部图。

证明. 设 是 对应的特征向量,设 ,那么 ,所以 。
如果 是二部图 ,每个顶点度数都是 ,那么 , ,其中 是 矩阵。令 ,其中 是 个 1 的向量,那么 ,所以 。
反过来,如果 ,那么 ,所以对每个 都有 。同理,对每个 都有 。归纳可得对每个顶点 都有 ,并且 当且仅当 。设 、 ,那么 是二部图。因为 ,所以每个顶点度数都是 。


user avatar   xu-jing-ye-82 网友的相关建议: 
      

因为G是一个二部图。图存在如下partition

其中

这说明 -d是的特征值.

同时因为diagonal dominate, (A + d I) 是半正定 说明-d是的最小特征值.




  

相关话题

  在一个球内任取n个点,则这n个点落在同一个半球内的概率是多少? 
  对 n × n 网格图,从左下角走到右上角的边不重复路径(即左下角到右上角的迹)有多少种? 
  有n级台阶,每次可以走1~(n-1)的任意阶数,那么一共有多少种走法? 
  已知映射f:N→N(其中N是正整数集),问以下三条是否可以相容? 
  “等价”就是重言等值,“推出”就是重言蕴涵吗? 
  请问这个关于全排列的图论结论如何证明? 
  数学上,「数」是怎么定义的? 
  如何求解这个偏序集的问题? 
  给定正整数 n,将 1 拆分为 n 个互不相同的单位分数之和,不计次序,有几种拆法? 
  任给N个连续的整数,是否能从中找到一些数(至少一个),使得它们加起来是N(N+1)/2的倍数? 

前一个讨论
如何求解这个偏序集的问题?
下一个讨论
科学家都是怎么记忆复杂的物理公式的?





© 2025-04-26 - tinynew.org. All Rights Reserved.
© 2025-04-26 - tinynew.org. 保留所有权利