版块导航: 正在加载中...

登录注册

应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜

北京石油化工学院2026年研究生招生接收调剂公告

返回列表

napoleon_999

木虫 (小有名气)

应助: 0 (幼儿园)
金币: 5369.5
帖子: 207
在线: 35.1小时
虫号: 3137925
注册: 2014-04-15
专业: 组合数学

[求助] 图论方面的一个小问题已有2人参与

有一个问题想了好久都没有证明出来，就是对于一个不含三角形的图G，∑d(i)^2<=mn，其中m是边数，n是顶点数，d(i)
是每个顶点的度数。请各位大神帮忙解决一下，我是新人，金币有点少，若能解决，感激不尽！

回复此楼

» 猜你喜欢

调剂已经有6人回复
一志愿江南大学 085602 化工专硕 338分求调剂已经有12人回复
材料专硕(0856) 339分求调剂已经有8人回复
377求调剂已经有5人回复
0703调剂，一志愿天津大学319分已经有6人回复
一志愿南昌大学，085600，344分求调剂已经有5人回复
308求调剂已经有8人回复
找调剂已经有9人回复
一志愿郑州大学085600求调剂已经有12人回复
316求调剂已经有3人回复

» 本主题相关价值贴推荐，对您同样有帮助:

关于顶点覆盖算法的一些问题已经有8人回复
拓扑学一个连通的问题已经有6人回复
求助，如何将一个图划分为几个大小相等的集群并集群间的互联度最小已经有5人回复
图论算法求助！已经有8人回复
请问有数学里面有研究图论和函数变化结合的交叉学科吗已经有15人回复
图论英文题目的翻译已经有5人回复
请教一个图论的题已经有5人回复
呼唤图论高手！关于图论中子图间连通度的问题。已经有4人回复
关于图论问题的NP完备性证明已经有7人回复
图论的四色问题我拿笔画画画出来个疑问已经有5人回复
计算机学报投稿过程，供大家分享已经有5人回复
30金币求助：最长路径问题，要求遍历每个节点，总路径最长已经有7人回复
matlab图论有关的算法程序已经有114人回复
图论中关于节点数量与边的关系已经有4人回复
介绍四色问题的肯普证明（节选自《数学证明》、大连理工大学出版社著萧文强）已经有4人回复
【求助】运筹学与控制论中的图论方向就业如何？已经有11人回复
【求助】一个经典的数模问题求解！！！！急已经有7人回复
【求助】关于图像分割的一个问题已经有9人回复

1楼 2014-08-11 11:13:16

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

回帖支持 ( 显示支持度最高的前 50 名 )

hank612

至尊木虫 (著名写手)

数学EPI: 14
应助: 225 (大学生)
金币: 14270.6
散金: 1055
红花: 95
帖子: 1526
在线: 1375.8小时
虫号: 2530333
注册: 2013-07-03
性别: GG
专业: 理论和计算化学

【答案】应助回帖

★ ★ ★ ★ ★
感谢参与，应助指数 +1
napoleon_999: 金币+5, ★★★★★最佳答案, 我太穷了 2014-08-12 09:00:17

引用回帖:

5楼: Originally posted by napoleon_999 at 2014-08-11 14:45:04
不，您弄错了，我就是指的所有的简单图，无圈无重边是简单图的概念，圈在这里指的是一条边两个端点是同一个顶点的那一种，不是circle，是loop，这道题的图G范围是全体简单图。证明目前还是想不出来。...

有了简单图并且没有三角形这两个条件，结论是十分显然的阿

引理1：如果G是简单图，并且没有三角形，那么对任意一条边e,设两个端点是 vi,vj, 由于v_i, v_j没有公共的邻居，所以 $d_i + d_j \leq V$ , 其中d_i为vi的顶点度数，d_j为v_j 的顶点度数， V为G中所有顶点总数。

然后，自然是 $\sum_{k=1}^V d_k^2=\sum_{e \in E} (d_i +d_j) \leq E\dot V$

楼主仔细验证一下，上面的对边e求和与对顶点求和的转换是成立的。

赞一下(2人)

