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



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

  

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

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

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


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

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

其中

这说明 -d是的特征值.

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




  

相关话题

  为什么集合的本身还可以是一个集合的元素? 
  有哪些指标可以描述两个图(graph)的相似度? 
  如何证明这个图的染色问题? 
  这道排列组合该如何思考? 
  n 座桥,连通 n+1 个岛,有多少种连法? 
  已知映射f:N→N(其中N是正整数集),问以下三条是否可以相容? 
  哪些看似与图论无关的问题可用图论模型解决? 
  这个图能够一笔画完吗? 
  如何证明f(A∩B) ⊆ f(A)∩f(B) 而不是f(A∩B) = f(A)∩f(B) ? 
  如何估计这个级数? 

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





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