设 [tex=3.571x1.357]WaOswwJAfJRrihXUrEIoCw==[/tex] 为无向图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]中一桥,证明 : [tex=0.643x0.786]QJxUxhssyKBmvelFWUbYJA==[/tex]是割点当且仅当 [tex=0.643x0.786]QJxUxhssyKBmvelFWUbYJA==[/tex]不是悬挂顶点.
举一反三
- 设 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 是简单图, 证明 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 是完全图当且仅当 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 有 [tex=2.857x2.214]jcCMHflCR8OS9TosV6N5vMuPmF8DXSHKmIKBnV2ExTOzIbKHOfak9FzzxRS+B78HS9CqeTlpcCcUdpM7q4bAOg==[/tex] 条边.
- 设[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]为[tex=3.857x1.357]7yjEVpVC7tVINCzkFztTGVbuXZ3jOK3XAi9UtkSNhqs=[/tex]阶无环图，证明：[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]是二部图当且仅当它是[tex=1.286x1.143]BqWWrIAXV20ROwXkNnp+KQ==[/tex]可着色的。
- 设[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是带有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点的简单图。证明：[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是树当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]没有简单回路并且有[tex=1.929x1.143]odTH0p5clPZMk1jQf4ctjw==[/tex]条边。
- 设[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是带有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点的简单图。证明：[br][/br][tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是树当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是连通的并且有[tex=1.929x1.143]odTH0p5clPZMk1jQf4ctjw==[/tex]条边。
- 证明：若无向图[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]恰有两个节点[tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex]和[tex=0.5x0.786]pmD1JbahT9zMRAbBNi045A==[/tex]度数为奇数，则在[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]中[tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex]可达[tex=0.5x0.786]pmD1JbahT9zMRAbBNi045A==[/tex]。如果[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]是有向图，上述结论是否成立？