回复此楼

We_must_know. We_will_know.

10楼2014-08-11 23:15:48

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

Edstrayer

版主 (著名写手)

方寸斗室小天地正气迷漫大世界

数学EPI: 7
应助: 157 (高中生)
贵宾: 0.927
金币: 9349.6
散金: 4503
红花: 77
沙发: 2
帖子: 2745
在线: 1465.6小时
虫号: 3086598
注册: 2014-03-25
管辖: 数学

【答案】应助回帖

★
napoleon_999: 金币+1, ★有帮助 2014-08-12 09:00:41

命题：设G=(V,E)是不含自环的无重边的简单图，如果G中的边不构成三角形，则

$\sum\limits_{v\in V}d^2(v)\leqslant mn$

其中d(v)表示图G中顶点v的度数， $m=\mid E\mid,n=\mid V\mid$ .
证明：对G的顶点V使用数学归纳法。
当n=1时，m=0，d(v)=0，显然有 $0^2=0\times 1$
当n=2时， $V=\{v_1,v_2\}$ ，因为是简单图，故 $m\leqslant 1$ ，
      情形一：如果m=0，则 $d(v_1)=d(v_2)=0,\text{then}0^2+0^2=0\times 2$
      情形二：如果m=1，则 $d(v_1)=d(v_2)=1,\text{then}1^2+1^2=1\times 2$
当n=3时， $V=\{v_1,v_2,v_3\}$ ，因为是简单图，故 $m\leqslant 2$ ，
      情形一：如果m=0，则 $d(v_1)=d(v_2)=d(v_3)=0,\text{then}0^2+0^2+0^2=0\times 3$
      情形二：如果m=1，则 $d(v_1)=d(v_2)=1,d(v_3)=0,\text{then}1^2+1^2+0^2=2<1\times 3$
      情形三：如果m=2，则 $d(v_1)=d(v_2)=1,d(v_3)=2,\text{then}1^2+1^2+2^2=6=2\times 3$
归纳假设：假设命题对于顶点数目不大于n的图G成立。
递推步骤：则当 $\mid V\mid=n+1$ 时，设 $V=\{v_1,v_2,\cdots,v_n,v_{n+1}\}$ ，记图G删掉顶点 $v_{n+1}$ 后得到的图为 $G_1=(V_1,E_1)$ ，显然在图 $G,G_1$ 中， $d(v_{n+1})=d\leqslant n,\mid E_1\mid=m-d,\mid V_1\mid=n$ 。由于图G中的边不构成三角形，所以图 $G_1$ 中的边也不构成三角形，故其满足归纳假设，因此就有：

$\sum\limits_{v\in G_1}d^2(v)\leqslant(m-d)n$

于是就有：

$\sum\limits_{v\in G}d^2(v)=\sum\limits_{v\in G_1}d^2(v)+d(v_{n+1})$

$\sum\limits_{v\in G}d^2(v)\leqslant(m-d)n+d^2=mn+d(d-n)\leqslant mn\leqslant m(n+1)$

所以由数学归纳法原理就知命题对任意顶点数目的图G都成立。

赞一下(1人)

回复此楼

青葱岁月圣诞夜，浪漫歌舞迎新年。

9楼2014-08-11 17:53:56

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

普通回帖

Edstrayer

版主 (著名写手)

方寸斗室小天地正气迷漫大世界

数学EPI: 7
应助: 157 (高中生)
贵宾: 0.927
金币: 9349.6
散金: 4503
红花: 77
沙发: 2
帖子: 2745
在线: 1465.6小时
虫号: 3086598
注册: 2014-03-25
管辖: 数学

图G是简单图吧？
否则，易举出反例的。
例如： $G=\{v_1,v_2,v_3\},E=\{v_1v_2,v_1v_2,v_1v_3,v_1v_3\}$ ，即G是三个顶点四条边的含圈图（不含成三角形的边），其中

$d(v_1)=4,d(v_2)=d(v_3)=2,n=3,m=4$

则有：

$\sum\limits_{v_i\in G}d^2(v_i)=4^2+2^2+2^2=24>3\times 4=12$

