當(dāng)前只顯示滿足指定條件的回帖，點(diǎn)擊這里查看本話題的所有回帖

napoleon_999

木蟲 (小有名氣)

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

[求助] 圖論方面的一個(gè)小問(wèn)題已有2人參與

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

回復(fù)此樓

» 猜你喜歡

085600，材料與化工321分求調(diào)劑已經(jīng)有5人回復(fù)
求化學(xué)調(diào)劑已經(jīng)有3人回復(fù)
調(diào)劑求院校招收已經(jīng)有3人回復(fù)
材料與化工（0856）304求B區(qū)調(diào)劑已經(jīng)有8人回復(fù)
320分，材料與化工專業(yè)，求調(diào)劑已經(jīng)有11人回復(fù)
0856求調(diào)劑已經(jīng)有10人回復(fù)
266分，求材料冶金能源化工等調(diào)劑已經(jīng)有9人回復(fù)
085600 286分材料求調(diào)劑已經(jīng)有8人回復(fù)
085701環(huán)境工程，267求調(diào)劑已經(jīng)有16人回復(fù)
286求調(diào)劑已經(jīng)有12人回復(fù)

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

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

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

已閱回復(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小時(shí)
蟲號(hào): 3086598
注冊(cè): 2014-03-25
管轄: 數(shù)學(xué)

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

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

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

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

其中d(v)表示圖G中頂點(diǎn)v的度數(shù)， $m=\mid E\mid,n=\mid V\mid$ .
證明：對(duì)G的頂點(diǎn)V使用數(shù)學(xué)歸納法。
當(dāng)n=1時(shí)，m=0，d(v)=0，顯然有 $0^2=0\times 1$
當(dāng)n=2時(shí)， $V=\{v_1,v_2\}$ ，因?yàn)槭呛?jiǎn)單圖，故 $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時(shí)， $V=\{v_1,v_2,v_3\}$ ，因?yàn)槭呛?jiǎn)單圖，故 $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è)命題對(duì)于頂點(diǎn)數(shù)目不大于n的圖G成立。
遞推步驟：則當(dāng) $\mid V\mid=n+1$ 時(shí)，設(shè) $V=\{v_1,v_2,\cdots,v_n,v_{n+1}\}$ ，記圖G刪掉頂點(diǎn) $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é)歸納法原理就知命題對(duì)任意頂點(diǎn)數(shù)目的圖G都成立。

贊一下(1人)

回復(fù)此樓

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

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

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

查看全部 15 個(gè)回答

Edstrayer

版主 (著名寫手)

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

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

圖G是簡(jiǎn)單圖吧？
否則，易舉出反例的。
例如： $G=\{v_1,v_2,v_3\},E=\{v_1v_2,v_1v_2,v_1v_3,v_1v_3\}$ ，即G是三個(gè)頂點(diǎn)四條邊的含圈圖（不含成三角形的邊），其中

$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小時(shí)
蟲號(hào): 3137925
注冊(cè): 2014-04-15
專業(yè): 組合數(shù)學(xué)

引用回帖:

2樓: Originally posted by Edstrayer at 2014-08-11 12:16:04
圖G是簡(jiǎn)單圖吧？
否則，易舉出反例的。
例如：G=\{v_1,v_2,v_3\},E=\{v_1v_2,v_1v_2,v_1v_3,v_1v_3\}，即G是三個(gè)頂點(diǎn)四條邊的含圈圖（不含成三角形的邊），其中
d(v_1)=4,d(v_2)=d(v_3)=2,n=3,m=4
則有：
\sum ...

對(duì)，忘說(shuō)了，是簡(jiǎn)單圖，無(wú)圈無(wú)重邊的。

贊一下

回復(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小時(shí)
蟲號(hào): 3086598
注冊(cè): 2014-03-25
管轄: 數(shù)學(xué)

你沒(méi)有把問(wèn)題的條件敘述清楚吧？
這個(gè)問(wèn)題中的圖G對(duì)于含圈的簡(jiǎn)單圖也是成立的。
例如，設(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是五個(gè)頂點(diǎn)的含圈的簡(jiǎn)單圖，則有：

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

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

[考研] 085600 286分材料求調(diào)劑 +7	麻辣魷魚 2026-03-27	8/400	2026-03-28 12:17 by zllcz
[考研] 調(diào)劑 +3	好好讀書。 2026-03-28	3/150	2026-03-28 12:04 by 王保杰33
[考研] 學(xué)碩274求調(diào)劑 +6	Li李魚 2026-03-26	6/300	2026-03-28 11:16 by Awei099
[考研] 081200-314 +3	LILIQQ 2026-03-27	4/200	2026-03-28 09:41 by 保護(hù)地球你我做?/a>
[考研] 材料求調(diào)劑一志愿哈工大總分298分，前三科223分 +5	dongfang59 2026-03-27	5/250	2026-03-28 04:53 by wxiongid
[考研] 一志愿211院校 344分東北農(nóng)業(yè)大學(xué)生物學(xué)學(xué)碩，求調(diào)劑 +5	丶風(fēng)雪夜歸人丶 2026-03-26	8/400	2026-03-27 19:22 by 丶風(fēng)雪夜歸人丶
[考研] 322求調(diào)劑 +4	舊吢 2026-03-24	4/200	2026-03-27 15:38 by 不吃魚的貓
[考研] 0856調(diào)劑 +5	求求讓我有書讀?/a> 2026-03-26	6/300	2026-03-27 15:12 by caszguilin
[考研] 085600，材料與化工321分，求調(diào)劑 +9	大饞小子 2026-03-27	9/450	2026-03-27 14:30 by mmm just
[考研] 317求調(diào)劑 +5	十閑wx 2026-03-24	5/250	2026-03-27 13:48 by 楊楊楊紫
[考研] 考研調(diào)劑 +10	呼呼？~+123456 2026-03-24	10/500	2026-03-27 11:46 by wangjy2002
[考研] 315調(diào)劑 +4	0860求調(diào)劑 2026-03-26	5/250	2026-03-27 11:23 by wangjy2002
[考研] 294分080500材料科學(xué)與工程求調(diào)劑 +4	柳溪邊 2026-03-26	4/200	2026-03-26 21:14 by XPU李慶
[考研] 一志愿北京化工大學(xué)材料與化工（085600）296求調(diào)劑 +9	稻妻小編 2026-03-26	9/450	2026-03-26 16:16 by 不吃魚的貓
[考研] 085600 材料與化工 329分求調(diào)劑 +9	Mr. Z 2026-03-25	9/450	2026-03-26 10:36 by baoball
[考研] 0854AI CV方向招收調(diào)劑 +4	章小魚567 2026-03-23	4/200	2026-03-25 17:04 by CoderLoser
[考研] 285求調(diào)劑 +3	AZMK 2026-03-24	3/150	2026-03-25 12:23 by userper
[考研] 一志愿武理085500機(jī)械專業(yè)總分300求調(diào)劑 +3	an10101 2026-03-24	7/350	2026-03-25 00:00 by 山鬼0-
[考研] 300求調(diào)劑，材料科學(xué)英一數(shù)二 +5	leaflight 2026-03-24	5/250	2026-03-24 16:25 by laoshidan
[考研] 384求調(diào)劑 +3	子系博 2026-03-22	6/300	2026-03-23 21:45 by 子系博