带宽为｜G｜-2的连通图个数
- 格式：pdf
- 大小：764.60 KB
- 文档页数：5
第34卷第3期
2018年5月齐齐哈尔大学学报（自然科学版）
Journal of Qiqihar University(Natural Science Edition)Vol.34,
No.3
May,2018
带宽为|G
|-2的连通图个数
陆锋
(湄洲湾职业技术学院，福建莆田
351254)
摘要：通过考虑带宽为
|G|-2的图的补图结构和补图边数的取值范围，运用拆分数知识得到了带宽为
|G|-2的连
通图
G个数的计数公式。
关键词：带宽；极图；拆分数
中图分类号：
O29 文献标志码：
A 文章编号：
1007-984X(2018)03-0072-04
首先介绍几个将用到的引理和定义。
定义1 [1] «为正整数，若…，〜满足：（1)« = «!+«2 +…+ ;( 2 ) q。
贝_«15«2为正整数《的一个左拆分，其中(1
S
S幻称为该左拆分的分量。《的左拆分的个数称
为左拆分数，记为^ («)。《的所有拆分（々取遍所有可能的值）的个数称为《拆分数。
引理1[1]设(«)为正整数《的左拆分数，则户2(«):
引理2[1]设巧(《)为正整数《的3拆分数，贝
IJP3(«):n
1
n2 + 3
12，
j_
n」表示不大于
n的最大整数。
定义2 记
n(A灼为^个点上带宽为
S的不同构的简单连通图个数。
■ k 3i+r
定理1 ( 1)若户=3
k + r(1
Ijn(户，户一2)=玄
ZA(3
k +
r)-2 ;
i=0j=1
k 3i
(2
)若户= 3
k(1<
k)，贝
Ijn(凡户一2)=玄艺户
7.(3/)-1。
i=1 j=1
证明：（1)当户= 3
k +
r(1<
k,1
Sr<2)时，由参考文献[2]中定理3.2知道，对于
e(凡户-2)的极图（即
边数最小的连通图）的边数
e(户，户-2) = |^
j-^ + 1。则完全图尤^是
e(户，户-2)唯一的极图。所以在完全
图中删去任意一条边所得图的带宽为|
G|-2。可以确定满足
B(
G) = |
G|-2连通图边数的最大值抓(户，户-2)
:
max{||
G||: |
G| = ^
S(
G)=户-2，
G是连通的} = P(
P-1) -1。由以上可知对于带宽为|
G| - 2的连通图，其补图
2
5的边数为1
下面证明对于5有如下性质：
①若风
G) =
p-2,
G»-
rn(1<
rn<
p)，则
G中含有
rn个星（把孤立点看成尤)
p-1
②若
G中只含星不含尤3，贝
lj满足条件巩
G) = |
G|-2的连通图个数等于2户,(
P)
j=1
j
③若
G中只含有
i(
i^1)个^，则满足条件巩
G) = |
G|-2的连通图个数等于2户,(
p-3
i)。
j =1
对于性质①：由参考文献[2]中定理3.1，可知对于叭5) = |5|-2的连通图
G，
G中只可能含有'和星
形的连通分支。因为||尤3||=|尤3|，1^.1=1^,-1，所以式（1)成立。
对于性质②：若
G={^
n—^^―〗，…，&—〗}，不妨令
n^
n2》'》1。又因为
G =
p，故得
收稿时间：
2017-10-29
作者简介：陆锋，男，福建莆田人，讲师，硕士，主要从事应用数学应用研究，
21848119@qq.com
,第3期带宽为|G|-2的连通图个数• 73 •
户=' +«
2 +…+ «
y。所以《
15«
2，…，' 是户的一个拆分。另一方面，
p的一个
J+拆分《
15«
2，…，' 也对应着
某个冱= {'
,„—
15…，^^―
J，其中' 2«
22..々《^1。所以恰好所有只含
_/个性的5与正整数
p的
所有
J拆分之间是存在一一对应的关系。考虑到
G的连通性和5的结构，在连通分支只含星的情况下，5
至少有两个连通分支。又因为1<(3,所以满足②的条件下^个数可以表示为
p的■/
c/=2,…,
p-1)拆分
数和(3左+
r)。因为5 = 5，所以满足②的条件下5的个数为(3左+
r)。
j=2 J
j=
2
对于性质③：若5中恰含有/个尤
3 (1
u ^)和,个星尤1b—
〗，尤1b—1
，…
，—
1，（不妨令
5乏《
2》》1 )则户-?/“，'+…+ «,。易见恰有
j个星的不同构的5的个数恰好等于
p-3/的
p—3i _
j(j = 2,…，
p-3
i)拆分数和2户,(
p-3
i)。故在这种情况下共含有
i个&的
G个数恰好等于
p-3
i的
j=1
p—3i
j(j = 2
,…,p - 3
i)拆分数和
Z，(p — 3
i)。
, =
1
综合②，以上情况，由加法原则，当0 = 3左+攻1
k + r—1
Z Pj (3k +
r)k p—3i p—1 k p—3i p-1
n(
p，
p-2) =
Z
ZP
j(
p-3
i)+
ZP
j(
p)=Z
ZP
j(3(
k-
i) +
r)+
ZP
j(3
k +
r)
i=1 j=1 j=2 i=1 j=1 j=2
k
3k
-3i
+r
3k+r —1 k
—13t+r 3k+r—1
=Z
Z P, (3
(k —
i) +
r) +
Z P, (3
k +
r) =
ZZ P, (3
t +
r) +
i=1 ,=1 ,=2 t
=0 j
=1
k
—13t+r 3k+r—1 k
—13t+r 3k+r 3k+r —1
=
ZZP
,(3
i +
r)+
ZP
,(3
k +
r) =
ZZP
,(3
i +
r)-
ZP
,(3
k +
r)+
ZP
,(3
k +
r)
i
=0 j
=1 j
=2 i
=0 j
=1 j
=1 j
=2
k
—13t+r k
—13t+r
=Z
Z
P
, (3
i +
r) —
P (3
k +
r) —
P^
+r (3
k +
r) =
Z
Z
P
, (3
i +
r) — 2
i
=0 =1 i
=0 =1(令
k —
i =
t )
(2)对于
p = 3
k(
k》2)，由参考文献[2]定理3.2可知足33，…
，3是
，3| =
p。而
其它件扒5) = |5|-2的连通图5，其补图的边数一定为1
s[5<
p-1。下面用前面讨论
p = 3
k +
r(1 <
k,1
S
r
S 2)时考虑补图边数时的方法分情况讨论补图连通分支中的尤
3的个数。
① 若补图中不含尤
3,则补图皆为星。不同构的补图的个数恰可以表示为正整数3
k的
j拆分数，
3k-1 3k-1
j = 2,3,…，3
k-1的和
ZP
,(3
k)。故满足
S(5) =
p-2并且补图中不含尤
3的连通图个数为
ZP
,(3
k)。
j=2 j
=2
② 若当补图中连通分支中有
i(1
S
i
S
k -1)个尤
3时，满足
S(5) =
p - 2的连通图个数恰可以表示为正整
p—3i
数
p — 3
i的
j拆分数
，j = 2,3,…，3
k-1的和，即为
ZP,(
p—3
i)。
j=1
③ 若当补图中连通分支中全为&时，满足
S(5) =
p-2的连通图的数目是唯一的。
综上所述，当
p = 3
k时，
k
—13k—3i 3k—1 k
—13k—3i k—1 3k—1
n(
p,p — 2) =
Z
ZP
,(3
k — 3
i)+
ZP
,(3
k) + 1 =
Z
ZP
,(3
k — 3
i) +
ZP
1(3
k — 3
i)+
ZP
,(3
k) + 1
i=1j=1 j=2 i=1 j=2 J i=1 j=2
k
—13k—3i 3k—1 k—13k—3i 3k
=Z
ZP
,(3
k — 3
i) +
k — 1+
ZP
,(3
k) +
P
3k(3
k) =
Z
ZP
,(3
k — 3
i) +
k — 1+
ZP
,(3
k)
i
=1 =2 =2 i
=1 =2 =2
k
—13k
—3i k
3t k
3t k
=Z
Z P, (3
k - 3
i) + k -1 (令 k — i = t ) =
ZZ P, (3t) + k -1 =
ZZ P, (3t) -
Z P1(3t) + k -1
i
=1 =2 i
=1 =2 i
=1 =1 i
=1 1
：
ZZ Pj (3
t) — k + k — 1 =
ZZ P, (3
t) — 1
i=1 j=1 i=1 j=1
定义3记
p个点上的边数
e(
p，
p-2) + 1，带宽为
p-2的连通图集合为
G+;
p个点上的边数为
e(
p，
p-2) + 2，带宽为
p-2的连通图集合为
G++。集合
d
所包含元素的个数记为|^|。
![53976-5G无线技术及部署(微课版)-课后习题答案更新.docx[10页]](https://imgs-1438308264.cos.ap-hongkong.myqcloud.com/3a1de5d9370cba1aa8114431b90d6c85ec3a8828.webp)