赞一下

回复此楼

青葱岁月圣诞夜，浪漫歌舞迎新年。

2楼2014-08-11 12:16:04

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

napoleon_999

木虫 (小有名气)

应助: 0 (幼儿园)
金币: 5369.5
帖子: 207
在线: 35.1小时
虫号: 3137925
注册: 2014-04-15
专业: 组合数学

引用回帖:

2楼: Originally posted by Edstrayer at 2014-08-11 12:16:04
图G是简单图吧？
否则，易举出反例的。
例如：G=\{v_1,v_2,v_3\},E=\{v_1v_2,v_1v_2,v_1v_3,v_1v_3\}，即G是三个顶点四条边的含圈图（不含成三角形的边），其中
d(v_1)=4,d(v_2)=d(v_3)=2,n=3,m=4
则有：
\sum ...

对，忘说了，是简单图，无圈无重边的。

赞一下

回复此楼

3楼2014-08-11 13:14:06

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

Edstrayer

版主 (著名写手)

方寸斗室小天地正气迷漫大世界

数学EPI: 7
应助: 157 (高中生)
贵宾: 0.927
金币: 9349.6
散金: 4503
红花: 77
沙发: 2
帖子: 2745
在线: 1465.6小时
虫号: 3086598
注册: 2014-03-25
管辖: 数学

你没有把问题的条件叙述清楚吧？
这个问题中的图G对于含圈的简单图也是成立的。
例如，设 $G=(V,E),\textbf{here} V=\{v_1,v_2,v_3,v_4,v_5\},E=\{v_1v_2,v_2v_3,v_3v_4,v_4v_5,v_5v_1\}$ ，即G是五个顶点的含圈的简单图，则有：

$d(v_i)=2(i=1,2,3,4,5),n=5,m=5$

于是就有：

$\sum\limits_{v_i\in G}d^2(v_i)=2^2\times 5=4\times 5=20<nm=5\times 5=25$

赞一下

回复此楼

青葱岁月圣诞夜，浪漫歌舞迎新年。

4楼2014-08-11 14:27:30

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

napoleon_999

木虫 (小有名气)

应助: 0 (幼儿园)
金币: 5369.5
帖子: 207
在线: 35.1小时
虫号: 3137925
注册: 2014-04-15
专业: 组合数学

引用回帖:

4楼: Originally posted by Edstrayer at 2014-08-11 14:27:30
你没有把问题的条件叙述清楚吧？
这个问题中的图G对于含圈的简单图也是成立的。
例如，设G=(V,E),\textbf{here} V=\{v_1,v_2,v_3,v_4,v_5\},E=\{v_1v_2,v_2v_3,v_3v_4,v_4v_5,v_5v_1\}，即G是五个顶点的含圈的简单 ...

不，您弄错了，我就是指的所有的简单图，无圈无重边是简单图的概念，圈在这里指的是一条边两个端点是同一个顶点的那一种，不是circle，是loop，这道题的图G范围是全体简单图。证明目前还是想不出来。

赞一下

回复此楼

5楼2014-08-11 14:45:04

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

napoleon_999

木虫 (小有名气)

应助: 0 (幼儿园)
金币: 5369.5
帖子: 207
在线: 35.1小时
虫号: 3137925
注册: 2014-04-15
专业: 组合数学

引用回帖:

全体无三角形的简单图。

赞一下

回复此楼

6楼2014-08-11 14:49:55

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

Edstrayer

版主 (著名写手)

方寸斗室小天地正气迷漫大世界

数学EPI: 7
应助: 157 (高中生)
贵宾: 0.927
金币: 9349.6
散金: 4503
红花: 77
沙发: 2
帖子: 2745
在线: 1465.6小时
虫号: 3086598
注册: 2014-03-25
管辖: 数学

引用回帖:

那你所说的圈是称作自环（即边的两个端点是同一个顶点）的概念，简单图是不讨论含自环的无重边的图的。

赞一下

回复此楼

青葱岁月圣诞夜，浪漫歌舞迎新年。

7楼2014-08-11 14:50:39

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

