问答题
设G是图，无回路，但若外加任意一条边于G后，就形成一回路，试证明G必为树．
【正确答案】
根据所给条件，知G的任意两点v
1
和v
2
间均存在通路，故图G是连通图，即v
1
与v
2
间有一条简单通路P
1
，但如果加入一条边后形成回路，即形成第2条简单通路P
2
，因此可知G中任意两个结点间存在唯一的通路，此结论符合树的定义，即图G必为树．
【答案解析】
提交答案
关闭