证明图 17.3( a )所示的平面图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 不是极大平面图.[br][/br][img=216x203]17926ec86595cbe.png[/img]
举一反三
- 通过求图 18.8( b ) 所示的平面图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 的对偶图 [tex=1.214x1.071]7DwFMljnmNxjtKf8fSxG1A==[/tex] 的点色数 [tex=2.786x1.357]/UVkJJ09X8toH7lTCx3hcHXYt0nV8fQE2Nyr4WYFsYU=[/tex], 求[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的面色数 [tex=2.786x1.357]/UVkJJ09X8toH7lTCx3hcHXYt0nV8fQE2Nyr4WYFsYU=[/tex].[br][/br][img=226x169]179282d1f7b350c.png[/img]
- 证明图17.15所示的两个图都是极大平面图.[br][/br][img=427x231]179270c00f99c61.png[/img]
- 图 18.11 所示的无向图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]有完美匹配吗? 为什么?[br][/br][img=314x185]17928377d282ce5.png[/img]
- 求图 18.11 所示的无向图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 的两个极大匹配、一个最大匹配及匹配数[tex=0.929x1.214]3GPaN3IuVXVR7YWpWML8Wg==[/tex].[br][/br][img=314x185]1792836816dec51.png[/img]
- 二部图[tex=7.5x1.214]owi8k6PAnrn6UxDb9Vv8U9MLbm7Dtz7QCpysp6HC7zw=[/tex]如图 18.27所示. 证明 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 中存在完备匹配,并找出[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 中所有不同的 完备匹配.[br][/br][img=310x208]179288576360f4a.png[/img]