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



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

  

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

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

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


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

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

其中

这说明 -d是的特征值.

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




  

相关话题

  “黎曼猜想在公元2030年之前(含2030年)被证明的概率大于等于60%”这个陈述是不是命题? 
  请问这个一阶逻辑等值式如何理解,请举一个现实的例子? 
  如何证明这个与树有关的递推式? 
  如何解决这个图的特征值问题? 
  n*n的棋盘填上1,2,...,n^2,使任意相邻(有公共边)格子里的数字之和不大于S,求S最小值? 
  竞赛组合题的成绩可以通过训练得到显著提高吗? 
  在一个球内任取n个点,则这n个点落在同一个半球内的概率是多少? 
  数学上,「数」是怎么定义的? 
  n 座桥,连通 n+1 个岛,有多少种连法? 
  从一副麻将(136 张)中任取 n 张,总能用其中 14 张组成和牌形,那么 n 至少是多少? 

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





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