如何证明两个边割集的对称差仍然边割集?
2024-11-27 阅读 18
要证明两个边割集的对称差仍然是边割集，可以按照以下步骤进行证明：
1. 首先，假设图G有两个边割集A和B，即A和B分别是将图G分成两个互不相连的部分的边集。
2. 然后，考虑A和B的对称差，记为A △ B。对称差的定义是A △ B = (A - B) ∪ (B - A)，即A和B中各自独有的边构成的集合的并集。
3. 接下来，我们需要证明A △ B也是一个边割集。也就是说，A △ B将图G分成两个互不相连的部分。
4. 假设A和B将图G分成的两个部分分别为V1和V2，对称差A △ B将图G分成的两个部分分别为V3和V4。
5. 要证明A △ B是一个边割集，需要证明V3和V4是互不相连的。即证明任何一条连接V3和V4的边都属于A △ B。
6. 假设存在一条连接V3和V4的边e不属于A △ B，即e既不在A中也不在B中。那么e必定连接V1和V2，否则e会属于A或B。
7. 但是，由于A是一个边割集，任何连接V1和V2的边都属于A。同理，B也是一个边割集，任何连接V1和V2的边都属于B。因此，不存在连接V3和V4的边e不属于A △ B。
8. 综上所述，A △ B也是一个边割集，证明完成。
通过以上步骤，可以证明两个边割集的对称差仍然是边割集。
更新于 2024年11月28日
