版塊導(dǎo)航: 正在加載中...

登錄注冊

應(yīng)《網(wǎng)絡(luò)安全法》要求，自2017年10月1日起，未進行實名認(rèn)證將不得使用互聯(lián)網(wǎng)跟帖服務(wù)。為保障您的帳號能夠正常使用，請盡快對帳號進行手機號驗證，感謝您的理解與支持！

24小時熱門版塊排行榜

北京石油化工學(xué)院2026年研究生招生接收調(diào)劑公告

返回列表

napoleon_999

木蟲 (小有名氣)

應(yīng)助: 0 (幼兒園)
金幣: 5369.5
帖子: 207
在線: 35.1小時
蟲號: 3137925
注冊: 2014-04-15
專業(yè): 組合數(shù)學(xué)

[求助] 圖論方面的一個小問題已有2人參與

有一個問題想了好久都沒有證明出來，就是對于一個不含三角形的圖G，∑d(i)^2<=mn，其中m是邊數(shù)，n是頂點數(shù)，d(i)
是每個頂點的度數(shù)。請各位大神幫忙解決一下，我是新人，金幣有點少，若能解決，感激不盡！

回復(fù)此樓

» 猜你喜歡

283求調(diào)劑已經(jīng)有5人回復(fù)
一志愿哈爾濱工業(yè)大學(xué)材料與化工方向336分已經(jīng)有7人回復(fù)
數(shù)一英一271專碩（085401）求調(diào)劑，可跨已經(jīng)有4人回復(fù)
0856，材料與化工321分求調(diào)劑已經(jīng)有11人回復(fù)
0703化學(xué)求調(diào)劑已經(jīng)有8人回復(fù)
277跪求調(diào)劑已經(jīng)有9人回復(fù)
材料277求調(diào)劑已經(jīng)有6人回復(fù)
085602 307分求調(diào)劑已經(jīng)有7人回復(fù)
一志愿南昌大學(xué)324求調(diào)劑已經(jīng)有7人回復(fù)
材料與化工272求調(diào)劑已經(jīng)有6人回復(fù)

» 本主題相關(guān)價值貼推薦，對您同樣有幫助:

關(guān)于頂點覆蓋算法的一些問題已經(jīng)有8人回復(fù)
拓?fù)鋵W(xué)一個連通的問題已經(jīng)有6人回復(fù)
求助，如何將一個圖劃分為幾個大小相等的集群并集群間的互聯(lián)度最小已經(jīng)有5人回復(fù)
圖論算法求助！已經(jīng)有8人回復(fù)
請問有數(shù)學(xué)里面有研究圖論和函數(shù)變化結(jié)合的交叉學(xué)科嗎已經(jīng)有15人回復(fù)
圖論英文題目的翻譯已經(jīng)有5人回復(fù)
請教一個圖論的題已經(jīng)有5人回復(fù)
呼喚圖論高手！關(guān)于圖論中子圖間連通度的問題。已經(jīng)有4人回復(fù)
關(guān)于圖論問題的NP完備性證明已經(jīng)有7人回復(fù)
圖論的四色問題我拿筆畫畫畫出來個疑問已經(jīng)有5人回復(fù)
計算機學(xué)報投稿過程，供大家分享已經(jīng)有5人回復(fù)
30金幣求助：最長路徑問題，要求遍歷每個節(jié)點，總路徑最長已經(jīng)有7人回復(fù)
matlab圖論有關(guān)的算法程序已經(jīng)有114人回復(fù)
圖論中關(guān)于節(jié)點數(shù)量與邊的關(guān)系已經(jīng)有4人回復(fù)
介紹四色問題的肯普證明（節(jié)選自《數(shù)學(xué)證明》、大連理工大學(xué)出版社著蕭文強）已經(jīng)有4人回復(fù)
【求助】運籌學(xué)與控制論中的圖論方向就業(yè)如何？已經(jīng)有11人回復(fù)
【求助】一個經(jīng)典的數(shù)模問題求解�。。�！急已經(jīng)有7人回復(fù)
【求助】關(guān)于圖像分割的一個問題已經(jīng)有9人回復(fù)

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

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

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

hank612

至尊木蟲 (著名寫手)

數(shù)學(xué)EPI: 14
應(yīng)助: 225 (大學(xué)生)
金幣: 14270.6
散金: 1055
紅花: 95
帖子: 1526
在線: 1375.8小時
蟲號: 2530333
注冊: 2013-07-03
性別: GG
專業(yè): 理論和計算化學(xué)

【答案】應(yīng)助回帖

★ ★ ★ ★ ★
感謝參與，應(yīng)助指數(shù) +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范圍是全體簡單圖。證明目前還是想不出來。...

有了簡單圖并且沒有三角形這兩個條件，結(jié)論是十分顯然的阿

