命题“若 [tex=1.214x1.071]XUYOLSDZxfQs8dKdxxKfFw==[/tex]为无向图 6 的最大点独立集,则 [tex=1.214x1.071]XUYOLSDZxfQs8dKdxxKfFw==[/tex]也是 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的最小支配集”为真吗?为什么?
举一反三
- 设[tex=1.214x1.071]7DwFMljnmNxjtKf8fSxG1A==[/tex]为平面图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的对偶图, [tex=1.571x1.071]gEKcCVI33pHSbZsmJNvZAQ==[/tex]是 [tex=1.214x1.071]7DwFMljnmNxjtKf8fSxG1A==[/tex]的对偶图,在什么情况下, [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]与 [tex=1.571x1.071]gEKcCVI33pHSbZsmJNvZAQ==[/tex]一定不同构?
- 下图所示平面图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的对偶图[tex=1.214x1.071]7DwFMljnmNxjtKf8fSxG1A==[/tex]，再求[tex=1.214x1.071]7DwFMljnmNxjtKf8fSxG1A==[/tex]的对偶图[tex=1.571x1.071]Ok2FrCkkaU9lU74rvuu8jg==[/tex]，[tex=1.571x1.071]Ok2FrCkkaU9lU74rvuu8jg==[/tex]与[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]同构吗？[img=167x154]179413ec0103bb0.png[/img]
- 求图 18.10所示的无向图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 的两个极大点独立集 一个最大点独立集及点独立数 [tex=0.929x1.214]DgO1Rmtans/V1jp3Na3K1w==[/tex].[br][/br][img=284x194]179283341146073.png[/img]
- 设 [tex=0.643x1.0]jLbabU9pW65GUKemsNBJWw==[/tex] 为无向连通图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 的一个边割集,证明 [tex=2.786x1.143]jMAYbh8you1a6SvAPIb1IA==[/tex] 不含 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的生成树.
- 证明:平面图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的对偶图 [tex=1.214x1.071]7DwFMljnmNxjtKf8fSxG1A==[/tex] 是欧拉图当且仅当 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]中每个面的次数均为偶数.