证明：设图G有n个结点 r个最大连通子图则图G的完全关联矩阵的秩为n－r．

大学 2023-04-07 07:15:07 结点,矩阵,最大已帮助人

证明：设图G有n个结点，r个最大连通子图，则图G的完全关联矩阵的秩为n-r．

难度★★☆ 搜索

设图G的r个最大连通子图为G1，G2，…，Gr，依次对G1，G2，…，Gr中的结点和边编号，由于Gi(1≤i≤r)都是最大连通子图，故G与Gj(i≠j)之间没有边，在这种编号下，M(G)为分块矩阵
$latex.action?latex=TShHKT1cbGVmdFtcYmVnaW57YXJyYXl9e2NjY2N9TShHXzEpICYwICAmXGNkb3RzICAgJjAgXFww%0D%0AICZNKEdfMikgICZcZGRvdHMgICAmXHZkb3RzICBcXFx2ZG90cyAgJlxkZG90cyAgICZcZGRvdHMg%0D%0AICAmMCBcXDAgJlxjZG90cyAgICYwICAmTShHX3IpXGVuZHthcnJheX1ccmlnaHRd$
这里M(Gi)(1≤i≤r)是图G的关联矩阵．由于G为连通图，r(M)=|Vi|-1，|Vi|是图Gi的结点数目．故而
$latex.action?latex=cihNKT1cc3VtIF97aT0xfV5ycihNKEdfaSkpPVxzdW0gX3tpPTF9XnIofFZfaXwtMSk9XHN1bSBf%0D%0Ae2k9MX1ecnxWX2l8LXI9bi1y$

证明：设图G有n个结点 r个最大连通子图 则图G的完全关联矩阵的秩为n－r．