求图 18.10所示的无向图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 的两个极大点独立集 一个最大点独立集及点独立数 [tex=0.929x1.214]DgO1Rmtans/V1jp3Na3K1w==[/tex].[br][/br][img=284x194]179283341146073.png[/img]
举一反三
- 求图 18.11 所示的无向图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 的两个极大匹配、一个最大匹配及匹配数[tex=0.929x1.214]3GPaN3IuVXVR7YWpWML8Wg==[/tex].[br][/br][img=314x185]1792836816dec51.png[/img]
- 图 7 中所示的无向图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 中.实线边所表示的子图为 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 的一棵生成树 [tex=0.643x1.0]iollMFTzm3iqFEHRyKQe1A==[/tex].[br][/br][img=302x171]1793b6fae3bc619.png[/img][br][/br]求 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]对应 [tex=0.643x1.0]iollMFTzm3iqFEHRyKQe1A==[/tex] 的所有基本割集.
- 命题“若 [tex=1.214x1.071]XUYOLSDZxfQs8dKdxxKfFw==[/tex]为无向图 6 的最大点独立集,则 [tex=1.214x1.071]XUYOLSDZxfQs8dKdxxKfFw==[/tex]也是 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的最小支配集”为真吗?为什么?
- 无向图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 如图 14.11 所示.(1) 求 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 的全部点割集和边割集，并指出其中的割点和桥(割边).(2) 求 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的点连通度 [tex=2.143x1.357]uxD1UPZJzwR5dyB53LAngg==[/tex] 和边连通度 [tex=2.214x1.429]tBQwnmV6DKXWSWeLfYxUSXY1Kh8jI/ka61DFKw8ydmA=[/tex].[img=257x170]17920459ee08cc6.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]