Edstrayer

版主 (著名写手)

方寸斗室小天地正气迷漫大世界

数学EPI: 7
应助: 157 (高中生)
贵宾: 0.927
金币: 9349.6
散金: 4503
红花: 77
沙发: 2
帖子: 2745
在线: 1465.6小时
虫号: 3086598
注册: 2014-03-25
管辖: 数学

【答案】应助回帖

感谢参与，应助指数 +1

通过对图G的顶点n使用数学归纳法可以证明本命题。

赞一下

回复此楼

青葱岁月圣诞夜，浪漫歌舞迎新年。

8楼2014-08-11 15:42:20

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

相关版块跳转我要订阅楼主 napoleon_999 的主题更新

返回列表

最具人气热帖推荐 [查看全部]		作者	回/看	最后发表

[考研] 调剂 +5	不逢春 2026-04-05	6/300	2026-04-05 21:50 by 不逢春
[考研] 一志愿郑州大学085600求调剂 +10	吃的不少 2026-04-05	12/600	2026-04-05 21:38 by 醉翁wl
[考研] 296求调剂 +3	汪！？！ 2026-04-05	4/200	2026-04-05 20:13 by 啵啵啵0119
[考研] 求调剂，一志愿郑州大学材料与化工专硕，英二数二342分，求老师收留 +18	v12abo 2026-04-02	20/1000	2026-04-05 11:37 by a8144223
[考研] 一志愿郑大0705求调剂 +3	橘十一 2026-04-02	4/200	2026-04-05 00:05 by chongya
[考研] 340求调剂 +4	jhx777 2026-03-29	4/200	2026-04-04 20:08 by 无际的草原
[考研] 学硕288调剂!!! +3	小王xw123 2026-04-03	3/150	2026-04-03 21:20 by 啵啵啵0119
[考研] 283求调剂 +3	jiouuu 2026-04-03	4/200	2026-04-03 13:28 by jiouuu
[考研] 282求调剂 +5	呼吸都是减肥 2026-03-31	5/250	2026-04-03 12:03 by 1753564080
[基金申请] 请问共同通讯和共同一作的认可度问题 10+4	psa1234 2026-04-01	10/500	2026-04-03 11:08 by Kittylucky
[考研] 一志愿深大085601材料工程专业（专硕）300分可以调剂去哪 +8	10160315 2026-04-02	8/400	2026-04-03 09:36 by hypershenger
[考研] 化学070300-总分378-求调剂 +5	挪椅子的泡泡糖 2026-04-02	5/250	2026-04-02 22:20 by ZXlzxl0425
[考研] 一志愿武汉理工0856，初试334 +3	26考研材料 2026-04-02	3/150	2026-04-02 21:22 by dongzh2009
[考研] 材料340分调剂 +7	夏夜晚风_long 2026-04-02	9/450	2026-04-02 21:20 by dongzh2009
[考研] 一志愿山东大学，085600，344 +7	魏子per 2026-04-02	8/400	2026-04-02 21:12 by 百灵童888
[考研] 初试301，代码085701环境工程，本硕一致，四六级已过，有二区一作，共发表5篇论文 +6	axibli 2026-04-01	6/300	2026-04-02 13:42 by Ecowxq666！
[考研] 08工科求调剂290分 +5	1314捧花 2026-04-02	8/400	2026-04-02 13:16 by 乔哒哒哒
[考研] 266分，一志愿电气工程，本科材料，求材料专业调剂 +10	哇呼哼呼哼 2026-04-01	11/550	2026-04-02 11:31 by lnilvy
[考研] 08工科，295，接受跨专业调剂 +6	lmnlzy 2026-03-31	6/300	2026-04-01 11:02 by 逆水乘风
[考研] 070300化学专业279调剂 +10	哈哈哈^_^ 2026-03-31	10/500	2026-03-31 23:13 by liu823948201

24小时热门版块排行榜

[求助] 图论方面的一个小问题 已有2人参与

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:

【答案】应助回帖

【答案】应助回帖

【答案】应助回帖

[求助] 图论方面的一个小问题已有2人参与