割边的性质 定理3.1.1:e=(u,)是割边,当且仅当e不属于G的任何“初级回路”。 必要性→:e=(u,v)是割边→e不属于G的任何“初级回路”。反证法。 若e=(u,v)属于G的某个“初级回路”,则G=G-e中仍存 在u到v的“初级道路”,故结点和v属于同一连通支,e不是 割边。 充分性←:e不属于G的任何“初级回路”→e=(w,v)是割边。反证法。 若e不是割边,则G'=G-e与G的连通支数一样。于 是u和v仍属于同一连通支。故G中存在初级道 路P(w,v),P(u,v)+e就是G的一个“初级回路”。 0Q0 刘胜利(上海交大-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
割边的性质 定理3.1.1:e=(u,)是割边,当且仅当e不属于G的任何“初级回路”。 必要性=:e=(u,v)是割边→e不属于G的任何“初级回路”。反证法。 若e=(u,v)属于G的某个“初级回路”,则G=G-e中仍存 在u到v的“初级道路”,故结点和v属于同一连通支,e不是 割边。 充分性←:e不属于G的任何“初级回路”→e=(w,v)是割边。反证法。 若e不是割边,则G'=G-e与G的连通支数一样。于 是u和v仍属于同一连通支。故G中存在初级道 路P(u,),P(u,v)+e就是G的一个“初级回路”。 口年 0Q0 刘胜利(上海交大-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
树的等价定义 定理3.1.2:设T是结点数为n≥2的树,则下列性质等价: (1)图T连通且无“初级回路”: 2图T连通且每条都是到边: 3)图T连通且有1-1条边: 4图有一1条边且元切回路 图订的任童两结点间有附一初级恒路 圆无初级回智,但在任两结点间加上一条边后哈有一 个初级回品 刘胜利(上海交大-CS实验到 图论第三章:树 511
ä✛✤❞➼➶ ➼♥3.1.2➭✗T➫✭✿ê➃n ≥ 2✛ä➜❑❡✎✺➓✤❞➭ (1) ãTëÏ❹➹“Ð❄↔➫”➯ (2) ãTëÏ❹③❫Ñ➫⑧❃➯ (3) ãTëÏ❹❦n − 1❫❃➯ (4) ãT❦n − 1❫❃❹➹“Ð❄↔➫”➯ (5) ãT✛❄➾ü✭✿♠❦➁➌“Ð❄✗➫”➯ (6) ãT➹“Ð❄↔➫”➜✂✸❄ü✭✿♠❭þ➌❫❃❚❦➌ ❻“Ð❄↔➫”✧ ✹➅⑤ (þ➦✂➀-CIS➣✟➾) ãØ✶♥Ù:ä 5 / 1
树的等价定义 定理3.1.2:设T是结点数为n≥2的树,则下列性质等价: (1)图T连通且无“初级回路”; (2)图T连通且每条都是割边: 3)mT连通且有1一1条边: 4)世T有一1条边且无“初级回路: 世的任垂两结点间有附一切级痘路 同面无初级回,但在任两结点间加上一条边后哈有一 个河明回品 刘胜利(上海交大-CS实验到 图论第三章:树 511
ä✛✤❞➼➶ ➼♥3.1.2➭✗T➫✭✿ê➃n ≥ 2✛ä➜❑❡✎✺➓✤❞➭ (1) ãTëÏ❹➹“Ð❄↔➫”➯ (2) ãTëÏ❹③❫Ñ➫⑧❃➯ (3) ãTëÏ❹❦n − 1❫❃➯ (4) ãT❦n − 1❫❃❹➹“Ð❄↔➫”➯ (5) ãT✛❄➾ü✭✿♠❦➁➌“Ð❄✗➫”➯ (6) ãT➹“Ð❄↔➫”➜✂✸❄ü✭✿♠❭þ➌❫❃❚❦➌ ❻“Ð❄↔➫”✧ ✹➅⑤ (þ➦✂➀-CIS➣✟➾) ãØ✶♥Ù:ä 5 / 1
树的等价定义 定理3.1.2:设T是结点数为n≥2的树,则下列性质等价: (1)图T连通且无“初级回路”; (2)图T连通且每条都是割边: (3)图T连通且有n-1条边: 4世T有一1条边且无切级回路”: 5)面T的任充两结点间有唯一“初级道路: 同面无初级回,但在任两结点间加上一条边后哈有一 个“初回路 刘胜利(上海交大-CS实验到 图第三章:树 511
ä✛✤❞➼➶ ➼♥3.1.2➭✗T➫✭✿ê➃n ≥ 2✛ä➜❑❡✎✺➓✤❞➭ (1) ãTëÏ❹➹“Ð❄↔➫”➯ (2) ãTëÏ❹③❫Ñ➫⑧❃➯ (3) ãTëÏ❹❦n − 1❫❃➯ (4) ãT❦n − 1❫❃❹➹“Ð❄↔➫”➯ (5) ãT✛❄➾ü✭✿♠❦➁➌“Ð❄✗➫”➯ (6) ãT➹“Ð❄↔➫”➜✂✸❄ü✭✿♠❭þ➌❫❃❚❦➌ ❻“Ð❄↔➫”✧ ✹➅⑤ (þ➦✂➀-CIS➣✟➾) ãØ✶♥Ù:ä 5 / 1