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

登录注册

应《网络安全法》要求，自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)
是每个顶点的度数。请各位大神帮忙解决一下，我是新人，金币有点少，若能解决，感激不尽！

回复此楼

» 猜你喜欢

262求调剂已经有5人回复
0856调剂已经有6人回复
张芳铭-中国农业大学-环境工程专硕-298 已经有6人回复
考研生物与医药调剂已经有3人回复
274求调剂已经有5人回复
化学工程085602 305分求调剂已经有26人回复
334求调剂已经有3人回复
一志愿南京航空航天大学，080500材料科学与工程学硕已经有5人回复
看看我！301求调剂 081700 已经有3人回复
求调剂生物学 377分已经有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的回帖

napoleon_999

木虫 (小有名气)

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

引用回帖:

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

全体无三角形的简单图。

赞一下

回复此楼

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

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

查看全部 15 个回答

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的回帖

查看全部 15 个回答

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

[考研] 22408 359分调剂 +4	Qshers 2026-03-27	8/400	2026-03-31 08:53 by Qshers
[考研] 311求调剂一志愿合肥工业大学 +5	秋二十二 2026-03-30	5/250	2026-03-31 06:55 by 无际的草原
[考研] 303求调剂 +7	DLkz1314. 2026-03-30	7/350	2026-03-30 21:07 by peike
[考研] 303求调剂 +7	DLkz1314. 2026-03-30	7/350	2026-03-30 16:05 by shuang5186
[考研] 329求调剂 +8	星野? 2026-03-26	8/400	2026-03-30 13:41 by chemdavid
[考研] 环境科学与工程334分求调剂 +6	王一一依依 2026-03-30	8/400	2026-03-30 11:52 by yjolah
[考研] 295求调剂 +5	wei-5 2026-03-26	5/250	2026-03-30 08:34 by 探123
[考研] 一志愿武汉理工，总分321，英一数二，求老师收留。 +11	nnnnnnn5 2026-03-25	11/550	2026-03-29 20:42 by 无际的草原
[考研] 086000生物与医药调剂 +5	Feisty。 2026-03-28	9/450	2026-03-29 12:02 by longlotian
[考研] 调剂求院校招收 +6	鹤鲸鸽 2026-03-28	6/300	2026-03-29 08:15 by fmesaito
[考研] 316求调剂 +7	江辞666 2026-03-26	7/350	2026-03-28 21:28 by sanrepian
[考研] 求调剂 +6	芦lty 2026-03-25	7/350	2026-03-28 13:13 by 唐沐儿
[考研] 一志愿西北大学总分282 英语一62 求调剂 +7	18419759900 2026-03-25	8/400	2026-03-27 16:38 by 18419759900
[考研] 材料求调剂 +5	.m.. 2026-03-25	5/250	2026-03-27 11:08 by 不吃魚的貓
[论文投稿] Journal of Mechanical Science and Technology +3	Russ_ss 2026-03-25	5/250	2026-03-27 10:49 by 陆小果画大饼
[考研] 292求调剂 +4	求求了收下我吧� 2026-03-26	4/200	2026-03-27 10:37 by zhshch
[考研] 286求调剂 +4	lim0922 2026-03-26	4/200	2026-03-27 10:28 by guoweigw
[考研] 081200-11408-276学硕求调剂 +4	崔wj 2026-03-26	4/200	2026-03-27 08:04 by chemisry
[考研] 材料调剂 5+4	想要一壶桃花水 2026-03-25	10/500	2026-03-26 19:56 by 不吃魚的貓
[考研] 一志愿吉林大学材料与化工303分求调剂 +4	为学666 2026-03-24	4/200	2026-03-25 11:27 by BruceLiu320

24小时热门版块排行榜

napoleon_999

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

» 猜你喜欢

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

napoleon_999

Edstrayer

napoleon_999

Edstrayer

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