引理1：如果G是簡單圖，并且沒有三角形，那么對任意一條邊e,設(shè)兩個端點是 vi,vj, 由于v_i, v_j沒有公共的鄰居，所以 $d_i + d_j \leq V$ , 其中d_i為vi的頂點度數(shù)，d_j為v_j 的頂點度數(shù)， V為G中所有頂點總數(shù)。

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

樓主仔細(xì)驗證一下，上面的對邊e求和與對頂點求和的轉(zhuǎn)換是成立的。

贊一下(2人)

回復(fù)此樓

We_must_know. We_will_know.

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

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

Edstrayer

版主 (著名寫手)

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

數(shù)學(xué)EPI: 7
應(yīng)助: 157 (高中生)
貴賓: 0.927
金幣: 9349.6
散金: 4503
紅花: 77
沙發(fā): 2
帖子: 2745
在線: 1465.6小時
蟲號: 3086598
注冊: 2014-03-25
管轄: 數(shù)學(xué)

【答案】應(yīng)助回帖

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

命題：設(shè)G=(V,E)是不含自環(huán)的無重邊的簡單圖，如果G中的邊不構(gòu)成三角形，則

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

其中d(v)表示圖G中頂點v的度數(shù)， $m=\mid E\mid,n=\mid V\mid$ .
證明：對G的頂點V使用數(shù)學(xué)歸納法。
當(dāng)n=1時，m=0，d(v)=0，顯然有 $0^2=0\times 1$
當(dāng)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$
當(dāng)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$
歸納假設(shè)：假設(shè)命題對于頂點數(shù)目不大于n的圖G成立。
遞推步驟：則當(dāng) $\mid V\mid=n+1$ 時，設(shè) $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òu)成三角形，所以圖 $G_1$ 中的邊也不構(gòu)成三角形，故其滿足歸納假設(shè)，因此就有：

$\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)$

所以由數(shù)學(xué)歸納法原理就知命題對任意頂點數(shù)目的圖G都成立。

贊一下(1人)

回復(fù)此樓

青蔥歲月圣誕夜，浪漫歌舞迎新年。

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

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

普通回帖

Edstrayer

版主 (著名寫手)

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

數(shù)學(xué)EPI: 7
應(yīng)助: 157 (高中生)
貴賓: 0.927
金幣: 9349.6
散金: 4503
紅花: 77
沙發(fā): 2
帖子: 2745
在線: 1465.6小時
蟲號: 3086598
注冊: 2014-03-25
管轄: 數(shù)學(xué)

圖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$

贊一下

回復(fù)此樓

青蔥歲月圣誕夜，浪漫歌舞迎新年。

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

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

napoleon_999

木蟲 (小有名氣)

應(yīng)助: 0 (幼兒園)
金幣: 5369.5
帖子: 207
在線: 35.1小時
蟲號: 3137925
注冊: 2014-04-15
專業(yè): 組合數(shù)學(xué)

引用回帖:

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 ...

對，忘說了，是簡單圖，無圈無重邊的。

贊一下

回復(fù)此樓

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

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

Edstrayer

版主 (著名寫手)

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

數(shù)學(xué)EPI: 7
應(yīng)助: 157 (高中生)
貴賓: 0.927
金幣: 9349.6
散金: 4503
紅花: 77
沙發(fā): 2
帖子: 2745
在線: 1465.6小時
蟲號: 3086598
注冊: 2014-03-25
管轄: 數(shù)學(xué)

你沒有把問題的條件敘述清楚吧？
這個問題中的圖G對于含圈的簡單圖也是成立的。
例如，設(shè) $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$

贊一下

回復(fù)此樓

青蔥歲月圣誕夜，浪漫歌舞迎新年。

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

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

napoleon_999

木蟲 (小有名氣)

應(yīng)助: 0 (幼兒園)
金幣: 5369.5
帖子: 207
在線: 35.1小時
蟲號: 3137925
注冊: 2014-04-15
專業(yè): 組合數(shù)學(xué)

引用回帖:

4樓: Originally posted by Edstrayer at 2014-08-11 14:27:30
你沒有把問題的條件敘述清楚吧？
這個問題中的圖G對于含圈的簡單圖也是成立的。
例如，設(shè)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范圍是全體簡單圖。證明目前還是想不出來。

贊一下

回復(fù)此樓

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

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

napoleon_999

木蟲 (小有名氣)

應(yīng)助: 0 (幼兒園)
金幣: 5369.5
帖子: 207
在線: 35.1小時
蟲號: 3137925
注冊: 2014-04-15
專業(yè): 組合數(shù)學(xué)

引用回帖:

全體無三角形的簡單圖。

贊一下

回復(fù)此樓

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

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

Edstrayer

版主 (著名寫手)

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

數(shù)學(xué)EPI: 7
應(yīng)助: 157 (高中生)
貴賓: 0.927
金幣: 9349.6
散金: 4503
紅花: 77
沙發(fā): 2
帖子: 2745
在線: 1465.6小時
蟲號: 3086598
注冊: 2014-03-25
管轄: 數(shù)學(xué)

