 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 5 | 1/1 | 返回列表 |
| 查看: 459 | 回復(fù): 2 | ||
| 當(dāng)前只顯示滿足指定條件的回帖，點擊這里查看本話題的所有回帖 | ||
[求助]
請教一個圖論問題！
|
||
|
圖G是一個2-連通圖，即不存在割點。 證明：對于任意u∈V(G)，存在u的某個鄰點v，使得G－u－v連通。 |
回復(fù)此樓» 猜你喜歡
壓國家一區(qū)線，求導(dǎo)師收留，有恩必謝！
已經(jīng)有4人回復(fù)
-
081200-314
已經(jīng)有4人回復(fù)
-
289求調(diào)劑
已經(jīng)有9人回復(fù)
-
085405 考的11408求各位老師帶走
已經(jīng)有3人回復(fù)
-
339求調(diào)劑
已經(jīng)有6人回復(fù)
-
材料與化工272求調(diào)劑
已經(jīng)有4人回復(fù)
-
085701環(huán)境工程，267求調(diào)劑
已經(jīng)有15人回復(fù)
-
材料求調(diào)劑一志愿哈工大324
已經(jīng)有9人回復(fù)
-
292求調(diào)劑
已經(jīng)有15人回復(fù)
-
304求調(diào)劑
已經(jīng)有5人回復(fù)
» 本主題相關(guān)價值貼推薦，對您同樣有幫助:
- 請教一個電子能量的問題
已經(jīng)有6人回復(fù)
- 請教一個老問題：結(jié)構(gòu)優(yōu)化時的對稱性問題
已經(jīng)有17人回復(fù)
- 請教一個養(yǎng)細胞的問題！急！
已經(jīng)有9人回復(fù)
- 求助，如何將一個圖劃分為幾個大小相等的集群并集群間的互聯(lián)度最小
已經(jīng)有5人回復(fù)
- 呼喚圖論高手！關(guān)于圖論中子圖間連通度的問題。
已經(jīng)有4人回復(fù)
- 請教一個問題，自旋多重度為什么是2S+1? 它的意義又是什么？
已經(jīng)有10人回復(fù)
- 請教一個小問題，capping agent 要怎么翻譯呢？
已經(jīng)有15人回復(fù)
- 請教一個關(guān)于相似度檢查的問題
已經(jīng)有6人回復(fù)
- 再請教一個shell命令批處理問題
已經(jīng)有8人回復(fù)
- SCI大修錄用經(jīng)歷
已經(jīng)有7人回復(fù)
- 弱問：運籌學(xué)和圖論有什么聯(lián)系？
已經(jīng)有6人回復(fù)
- APL 奇怪， 沒有Editorial Office，直接Under Consideration - Editor
已經(jīng)有10人回復(fù)
- 請教一個CCDC的小問題
已經(jīng)有8人回復(fù)
- 請教一個關(guān)于測序峰圖的問題
已經(jīng)有5人回復(fù)
- 請教一個烯丙基溴反應(yīng)的問題
已經(jīng)有9人回復(fù)
- 請教一個while loop程序的問題
已經(jīng)有5人回復(fù)
- 請教一個問題：用商用盜版軟件仿真的結(jié)果發(fā)表論文會不會有麻煩？
已經(jīng)有6人回復(fù)
- 【請教】請教一個六方晶系的問題
已經(jīng)有12人回復(fù)
- 【請教】請教一個關(guān)于圖片精度的問題
已經(jīng)有6人回復(fù)
- 【求助】請教一個m062x的問題
已經(jīng)有7人回復(fù)
- 【求助】關(guān)于圖像分割的一個問題
已經(jīng)有9人回復(fù)
- 【求助】請教 科研學(xué)術(shù)論文的寫作
已經(jīng)有15人回復(fù)
hank612
至尊木蟲 (著名寫手)
- 數(shù)學(xué)EPI: 14
- 應(yīng)助: 225 (大學(xué)生)
- 金幣: 14270.6
- 散金: 1055
- 紅花: 95
- 帖子: 1526
- 在線: 1375.8小時
- 蟲號: 2530333
- 注冊: 2013-07-03
- 性別: GG
- 專業(yè): 理論和計算化學(xué)
3樓2013-11-28 14:08:21
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
feixiaolin: 金幣+2, Hank612很活躍，常應(yīng)助一些疑難問題。頒數(shù)學(xué)EPI一枚。 2013-11-28 09:24:48
dameng: 金幣+20, ★★★★★最佳答案, 果然是高手！ 2013-11-28 11:46:35
感謝參與，應(yīng)助指數(shù) +1
feixiaolin: 金幣+2, Hank612很活躍，常應(yīng)助一些疑難問題。頒數(shù)學(xué)EPI一枚。 2013-11-28 09:24:48
dameng: 金幣+20, ★★★★★最佳答案, 果然是高手！ 2013-11-28 11:46:35
|
根據(jù)Menger定理, a graph is k-connected if and only if it contains k independent paths between any two vertices. 現(xiàn)在假設(shè)在圖 G-{v}中, 刪除任意一個鄰居(u~v), 都將使得G-{u}-{v}不連通. 這意味著,存在x,y 在G-{v}, 使得所有連接x到y(tǒng)的道路Path, 一定經(jīng)過u. 那么, x,y在G中一定有一條道路通過v, 并且跟上述經(jīng)過u的道路沒有在內(nèi)部相交.換句話說, 存在z,w 均為v的鄰居, 使得: x--z--v--w--y, 并且 z,w,u 均不相同. 下一步, 忘記所有不是v鄰居的頂點, 只考慮v鄰居們形成的三元組(z,u,w), 使它們滿足: 從z到w在G-{v}中必須要經(jīng)過u. 我們還可以額外要求, 從z到u不經(jīng)過v的任何鄰居, 從u到w也不經(jīng)過 v的任何鄰居. 我們可以證明, 一定有另外鄰居 a, 使得 (a, z, u). 要不然, 所有鄰居都可以不通過z到達u, 那么對頂點z, 它們可以通過u中轉(zhuǎn),就沒有三元組(a,z,b)以z為必經(jīng)之地了, 這和我們的假設(shè)不符. 那么, 由于v鄰居只有有限個, 所以一定有個頂點p, 使得, p - a1 -a2 -a3-...- an-p, 其中, p, a1,..,an各不相同, (p, a1, a2), (a1, a2, a3) 等等都是三元組. 可是, 這就是矛盾所在, 因為p可以反過來經(jīng)過an -a(n-1)-..-a3到達a2, 并且這條道路上僅有的v的鄰居就是an ,a(n-1),..,a3, 但是不用經(jīng)過a1. |
2樓2013-11-28 06:13:23
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 081200-314 +3 | LILIQQ 2026-03-27 | 4/200 |
|
|---|---|---|---|---|
|
[考研] 286求調(diào)劑 +10 | PolarBear11 2026-03-26 | 10/500 |
|
|
|
[考研] 085404求調(diào)劑，總分309，本科經(jīng)歷較為豐富 +4 | 來財aa 2026-03-25 | 4/200 |
|
|
|
[考研] 求調(diào)劑推薦 材料 304 +15 | 荷包蛋hyj 2026-03-26 | 15/750 |
|
|
|
[考研] 331環(huán)境科學(xué)與工程求調(diào)劑 +3 | 熠然好運氣 2026-03-27 | 3/150 |
|
|
|
[考研] 求調(diào)劑 +4 | 零八# 2026-03-27 | 4/200 |
|
|
|
[考研] 一志愿北化085600材料專碩275|有文章專利｜求調(diào)劑 +3 | Micky11223 2026-03-25 | 3/150 |
|
|
|
[考研] 求調(diào)劑 +6 | 林之夕 2026-03-24 | 6/300 |
|
|
|
[考研] 一志愿華理，數(shù)一英一285求A區(qū)調(diào)劑 +8 | AZMK 2026-03-25 | 10/500 |
|
|
|
[考研] 325求調(diào)劑 +3 | Aoyijiang 2026-03-23 | 3/150 |
|
|
|
[考研] 材料277求調(diào)劑 +5 | min3 2026-03-24 | 5/250 |
|
|
|
[考研] 尋找調(diào)劑 +5 | 倔強芒? 2026-03-21 | 8/400 |
|
|
|
[考研] 299求調(diào)劑 +4 | 15188958825 2026-03-25 | 4/200 |
|
|
|
[考研] 07化學(xué)303求調(diào)劑 +5 | 睿08 2026-03-25 | 5/250 |
|
|
|
[考研] 材料專碩 335 分求調(diào)劑 +4 | 拒絕冷暴力 2026-03-25 | 4/200 |
|
|
|
[考研] 0854電子信息求調(diào)劑 +7 | α____ 2026-03-22 | 9/450 |
|
|
|
[考研] 086003食品工程求調(diào)劑 +6 | 淼淼111 2026-03-24 | 6/300 |
|
|
|
[基金申請] 請教下大家 2026年國家基金申請是雙盲審嗎？ +3 | lishucheng1 2026-03-22 | 5/250 |
|
|
|
[考研] 384求調(diào)劑 +3 | 子系博 2026-03-22 | 6/300 |
|
|
|
[考研] 考研調(diào)劑 +3 | 呼呼？~+123456 2026-03-21 | 3/150 |
|