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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 数学 » 运筹学与控制论 » 图论方面的一个小问题
北京石油化工学院2026年研究生招生接收调剂公告
51/1返回列表
查看: 2343  |  回复: 14
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

napoleon_999

木虫 (小有名气)

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

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

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
1楼 2014-08-11 11:13:16
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

hank612

至尊木虫 (著名写手)

【答案】应助回帖

★ ★ ★ ★ ★
感谢参与，应助指数 +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为vi的顶点度数，d_j为v_j 的顶点度数， V为G中所有顶点总数。

然后，自然是

楼主仔细验证一下，上面的对边e求和与对顶点求和的转换是成立的。
赞一下(2人) 回复此楼
We_must_know. We_will_know.
10楼2014-08-11 23:15:48
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 15 个回答

Edstrayer

版主 (著名写手)

方寸斗室小天地正气迷漫大世界
图G是简单图吧？
否则，易举出反例的。
例如：，即G是三个顶点四条边的含圈图（不含成三角形的边），其中


则有：
赞一下 回复此楼
青葱岁月圣诞夜，浪漫歌舞迎新年。
2楼2014-08-11 12:16:04
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

napoleon_999

木虫 (小有名气)
引用回帖:
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

版主 (著名写手)

方寸斗室小天地正气迷漫大世界
你没有把问题的条件叙述清楚吧？
这个问题中的图G对于含圈的简单图也是成立的。
例如，设，即G是五个顶点的含圈的简单图，则有：


于是就有：
赞一下 回复此楼
青葱岁月圣诞夜，浪漫歌舞迎新年。
4楼2014-08-11 14:27:30
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 15 个回答
普通表情 龙 兔 虎 猫
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 学硕274求调剂 +14 Li李鱼 2026-03-26 14/700 2026-03-31 09:31 by zhshch
[考研] 284求调剂 +4 小熊～～ 2026-03-31 4/200 2026-03-31 09:30 by longlotian
[考研] 070300一志愿211，312分求调剂院校 +6 小黄鸭宝 2026-03-30 6/300 2026-03-31 09:23 by jp9609
[考研] 085602化工求调剂（331分） +8 111@127 2026-03-30 8/400 2026-03-30 21:23 by 研究僧导导
[考研] 085600 295分求调剂 +7 W55j 2026-03-30 9/450 2026-03-30 20:36 by dick_runner
[有机交流] 考研调剂 +8 watb 2026-03-26 8/400 2026-03-30 18:40 by 544594351
[考研] 334分 一志愿武理 材料求调剂 +16 李李不服输 2026-03-26 16/800 2026-03-30 17:47 by wangjy2002
[考研] 310求调剂 +10 争取九点睡 2026-03-30 10/500 2026-03-30 16:45 by ztnimte
[考研] 本科211生物医学工程085409求调剂339分 +3 里子木yy 2026-03-29 3/150 2026-03-30 13:29 by gyzj2026
[考研] 0703化学/290求调剂/本科经历丰富/工科也可 +13 丹青奶盖 2026-03-26 15/750 2026-03-30 12:35 by fangnagu
[考研] 一志愿北京工业大学，324分求调剂 +6 零八# 2026-03-28 6/300 2026-03-29 21:20 by nanaliuyun
[考研] 343求调剂085601 +3 要努力学习x 2026-03-29 3/150 2026-03-29 18:35 by wxiongid
[考研] 291求调剂 +5 Y-cap 2026-03-29 6/300 2026-03-29 13:18 by mumin1990
[考研] 调剂求院校招收 +6 鹤鲸鸽 2026-03-28 6/300 2026-03-29 08:15 by fmesaito
[考研] 11408软件工程求调剂 +3 Qiu学ing 2026-03-28 3/150 2026-03-28 21:50 by zhq0425
[考研] 求调剂 +7 争取九点睡 2026-03-28 8/400 2026-03-28 21:07 by 争取九点睡
[考研] 本科新能源科学与工程，一志愿华理能动285求调剂 +7 AZMK 2026-03-28 11/550 2026-03-28 21:01 by xxxsssccc
[考研] 304求调剂 +6 曼殊2266 2026-03-27 6/300 2026-03-28 14:10 by 唐沐儿
[考研] 330一志愿中国海洋大学 化学工程 085602 有读博意愿 求调剂 +3 wywy.. 2026-03-27 4/200 2026-03-28 03:32 by fmesaito
[考研] 【2026考研调剂】制药工程 284分 求相关专业调剂名额 +4 袁奂奂 2026-03-25 8/400 2026-03-25 14:32 by lbsjt
信息提示
关闭
请填处理意见
关闭