数学吧 关注:890,918贴子:8,757,202
  • 1回复贴,共1

有向连通无自环图G,有n个顶点和p条边。其incidence

取消只看楼主收藏回复

有向连通无自环图G,有n个顶点和p条边。其incidence矩阵定义为n*p矩阵B(v,e)。v,e为G的顶点和边。
如果v和e不相连,B=0。
如果v是e的发出点,B=1。
如果v是e的进入点,B=-1。
求证rank(B)=n-1
这里的连通是指,将G中所有边的方向去掉,得到的无向图G'是连通的。


IP属地:河北来自Android客户端1楼2019-10-29 18:35回复
    都没有说的很正式,如何证明其n-1个行向量或支撑树的列向量组无关,没说清楚。
    昨天看了下答案,大概证明方法是酱紫的:
    令x=(x1,x2,…,xn)为行向量,那么xB=0的解空间维度为1,基为全1行向量,于是rank(B)=n-1。
    这是因为对任意边(i, j),解都是xi=xj。边遍历所有顶点,于是所有xi都相等。


    IP属地:河北来自Android客户端4楼2019-10-30 09:56
    回复