割边的性质 定理3.1.1：e=(u,)是割边，当且仅当e不属于G的任何“初级回路”。 必要性=：e=(u,v)是割边→e不属于G的任何“初级回路”。反证法。 若e=(u,v)属于G的某个“初级回路”，则G=G-e中仍存 在u到v的“初级道路”，故结点和v属于同一连通支，e不是 割边。 充分性=：：不漏于G的任何“初级回路”一=“，是割边。反证法 若不是割边，则G=G一：与G的连通支数一样于 是：和仍属于同一连通支。故G中存在初级道 路P(4,),Pu,)+e就是G的一个“初级回路 刘胜利（上海交大-CS实验到 图论第三章：树 41⑧❃✛✺➓ ➼♥3.1.1➭e = (u, v)➫⑧❃➜✟❹❂✟eØá✉G✛❄Û“Ð❄↔➫”✧ ✼❻✺⇒➭ e = (u, v)➫⑧❃⇒eØá✉G✛❄Û“Ð❄↔➫”✧ ❻②④✧ ❡e = (u, v)á✉G✛✱❻“Ð❄↔➫”➜❑G 0 = G − e➙❊⑧ ✸u✔v✛“Ð❄✗➫”➜✙✭✿uÚvá✉Ó➌ëÏ⑤➜eØ➫ ⑧❃✧ ➾➞✺⇐➭ eØá✉G✛❄Û“Ð❄↔➫”⇒ e = (u, v)➫⑧❃✧ ❻②④✧ ❡eØ➫⑧❃➜❑G 0 = G − e❺G✛ëÏ⑤ê➌✘✧✉ ➫uÚv❊á✉Ó➌ëÏ⑤✧✙G 0➙⑧✸Ð❄✗ ➫P(u, v)➜P(u, v) + eÒ➫G✛➌❻“Ð❄↔➫”✧ ä✹✛➅⑤③(❫þ➦❃✂➀➜-CISÑ➣✟Ø➾➡) á✉❄Û“Ðã❄Ø✶↔♥Ù➫:ä”✧↕➧ä✛③❫❃Ñ➫⑧❃✧4 / 1