百科问答小站 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次? 
  请教拓扑排序中的一点疑问? 
  1×0=0 是因为 0 乘以任何数字都等于 0,还是因为 1 乘任何数字都等于那个数? 
  对 n × n 网格图,从左下角走到右上角的边不重复路径(即左下角到右上角的迹)有多少种? 
  我好像证明了四色猜想,各位怎么看? 
  在集合的势的意义下,是否存在比实数集更大的全序集? 
  如何用组合数学证明 (n²)! 能被 (n!)^(n+1) 整除? 
  到底是奇数多还是偶数多? 

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





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