版塊導航: 正在加載中...

登錄注冊

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

24小時熱門版塊排行榜

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

返回列表

napoleon_999

木蟲 (小有名氣)

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

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

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

回復(fù)此樓

» 猜你喜歡

299求調(diào)劑已經(jīng)有8人回復(fù)
一志愿北京理工大學本科211材料工程294求調(diào)劑已經(jīng)有6人回復(fù)
300求調(diào)劑，材料科學英一數(shù)二已經(jīng)有8人回復(fù)
招收生物學/細胞生物學調(diào)劑已經(jīng)有5人回復(fù)
070305高分子化學與物理 304分求調(diào)劑已經(jīng)有7人回復(fù)
289求調(diào)劑已經(jīng)有13人回復(fù)
一志愿哈爾濱工業(yè)大學材料與化工方向336分已經(jīng)有9人回復(fù)
081200-11408-276學碩求調(diào)劑已經(jīng)有6人回復(fù)
調(diào)劑求院校招收已經(jīng)有5人回復(fù)
調(diào)劑310 已經(jīng)有8人回復(fù)

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

關(guān)于頂點覆蓋算法的一些問題已經(jīng)有8人回復(fù)
拓撲學一個連通的問題已經(jīng)有6人回復(fù)
求助，如何將一個圖劃分為幾個大小相等的集群并集群間的互聯(lián)度最小已經(jīng)有5人回復(fù)
圖論算法求助！已經(jīng)有8人回復(fù)
請問有數(shù)學里面有研究圖論和函數(shù)變化結(jié)合的交叉學科嗎已經(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ù)
計算機學報投稿過程，供大家分享已經(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ù)學證明》、大連理工大學出版社著蕭文強）已經(jīng)有4人回復(fù)
【求助】運籌學與控制論中的圖論方向就業(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ù)學EPI: 14
應(yīng)助: 225 (大學生)
金幣: 14270.6
散金: 1055
紅花: 95
帖子: 1526
在線: 1375.8小時
蟲號: 2530333
注冊: 2013-07-03
性別: GG
專業(yè): 理論和計算化學

【答案】應(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$

樓主仔細驗證一下，上面的對邊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ù)學EPI: 7
應(yīng)助: 157 (高中生)
貴賓: 0.927
金幣: 9349.6
散金: 4503
紅花: 77
沙發(fā): 2
帖子: 2745
在線: 1465.6小時
蟲號: 3086598
注冊: 2014-03-25
管轄: 數(shù)學

【答案】應(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ù)學歸納法。
當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$
歸納假設(shè)：假設(shè)命題對于頂點數(shù)目不大于n的圖G成立。
遞推步驟：則當 $\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ù)學歸納法原理就知命題對任意頂點數(shù)目的圖G都成立。

贊一下(1人)

回復(fù)此樓

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

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

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

普通回帖

Edstrayer

版主 (著名寫手)

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

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

圖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ù)學

引用回帖:

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

你沒有把問題的條件敘述清楚吧？
這個問題中的圖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ù)學

引用回帖:

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ù)學

引用回帖:

全體無三角形的簡單圖。

贊一下

回復(fù)此樓

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

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

Edstrayer

版主 (著名寫手)

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

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

引用回帖:

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

贊一下

回復(fù)此樓

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

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

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

Edstrayer

版主 (著名寫手)

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

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

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

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

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

贊一下

回復(fù)此樓

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

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

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

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

返回列表

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

[考研] 299求調(diào)劑 +8	15188958825 2026-03-25	8/400	2026-03-29 01:36 by fmesaito
[碩博家園] 求調(diào)劑 330分 085600材料與化工 +3	gqhhh 2026-03-22	3/150	2026-03-29 00:52 by 544594351
[考研] 材料學碩333求調(diào)劑 +10	北道巷 2026-03-24	10/500	2026-03-28 23:06 by 無際的草原
[考研] 343求調(diào)劑 +5	愛羈絆 2026-03-28	5/250	2026-03-28 20:53 by 唐沐兒
[考研] 生物學學碩，一志愿湖南大學，初試成績338 +6	YYYYYNNNNN 2026-03-26	7/350	2026-03-28 20:52 by 唐沐兒
[考研] 一志愿北化085600材料專碩275\|有文章專利｜求調(diào)劑 +7	Micky11223 2026-03-25	7/350	2026-03-28 18:34 by 無際的草原
[考研] 壓國家一區(qū)線，求導師收留，有恩必謝！ +7	迷人的哈哈 2026-03-28	7/350	2026-03-28 16:47 by 催化大白
[考研] 275求調(diào)劑 +10	Micky11223 2026-03-25	14/700	2026-03-28 15:48 by Micky11223
[考研] 298調(diào)劑 +3	jiyingjie123 2026-03-27	3/150	2026-03-27 11:57 by wxiongid
[論文投稿] Journal of Mechanical Science and Technology +3	Russ_ss 2026-03-25	5/250	2026-03-27 10:49 by 陸小果畫大餅
[考研] 一志愿北化求調(diào)劑 +3	Jsman 2026-03-22	3/150	2026-03-26 21:06 by ajpv風雷
[考研] 086000生物與醫(yī)藥292求調(diào)劑 +6	小小陳小小 2026-03-22	9/450	2026-03-26 15:58 by dick_runner
[考研] 一志愿河工大 081700 276求調(diào)劑 +4	地球繞著太陽轉(zhuǎn) 2026-03-23	4/200	2026-03-26 14:27 by zzll406
[考研] 環(huán)境專碩324分求調(diào)劑推薦 +5	軒小寧—— 2026-03-26	5/250	2026-03-26 12:05 by i_cooler
[考研] 26考研-291分-廈門大學（085601）-柔性電子學院材料工程專業(yè)求調(diào)劑 +3	min3 2026-03-24	4/200	2026-03-25 18:22 by xcjcqu
[考研] 網(wǎng)絡(luò)空間安全0839招調(diào)劑 +4	w320357296 2026-03-25	6/300	2026-03-25 17:59 by 255671
[考研] 347求調(diào)劑 +4	L when 2026-03-25	4/200	2026-03-25 13:37 by cocolv
[考研] 上海電力大學材料防護與新材料重點實驗室招收調(diào)劑研究生（材料、化學、電化學，環(huán)境） +4	我愛學電池 2026-03-23	4/200	2026-03-25 00:59 by 1027_324
[考研] 344求調(diào)劑 +3	desto 2026-03-24	3/150	2026-03-24 10:09 by 搏擊518
[考研] 361求調(diào)劑 +3	Glack 2026-03-22	3/150	2026-03-23 22:03 by fuyu_

24小時熱門版塊排行榜

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

» 猜你喜歡

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

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

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

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

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

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