• 2022-06-04
    二部图 [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]
  •     在图 18.29 中,[tex=0.857x1.0]kV0D+PJHG/C/5rltbVNBOQ==[/tex] 与[tex=0.857x1.0]z1WgSpi7t4Cme8y5zX37vg==[/tex] 均只与[tex=0.929x1.0]f4h7jfFIT6S+sXz3wobTtw==[/tex]相邻,由此就破坏了相异性条件,因而无完备匹配. [tex=13.5x1.357]c+nMk3Co5ByB59+PkVA5CK/BLyKGyDauyBOee4loR71CqrJg4JD8Lj9mPQxEcKRticROhvpzAcZL1KMBj3EYk5BMlrjHUNjzp1Pq4/9f+j1jl/Ja3XpqldRBTU0FkbRgb7XjKrO6Aw0Av9maoaNjnA==[/tex]为 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 中的一个最大匹配, 因而 [tex=2.5x1.214]WJVpPzZK+y7NW9nX8F8hJA==[/tex]

    举一反三

    内容

    • 0

      无向图 [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]

    • 1

      设二部图 [tex=7.5x1.214]owi8k6PAnrn6UxDb9Vv8U9MLbm7Dtz7QCpysp6HC7zw=[/tex] 为 [tex=0.571x1.0]rFc/sfAAuCOtzhevhoREeA==[/tex]-正则图,证明 : [tex=0.786x1.0]AE39d9jt5lmaK/QknwwnQQ==[/tex]中存在完美匹配,其中[tex=2.643x1.143]cfaqtnyliryf7/MzE4dm3ZjOyK4nZ3Dw+cBIlNgbU3o=[/tex]

    • 2

        设 9 阶无向图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 中,每个顶点的度数不是 5 就是 6, 证明 : [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 中至少有 5 个 6 度顶点或至 少有 6 个5 度顶点.

    • 3

      给定平面图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]如图6.17所示,平面图的面数是(      ).[img=355x220]178646b659a6f03.png[/img] 未知类型:{'options': ['6', '5', '8', '9'], 'type': 102}

    • 4

      图 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] 的所有基本割集.