 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 3 | 1/1 | 返回列表 |
| 查看: 457 | 回復(fù): 2 | ||
[求助]
請教一個圖論問題！
|
|
圖G是一個2-連通圖，即不存在割點。 證明：對于任意u∈V(G)，存在u的某個鄰點v，使得G－u－v連通。 |
回復(fù)此樓» 猜你喜歡
286求調(diào)劑
已經(jīng)有9人回復(fù)
-
一志愿南昌大學(xué)324求調(diào)劑
已經(jīng)有6人回復(fù)
-
0703化學(xué)/290求調(diào)劑/本科經(jīng)歷豐富/工科也可
已經(jīng)有10人回復(fù)
-
291求調(diào)劑
已經(jīng)有5人回復(fù)
-
308求調(diào)劑
已經(jīng)有7人回復(fù)
-
085404求調(diào)劑，總分309，本科經(jīng)歷較為豐富
已經(jīng)有4人回復(fù)
-
壓國家一區(qū)線，求導(dǎo)師收留，有恩必謝！
已經(jīng)有3人回復(fù)
-
一志愿中南大學(xué)化學(xué)0703總分337求調(diào)劑
已經(jīng)有4人回復(fù)
-
083000學(xué)碩274求調(diào)劑
已經(jīng)有6人回復(fù)
-
304求調(diào)劑
已經(jīng)有4人回復(fù)
» 本主題相關(guān)價值貼推薦，對您同樣有幫助:
- 請教一個電子能量的問題
已經(jīng)有6人回復(fù)
- 請教一個老問題：結(jié)構(gòu)優(yōu)化時的對稱性問題
已經(jīng)有17人回復(fù)
- 請教一個養(yǎng)細(xì)胞的問題！急！
已經(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é)
【答案】應(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到達(dá)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到達(dá)a2, 并且這條道路上僅有的v的鄰居就是an ,a(n-1),..,a3, 但是不用經(jīng)過a1. |
2樓2013-11-28 06:13:23
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
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 dameng 的主題更新
| 3 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 求調(diào)劑推薦 材料 304 +15 | 荷包蛋hyj 2026-03-26 | 15/750 |
|
|---|---|---|---|---|
|
|
[考研] 331環(huán)境科學(xué)與工程求調(diào)劑 +3 | 熠然好運氣 2026-03-27 | 3/150 |
|
|
|
[考研] 0856材料化工調(diào)劑 總分330 +10 | zhubinhao 2026-03-27 | 10/500 |
|
|
|
[考研] 265求調(diào)劑11408 +3 | 劉小鹿lu 2026-03-27 | 3/150 |
|
|
[考研] 292求調(diào)劑 +13 | 鵝鵝鵝額額額額?/a> 2026-03-25 | 14/700 |
|
|
|
[考研] 287求調(diào)劑 +10 | land xuxu 2026-03-26 | 10/500 |
|
|
|
[考研] 08開頭275求調(diào)劑 +4 | 拉誰不重要 2026-03-26 | 4/200 |
|
|
|
[考研] 085600，材料與化工321分調(diào)劑 +4 | 大饞小子 2026-03-27 | 6/300 |
|
|
|
[材料工程] 一志愿C9材料與化工專業(yè)總分300求調(diào)劑 +7 | 曼111 2026-03-24 | 8/400 |
|
|
|
[考研] 315調(diào)劑 +4 | 0860求調(diào)劑 2026-03-26 | 5/250 |
|
|
|
[考研] 314求調(diào)劑 +3 | 溪云珂 2026-03-26 | 3/150 |
|
|
|
[考研] 327求調(diào)劑 +7 | prayer13 2026-03-23 | 7/350 |
|
|
|
[考研] 中國科學(xué)院深圳先進技術(shù)研究院-光纖傳感課題組招生-中國科學(xué)院大學(xué)、深圳理工大學(xué)聯(lián)培 +5 | YangTyu1 2026-03-26 | 5/250 |
|
|
|
[考研] 材料專碩 335 分求調(diào)劑 +4 | 拒絕冷暴力 2026-03-25 | 4/200 |
|
|
|
[考研] 0854AI CV方向招收調(diào)劑 +4 | 章小魚567 2026-03-23 | 4/200 |
|
|
|
[考研] 0854電子信息求調(diào)劑 324 +4 | Promise-jyl 2026-03-23 | 4/200 |
|
|
|
[考研]
 材料考研調(diào)劑生
+3
|
黃粱一夢千年 2026-03-24 | 3/150 |
|
|
|
[基金申請] 請教下大家 2026年國家基金申請是雙盲審嗎？ +3 | lishucheng1 2026-03-22 | 5/250 |
|
|
|
[考研] 361求調(diào)劑 +3 | Glack 2026-03-22 | 3/150 |
|
|
|
[考研]
一志愿東華大學(xué)控制學(xué)碩320求調(diào)劑
+3
|
Grand777 2026-03-21 | 3/150 |
|