Re: [組合] 圖論
※ 引述《cuttlefish (無聊ing ><^> .o O)》之銘言：
: 圖論一題 應該不難只是沒學過不會XD
: n個點每兩點連一條邊顏色為red或blue, 總共有q條blue邊且每三點間必有一red邊.
: 試證明至少有一點滿足和其連red邊的那些點組成的子圖包含了不超過q(1-4q/n^2)條
: blue邊.
: 謝謝
設 d(v) 表點 v 所連藍邊數, D(v)=Σ{d(u):uv 為藍邊}
則 Σ{D(v):v in V}=Σ{d(v)^2:v in V}≧(1/n)(Σ{d(v):v in V})^2=4q^2/n
故存在 v in V 使得 D(v)≧4q^2/n^2, 此即為所求的 v 點
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.122.136.11
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1497454582.A.8DE.html
→
06/15 09:04, , 1F
06/15 09:04, 1F
推
06/19 06:40, , 2F
06/19 06:40, 2F
→
06/19 06:40, , 3F
06/19 06:40, 3F
→
06/19 16:58, , 4F
06/19 16:58, 4F
→
06/20 08:41, , 5F
06/20 08:41, 5F
→
06/22 13:29, , 6F
06/22 13:29, 6F
討論串 (同標題文章)