当且仅当G的一条边e不包含在G的闭迹中时,e才是G的割边。

发布网友发布时间：2023-06-24 06:24

共1个回答

热心网友时间：2024-11-30 00:35

【答案】：必要性,设边e是G的割边,边e关联的两个结点为u,v。若边e包含G的一个闭迹中,则除边e=(u,v)外还有别的以u,v为端点的路，故去掉边e后，G仍是连通的，这与边e是割边矛盾。
充分性,若边e不包含在G的任一闭迹中,那么连接结点的只有边e，而不会有其他连接u和v的任何路。因为若连接u和v还有不同与边e的路,则此路与边e就组成了一条包含边e的闭迹,从而导致矛盾。所以,去掉边e后，u和v就不连通,故边e是割边。
注:本题所用知识点:判断制边的充要条件,删去该边后,原图不连通。

声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com