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



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

  

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

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

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


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

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

其中

这说明 -d是的特征值.

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




  

相关话题

  P是任意数域,如何证明P^n*n对于普通加法和乘法构成的环没有非平凡理想? 
  质数集P与自然数集N等势吗? 
  母函数都是用幂级数吗?三角级数可以构造母函数吗? 
  对 n × n 网格图,从左下角走到右上角的边不重复路径(即左下角到右上角的迹)有多少种? 
  “等价”就是重言等值,“推出”就是重言蕴涵吗? 
  如何直观地理解群论? 
  无限大的围棋盘上某个子的存活概率是多少? 
  为什么集合的本身还可以是一个集合的元素? 
  考虑一个半径为 1 的圆,若「随机」选择圆上的弦,求弦长的概率分布? 
  2018年,如何规划一条最新的《中国铁道大纪行》路线? 

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





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