PPT《图论习题》

10 设图G有n个结点,r个连通分支,则图G的路径矩阵的秩为n-r. 证明:设图G的r个连通分支为G1, G2, …, Gr.得分块路径矩阵如下: 因为Gi是连通图,Gi的秩是连通分支Gi的结点个数-1,所以rank(G)=?rank(Gi)=n-r. 本题背景:1 线性相关/线性无关 如果对m个向量?1, ?2, …., ?m?Fm,有m个不全为零的数k1, k2, …., km?F,使k1?1+k2?2 +…….+km?m=0n成立,则称?1, ?2, …., ?m线性相关;

否则,称?1, ........