引用回帖:

那你所說的圈是稱作自環(huán)（即邊的兩個端點是同一個頂點）的概念，簡單圖是不討論含自環(huán)的無重邊的圖的。

贊一下

回復(fù)此樓

青蔥歲月圣誕夜，浪漫歌舞迎新年。

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

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

Edstrayer

版主 (著名寫手)

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

數(shù)學(xué)EPI: 7
應(yīng)助: 157 (高中生)
貴賓: 0.927
金幣: 9349.6
散金: 4503
紅花: 77
沙發(fā): 2
帖子: 2745
在線: 1465.6小時
蟲號: 3086598
注冊: 2014-03-25
管轄: 數(shù)學(xué)

【答案】應(yīng)助回帖

感謝參與，應(yīng)助指數(shù) +1

通過對圖G的頂點n使用數(shù)學(xué)歸納法可以證明本命題。

贊一下

回復(fù)此樓

青蔥歲月圣誕夜，浪漫歌舞迎新年。

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

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

相關(guān)版塊跳轉(zhuǎn) 我要訂閱樓主 napoleon_999 的主題更新

返回列表

最具人氣熱帖推薦 [查看全部]		作者	回/看	最后發(fā)表

[考研] 一志愿哈爾濱工業(yè)大學(xué)材料與化工方向336分 +7	辰沐5211314 2026-03-26	7/350	2026-03-28 10:09 by lbsjt
[考研] 數(shù)一英一271專碩（085401）求調(diào)劑，可跨 +3	前行必有光 2026-03-28	4/200	2026-03-28 10:07 by laoshidan
[考研] 材料與化工考研調(diào)劑 +17	孅華 2026-03-22	17/850	2026-03-28 08:35 by WYUMater
[考研] 一志愿中南大學(xué)化學(xué)0703總分337求調(diào)劑 +4	niko- 2026-03-27	4/200	2026-03-28 07:26 by fungyao
[考研] 328求調(diào)劑 +7	嗯滴的基本都 2026-03-27	7/350	2026-03-28 04:19 by fmesaito
[考研] 330一志愿中國海洋大學(xué) 化學(xué)工程 085602 有讀博意愿求調(diào)劑 +3	wywy.. 2026-03-27	4/200	2026-03-28 03:32 by fmesaito
[考研] 學(xué)碩274求調(diào)劑 +5	Li李魚 2026-03-26	5/250	2026-03-27 20:51 by 熱情沙漠
[考研] 308求調(diào)劑 +7	墨墨漠 2026-03-25	7/350	2026-03-27 14:47 by 狂炫麥當(dāng)當(dāng)
[考研] 化學(xué)308分求調(diào)劑 +8	你好明天你好 2026-03-23	9/450	2026-03-27 14:01 by 楊光于青云
[考研] 292求調(diào)劑 +4	求求了收下我吧?/a> 2026-03-26	4/200	2026-03-27 10:37 by zhshch
[考研] 286求調(diào)劑 +4	lim0922 2026-03-26	4/200	2026-03-27 10:28 by guoweigw
[考研] 一志愿武漢理工，總分321，英一數(shù)二，求老師收留。 +5	nnnnnnn5 2026-03-25	5/250	2026-03-27 04:42 by wxiongid
[考研] 317求調(diào)劑 +7	蛋黃咸肉粽 2026-03-26	7/350	2026-03-27 02:29 by fmesaito
[考研] 機械學(xué)碩310分，數(shù)一英一，一志愿211本科雙非找調(diào)劑信息 +3	@357 2026-03-25	3/150	2026-03-26 16:34 by by.MENG
[考研] 考研調(diào)劑 +6	來好運來來來 2026-03-21	7/350	2026-03-25 22:43 by 418490947
[考研] 289材料與化工（085600）B區(qū)求調(diào)劑 +4	這么名字咋樣 2026-03-22	5/250	2026-03-25 08:20 by mx.yue
[考研] 一志愿北化315 求調(diào)劑 +3	akrrain 2026-03-24	3/150	2026-03-24 19:35 by 了了了了。。
[考研] 求調(diào)劑 +6	研研，接電話 2026-03-24	7/350	2026-03-24 17:01 by barlinike
[考研] 一志愿070300浙大化學(xué)358分，求調(diào)劑！ +4	酥酥魚.. 2026-03-21	4/200	2026-03-23 08:12 by Iveryant
[考研] 求調(diào)劑 +3	.m.. 2026-03-21	4/200	2026-03-21 16:25 by barlinike

24小時熱門版塊排行榜

[求助] 圖論方面的一個小問題 已有2人參與

» 猜你喜歡

» 本主題相關(guān)價值貼推薦，對您同樣有幫助:

【答案】應(yīng)助回帖

【答案】應(yīng)助回帖

【答案】應(yīng)助回帖

[求助] 圖論方面的一個小問題已有2人參與