设无向图G是由k（k≥2)棵树组成的森林已知G中有n个结点 m条边．试证明．m=n－k．

大学 2020-06-09 09:01:12 结点,森林已帮助人

设无向图G是由k(k≥2)棵树组成的森林，已知G中有n个结点，m条边．试证明．m=n-k．

难度★★☆ 搜索

证明设G的k个连通分枝为G1，G2，…，Gk，每个Gi有ni个结点mi，条边，i=1，2，…，k．由于G，都是树，有mi=ni-1，i=1，2，…，k．
故 m=∑i=1kmi-∑i=1k(n1-1)=n-k

设无向图G是由k（k≥2)棵树组成的森林 已知G中有n个结点 m条边．试证明．m=n－k．