无向图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 如图 18.4所示.(1) 给出 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 的一个非最大匹配的极大匹配 [tex=1.357x1.214]QcSZflolD/TZzu4WluEs9g==[/tex].(2) 求(1) 中给出的 [tex=1.357x1.214]QcSZflolD/TZzu4WluEs9g==[/tex] 的一条可增广的交错路径 [tex=0.643x1.0]MEgqm6iWtfwwGGtWVl2Eng==[/tex].(3) 由(2)中给出的 [tex=0.643x1.0]MEgqm6iWtfwwGGtWVl2Eng==[/tex] 产生一个边数更多的匹配 [tex=1.0x1.0]0KCelhZna0R9EGhYF1VZHA==[/tex].(4) [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]中存在完美匹配吗? 为什么?[br][/br][img=256x175]179281f4e015d48.png[/img]
举一反三
- 设二部图 [tex=13.929x1.357]h20eAWbQrta/ABU0cRM/li/VpGQfGN8S6sjciqZJj7uKwyHK5FyymT/xt9ZZXgErIFqqAHt4vN8VxaN1a0lXGzGSabglRIOehOO3gGYxU/s=[/tex] 为 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 中一个匹配,[tex=0.643x1.0]u7XUci3hWIE/S+TBToDPxA==[/tex]为一条 [tex=1.0x1.0]0KCelhZna0R9EGhYF1VZHA==[/tex]可增广的交错路 径, [tex=1.0x1.0]0KCelhZna0R9EGhYF1VZHA==[/tex] 能是 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]中 [tex=0.643x1.0]jro2X/cRz2SsmjZvcOdvsQ==[/tex]到 [tex=0.643x1.0]jro2X/cRz2SsmjZvcOdvsQ==[/tex], 的完备匹配吗?为什么?
- 二部图[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]
- 二部图 [tex=7.5x1.214]owi8k6PAnrn6UxDb9Vv8U9MLbm7Dtz7QCpysp6HC7zw=[/tex] 如图 18.29 所示. 证明[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 中不存在完备匹配，找出 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]中的一个最大匹配,并求匹配数 [tex=0.929x1.214]3GPaN3IuVXVR7YWpWML8Wg==[/tex].[img=302x192]1792889287b48d9.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] 的所有基本割集.
- 在图 16.8 所示的无向图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 中,实线边的导出子图为 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 的生成树 [tex=0.643x1.0]iollMFTzm3iqFEHRyKQe1A==[/tex].(1) 求 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 对应 [tex=0.643x1.0]iollMFTzm3iqFEHRyKQe1A==[/tex] 的基本回路与基本回路系统.(2) 求 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 对应[tex=0.643x1.0]iollMFTzm3iqFEHRyKQe1A==[/tex] 的基本割集与基本割集系统.[img=255x246]17921866e94484e.png[/img]