讨论[tex=1.214x1.214]kFXZ1uR8GjycbJx+Ts2kyQ==[/tex] 与 [tex=1.214x1.214]6WSs2HoeTjDhtmqTp8KAgA==[/tex] 各有几个非同构的生成子图是正则图.
在 [tex=0.643x0.786]/he/ol8BkDuTTL9yMPtH4Q==[/tex] 阶 [tex=0.571x1.0]rFc/sfAAuCOtzhevhoREeA==[/tex]-正则图中, [tex=5.857x1.143]FMMMqj3oap9WEUMkJHkVMsWdYCd96FTtS8LhmLfjgYc=[/tex]当 [tex=0.643x0.786]/he/ol8BkDuTTL9yMPtH4Q==[/tex] 为奇数时,由握手定理的推论可知, [tex=0.571x1.0]rFc/sfAAuCOtzhevhoREeA==[/tex]只能取[tex=3.214x1.143]CYc0v78aphekC019PwzDSQ==[/tex]中的偶数; 当[tex=0.643x0.786]/he/ol8BkDuTTL9yMPtH4Q==[/tex] 为偶数时, [tex=0.571x1.0]rFc/sfAAuCOtzhevhoREeA==[/tex] 可以取 [tex=3.214x1.143]CYc0v78aphekC019PwzDSQ==[/tex]中的任何值. 在讨论 [tex=1.214x1.214]kFXZ1uR8GjycbJx+Ts2kyQ==[/tex] 与 [tex=1.214x1.214]6WSs2HoeTjDhtmqTp8KAgA==[/tex]的非同构的正则生成子图时,除了注意以上的讨论外,还应该注意, 同一个 [tex=0.571x1.0]rFc/sfAAuCOtzhevhoREeA==[/tex] 可能产生多个非同构的正则生成子图.对于 [tex=1.214x1.214]kFXZ1uR8GjycbJx+Ts2kyQ==[/tex]来说,由于阶数 [tex=0.643x0.786]/he/ol8BkDuTTL9yMPtH4Q==[/tex] 为奇数,所以 [tex=0.571x1.0]rFc/sfAAuCOtzhevhoREeA==[/tex] 只能取 3 个值:0,2,4 . 对应的正则生成子图分别由图 14.1 中 ( a ),( b ),( c ) 所示.其中 ( a ) 为 0 -正则图,( b ) 为 2- 正则图, ( c ) 为 4 -正则图. 不难看出 ( a )与( c ) 互为补图,而 ( b ) 是自补图.[img=446x192]17916aba3535cbc.png[/img][br][/br] 对于 [tex=1.214x1.214]6WSs2HoeTjDhtmqTp8KAgA==[/tex]来说,由于阶数为偶数,所以 [tex=0.571x1.0]rFc/sfAAuCOtzhevhoREeA==[/tex]可取 6 个值: 0,1,2,3,4,5 . 对应的正则生成子图分别由 图 14.2 中[tex=3.5x1.357]ucHBXaCtTgKLnTyqond9vZhWWRyluoEIqeF9rY9m7Q8=[/tex]所示.其中 ( a ) 为 0 -正则图,( b ) 为 1 -正则图,(c) 与 ( d ) 均为 2 -正则图, ( e ) 与(f)为 3-正则图, ( g ) 为 4 -正则图, ( h )为 5 -正则图. ( a )与 ( h ) 互为补图, ( b ) 与 ( g ) 互为补图, ( c ) 与(e) 互为补图,(d)与 ( f )互为补图.在这里,2-正则图与 3-正则图均各有两个是非同构的.[img=618x318]17916ad8e8e696d.png[/img]
举一反三
- [tex=1.214x1.214]kFXZ1uR8GjycbJx+Ts2kyQ==[/tex]$的非同构的生成子图中有[input=type:blank,size:6][/input]个是生成树.
- 画出 [tex=1.214x1.214]kFXZ1uR8GjycbJx+Ts2kyQ==[/tex]的 3 条边的所有非同构的子图.
- 6个顶点11条边的所有非同构的连通的简单非平面图有[tex=2.143x2.429]iP+B62/T05A6ZTM0eeaWiQ==[/tex]个,其中有[tex=2.143x2.429]ndZSw3zT0QTOVLVdoUto1Q==[/tex]个含子图[tex=1.786x1.286]J+vVZa2YaMpc6mJBbqVvWw==[/tex],有[tex=2.143x2.429]lmhx48evnQMhi03NovPXig==[/tex]个含与[tex=1.214x1.214]kFXZ1uR8GjycbJx+Ts2kyQ==[/tex]同胚的子图。供选择的答案[tex=3.071x1.214]3KinXFh3SXhZ7nIe1y9KEV6aadxhhJWeEy6Dij1iObdMUZkY6ZA5J2dVVjPSuhEf[/tex]:(1) 1 ;(2) 2 ;(3) 3 ; (4) 4 ;(5) 5 ;(6) 6 ; (7) 7 ; (8) 8 。
- 画出[tex=1.214x1.214]styqSQYCkugnlIKncQ1URw==[/tex]的所有非同构的子图,其中有几个是生成子图?生成子图中有几个是连通图?
- 求出[tex=1.214x1.214]6WSs2HoeTjDhtmqTp8KAgA==[/tex]中所有不同构的生成树。
内容
- 0
[tex=0.5x1.286]w9szX5MVVkKzPTQtDmrYaA==[/tex]阶完全无向图[tex=1.214x1.214]aPxICcmXlww7Mb0P6jOgjw==[/tex]的不同构的生成子图有( )。 A: 2 B: 3 C: 4 D: 5
- 1
[tex=1.214x1.214]u7MAYAh9dMKxy9pMW1L19A==[/tex]有多少种非同构的子图?
- 2
试画出[tex=1.214x1.214]X8Rbq++N1XqLSVSencwbCA==[/tex](4阶无向简单完全图)的所有非同构的生成子图.
- 3
给下列各图的顶点用尽量少的颜色着色.[br][/br]6 阶完全图 [tex=1.214x1.214]6WSs2HoeTjDhtmqTp8KAgA==[/tex]
- 4
无向完全图 [tex=1.214x1.214]styqSQYCkugnlIKncQ1URw==[/tex]的非同构的连通的生成子图共有[input=type:blank,size:4][/input]个.