Re: [組合] 圖論

[XII (Mathkid)]

※ 引述《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
→ cuttlefish  : Thx
推 cuttlefish  : 突然想到你這個解法有個條件沒用到 所以那條件是多
→ cuttlefish  : 的?
→ XII         : 哪個條件?
→ cuttlefish  : 每三點必一紅邊那個
→ XII         : 證明的最後一句話會用到