设 [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]不是悬挂顶点.

2022-06-04

设 [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.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 是割点,下面证明 [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 不是悬挂顶点(即 1 度顶点).若 [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 是悬挂顶点, [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex]只关联桥[tex=0.5x0.786]rCTQ93hYjIOF3vc8FasIqg==[/tex],将[tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 从 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 中删除,只从[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 中去掉了 [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 及 [tex=0.5x0.786]rCTQ93hYjIOF3vc8FasIqg==[/tex], 并不产生新的连通分支, 即 [tex=6.286x1.357]Hwp4K0q+PusqdaZWsKEKXQ==[/tex], 这与 [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 是割点相矛盾. [br][/br]     若 [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 不是悬挂顶点,下面证明 [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex]是割点. [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 不是悬挂顶点,因而 [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 除与桥 [tex=0.5x0.786]rCTQ93hYjIOF3vc8FasIqg==[/tex]关联外,还至少与 另外一条边关联.不妨设除 [tex=0.5x0.786]pmD1JbahT9zMRAbBNi045A==[/tex] 外, [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex] 还与 [tex=9.214x1.357]fkKyYDoZSqhaMXNqW13RZ/P9WkeVBZ57+HB7d6SMMoA0yftZZxLj1+MIBGz/16Ac[/tex]相邻,于是 [tex=2.143x1.143]hZON16w66deTdcgBXVGyHg==[/tex]至少产生一个新的连通分支, 即 [tex=6.857x1.357]Vwq3LJhiFYTV9QrWaylMiQ==[/tex], 所以 [tex=0.643x0.786]dFKQavWFzybe6S1GPVXNhQ==[/tex]是割点.

举一反三

内容

0
设 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex] 是 [tex=0.643x0.786]/he/ol8BkDuTTL9yMPtH4Q==[/tex] 阶无向简单图, [tex=2.5x1.143]WHvOziYYJdz0BFGLmQB/8g==[/tex]且为奇数,证明 : [tex=0.786x1.0]AE39d9jt5lmaK/QknwwnQQ==[/tex] 与 [tex=0.786x1.143]3go8UcZXyYUwPOwYloc1nw==[/tex]中奇度顶点的个数相等.
1
若无向图 [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]为欧拉图,证明: [tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]中无桥.
2
设[tex=0.857x1.0]+NBI8Pm2vVS+bGgOpHKyOA==[/tex]是群[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的一个子群，证明：[tex=0.857x1.0]+NBI8Pm2vVS+bGgOpHKyOA==[/tex]是[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的特征子群，当且仅当对[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]的每个自同构[tex=0.571x0.786]G/buLKOLYVDEKMZ76t752w==[/tex]都是[tex=3.786x1.357]/hUAIv2XJLX3YXBqW5nP/A==[/tex].
3
设 [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]的生成树.
4
设[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]为无向连通图，有[tex=0.643x0.786]/he/ol8BkDuTTL9yMPtH4Q==[/tex]个结点，那么[tex=0.786x1.0]LyvDGollVJ+xwurtsLcn0g==[/tex]中至少有几条边？为什么？若是有向图又如何？