命题“若 [tex=1.214x1.071]XUYOLSDZxfQs8dKdxxKfFw==[/tex]为无向图 6 的最大点独立集,则 [tex=1.214x1.071]XUYOLSDZxfQs8dKdxxKfFw==[/tex]也是 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的最小支配集”为真吗?为什么?

2022-05-27

命题“若 [tex=1.214x1.071]XUYOLSDZxfQs8dKdxxKfFw==[/tex]为无向图 6 的最大点独立集,则 [tex=1.214x1.071]XUYOLSDZxfQs8dKdxxKfFw==[/tex]也是 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的最小支配集”为真吗?为什么?

答案：

      命题不为真.定理 18.1 说 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的极大点独立集都是[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 的极小支配集，但最大点独立集 不一定 是最小支配集，[tex=0.929x1.214]DgO1Rmtans/V1jp3Na3K1w==[/tex] 不一定等于 [tex=0.929x1.0]/PO8Y9+ipwiWZIKSqWU0Kg==[/tex].图 18.2给出一棵 8 阶树，此类树也称星形图.图中 有 2 个极大点独立集, [tex=12.857x1.357]ufVMqHSiAntsSHtm4b6WouXrSYcwMNG+9BI0C5aLoCdjIKEpreIpQJyKdAYYs2FumInKRt14C3t7nFx0z2ukUmqzQG+jlXC4m3OCKuARc+eVngLgvClRp8z2a28YqOXW[/tex],其中 [tex=1.214x1.357]ncQUPsnNICKJ1N1VUoBctA==[/tex]是最大点独立集，但不是最小支配集，它只是极小支配集. [tex=1.214x1.357]QeCZ94eANrAdJE7Jy/m8Lg==[/tex]是最小支配集，但只是极大点独立集，而不是最大点独立集.[tex=4.786x1.214]jZb7QgVF9e95uRJPXjRH9c4mbk37bqxE5BapwxVm2Tk=[/tex].

举一反三

内容

0
设 [tex=1.214x1.071]q6yilpXXTPX9Lcn+AOy/3Q==[/tex]是具有 [tex=3.143x1.357]f7PdaG8M9x9Aazk5vJIjurlpUXRbzj423Fbwl62lwGs=[/tex]个连通分支的平面图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的对偶图,已知 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的边数 [tex=2.714x1.0]nY7qCv1RY8R8j/Iu1HwN4A==[/tex], 面数 [tex=1.786x1.0]Gz4GRLLzFj014/8HSjWhJg==[/tex],求[tex=1.214x1.071]q6yilpXXTPX9Lcn+AOy/3Q==[/tex]的面数 [tex=0.929x1.071]hYOA3pDT8+Ve3xn1VB+3XA==[/tex].
1
证明当[tex=0.786x1.0]mfjRqhorWjKnT4vuQia3hQ==[/tex]是[tex=1.214x1.071]ERAYMLhAZTY9mDX0C5cJmQ==[/tex]中的不可数无穷点集时，[tex=1.071x1.143]g0IbrHa9ffhybTQXy4CAubbbHMTCiuTu1wV7RGCxDd0=[/tex]不可能是有限集.
2
(1) 设[tex=1.143x1.214]dR9jxhXF4eOBq39r4zKh9g==[/tex]与[tex=1.143x1.214]1b46y//cjGpQ43dW216vJA==[/tex]是两个平面图，若[tex=3.643x1.571]qTl+oasCr3T9IVJ+KgQZSZEdxxhD9K1gmiQ9VkVcO1E=[/tex]，它们的对偶图[tex=3.714x1.571]hTXLrYla6i91O01NvB1/8D7Gxn/bkWEHgwnrfnghRks=[/tex]。这个命题为[tex=2.143x2.429]rVbjoKgaBYChmT2nPEBA4Q==[/tex]。(2) 任何平面图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的对偶图[tex=1.214x1.071]7DwFMljnmNxjtKf8fSxG1A==[/tex]的对偶图[tex=1.571x1.071]gEKcCVI33pHSbZsmJNvZAQ==[/tex]与[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]同构。这个命题为[tex=2.143x2.429]ndZSw3zT0QTOVLVdoUto1Q==[/tex]。(3) 任何平面图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的对偶图[tex=1.214x1.071]7DwFMljnmNxjtKf8fSxG1A==[/tex]的面数[tex=0.929x1.071]IBNH4jjhZIn6t7n7W9WcfQ==[/tex]都等于[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的顶点数[tex=0.643x0.786]h6IfGOxBlahC8le5jX4WiA==[/tex]。这个命题为[tex=2.143x2.429]lmhx48evnQMhi03NovPXig==[/tex]。供选择的答案[tex=0.786x1.0]Yn3GgEZev6SOu2r4v1WnCw==[/tex]、[tex=0.786x1.0]ri6gmnf1+J9dGqG5/1sV6A==[/tex]、[tex=0.714x1.0]J/aA9EEo0KmJFnWWfX7LmQ==[/tex]：(1) 真；(2) 假。
3
若无向图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]为欧拉图,证明: [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]中无桥.
4
设[tex=1.071x1.143]SEwIem1RXUAaU4aCzKG5tQ==[/tex]和[tex=1.071x1.143]/kl5SQf6O9fsMGHhcDhR+g==[/tex]分别为无向连通图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的点割集和边割集。[tex=1.857x1.143]OkM2URLKcUuB+lJJBopihg==[/tex]的连通分支个数一定为几？[tex=2.643x1.286]jhfTeztVboi83zj5AJ3iVQ==[/tex]的连通分支数也是定数吗？