在图 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]

2022-06-16

在图 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]

答案：

       对应每一条弦有一条基本回路,每一条基本回路中只含一条弦， 其余的边全为树枝.对应每一条树枝有一个基本割集,每一个基本割 集中只含一条树枝,其余的边全为弦.注意回路与割集的不同表示法.(1) 对应弦 [tex=0.857x1.0]tNYtQQjuwJCOoFWZed/ggg==[/tex] 的基本回路为 [tex=2.714x1.214]3/m5Ygdr4Mw9h2gBaaI4cw==[/tex].[br][/br]     对应弦 [tex=0.857x1.0]iB1uBost/kvxcpYUJQ/2SA==[/tex] 的基本回路为 [tex=4.357x1.214]A2NJtI8FKmpBjsTAfQ3j5lmoPJfP7JFCudreOZP8ILE=[/tex]. [br][/br]     对应弦 [tex=0.857x1.0]YCXJHWgYgMSK4SVYp67WLQ==[/tex] 的基本回路为[tex=6.214x1.214]LLXqv56/l1A+wil4KsSEOfKrwf5vNbKyctfpMvsI8p261jycug56BL2ch32vY31q[/tex][br][/br]     对应弦 [tex=0.857x1.0]0w/gQeW34mVjQh6yjx1saA==[/tex] 的基本回路为 [tex=6.214x1.214]OnCRkua8o2y/Pp1ua+Q+Iz5mmbm437huy8fIb3bojUbofHXHDVFJkGsrendjZHja[/tex]     [br][/br]     对应弦 [tex=0.857x1.0]Yf5NO4EryHhUqf0DJmvBCQ==[/tex] 的基本回路为 [tex=4.357x1.214]hY2JY3BGIz+HPiYNfDYlt1ZFVHzO3CcuuebOFgegyLU=[/tex][br][/br] 基本回路系统为 [tex=11.786x1.429]ROaoEkn3C/1nTGFZ65JrLImYsf0O8atswHgu5zS2cZn7kGEjCs8EdI9vz/vdvqwqoP/qouE5cpsHOICmQSyrC+rnonK7IbFvtW7wdl4n7hI=[/tex] [br][/br](2) 对应树枝 [tex=0.857x1.0]rW4/zu0wWjgAfyQpsUK3Pw==[/tex]的基本割集为 [tex=7.571x1.357]zM4Ju4ZOahTy+AcQi1jRuJvX9I3ASKgt2EiA21Oy8Ivf8eI1YsJtYS2E3Fz9eoxkPMwS0FoPvEW4SSbxv9WZDw==[/tex].     对应树枝 [tex=0.857x1.0]NE5viVQtUJ1Z7sNTvKYsYg==[/tex] 的基本割集为 [tex=7.786x1.357]XBSNgCG/JsXYIvF8pDjogCIZGjpM+rHHpQ0oNDHUX9D3Iy9Ye1VCXiKSNAVYns8l8e1/qDHFu/bYAH3E75egoA==[/tex]     对应树枝 [tex=0.857x1.0]d6P6Y012DDZau8aa7mb/8w==[/tex]的基本割集为 [tex=8.0x1.357]kOvXmj33HWf/wH/KGEj8FWn/G7FmqoFfVmG3kg4bWiWZZu1xtlyPP76/y6HKdp49UnK8+vr781HgIjnWbWBO+g==[/tex]     对应树枝 [tex=0.857x1.0]6dNLRHttQ/B0LA9D3Qprog==[/tex] 的基本割集为 [tex=8.0x1.357]Stbk5gc16ZXbf523SXtCpDKNU5xF2ZpgY20IZY/y8fKiucUinClN7/Qq16j7DIitWQfu+8UQbS+qlQum5GSOFg==[/tex]     对应树枝 [tex=1.214x1.0]X6c0eTsYZYKpfv43ZUzT8g==[/tex]的基本割集为 [tex=4.571x1.357]/I8M83GsBF/FnyvE7YE7cisHeYdMXWc7d54/vDiUU7Q=[/tex]基本割集系统为 [tex=11.0x1.429]+o6YKhHbxlvXXaS5I+nI2+s/l8mDdZ1Ddf5i/Z1THSM4k5/D21qbysZqMi100EX1EkaKya1gcGfmtN8BahVabWUdrB1Siwgm3sezXvLb+ZM=[/tex]

举一反三

内容

0
设[tex=0.643x1.0]jLbabU9pW65GUKemsNBJWw==[/tex] 是群 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的非空子集。证明: [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 中与[tex=0.643x1.0]jLbabU9pW65GUKemsNBJWw==[/tex]的每个元素可交换的元素构成[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 的子群。
1
无向图 [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]
2
给定图[tex=4.0x1.357]yW/Sa0HYYSgWDqqktERSvSBe7S4aZr6ltchCYx0qg+4=[/tex]，如图6.11所示.[img=278x348]17863899051b602.png[/img]（1）在[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]中找出一条长度为7的通路；（2）在[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]中找出一条长度为4的简单通路；（3）在[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]中找出一条长度为4的简单回路.
3
树 [tex=0.643x1.0]iollMFTzm3iqFEHRyKQe1A==[/tex] 如图 16.18 所示. 回答以下问题.(1) [tex=0.643x1.0]iollMFTzm3iqFEHRyKQe1A==[/tex] 是几叉树?(2) [tex=0.643x1.0]iollMFTzm3iqFEHRyKQe1A==[/tex]的树高为几?(3) [tex=0.643x1.0]iollMFTzm3iqFEHRyKQe1A==[/tex] 有几个内点?(4) [tex=0.643x1.0]iollMFTzm3iqFEHRyKQe1A==[/tex]有几个分支点?[img=273x205]17926ce3f0ebfd1.png[/img]
4
无向图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]是欧拉图，当且仅当[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]满足下面4个条件中的哪一个？（1）[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的所有结点的次数为偶数；（2）[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的所有结点的次数为奇数；（3）[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]连通且所有结点的次数为偶数；（4）[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]连通且所有结点的次数为奇数.