鐵之狂傲

標題: [大學][離散][圖形與平面圖形][路徑與迴路]連通 [列印本頁]
作者: 闇之鬥魂    時間: 07-3-14 18:05
標題: [大學][離散][圖形與平面圖形][路徑與迴路]連通
問題一：

離散：『若將一有向圖中各頂點間的箭頭方向去掉，所成的無向圖是連通的，就稱作是連通，否則就叫做不連通。』

「否則」是基於哪種條件下才叫「否則」？能否舉例子？


問題二：

A→B的路徑有8條
B→A的路徑有7條

這樣我可以說A→B是強連通還是弱連通？
反之，B→A呢？


PS.問老師沒用，有答等於沒答，真想去教育部陳情老師素質低落……

[ 本文最後由 闇之鬥魂 於 07-3-14 06:07 PM 編輯 ]
作者: 傲月光希    時間: 07-3-14 22:40
原文由闇之鬥魂 於 07-3-14 06:05 PM 發表
問題一：

離散：『若將一有向圖中各頂點間的箭頭方向去掉，所成的無向圖是連通的，就稱作是連通，否則就叫做不連通。』

「否則」是基於哪種條件下才叫「否則」？能否舉例子？

"連通"的定義，就是圖中對所有的兩個頂點u,v，一定存在一條路徑，使得u跟v可以連在一起，就是你一定有辦法從u走到v

而否則就是將原命題給變成否命題，就是存在兩個頂點a,b使得對任意一條路徑都沒辦法讓它們連通

"對所有"的相反就是"存在"，反之亦然

假設一個圖G是不連通圖，則他裡面至少存在兩個圖是連通圖，也就是一個連通圖的所有點都不能連到另一個連通圖的點

這是我從我的圖論講義硬湊出來的結果(毆)，有錯請提醒我
未命名.jpg
原文由闇之鬥魂 於 07-3-14 06:05 PM 發表
問題二：

A→B的路徑有8條
B→A的路徑有7條

這樣我可以說A→B是強連通還是弱連通？
反之，B→A呢？

根據我講義的定義

"如果D的基礎圖G是連通的，則稱D是弱連通；如果對所有頂點u,v屬於V(D)都是有向相連，則稱D是強連通。"

因此連通是用來看整個圖的，並不是看當兩點的路徑多少能決定的

[ 本文最後由 傲月光希 於 07-3-14 10:58 PM 編輯 ]
作者: 闇之鬥魂    時間: 07-3-15 17:43
原文由 傲月光希 於 07-3-14 10:40 PM 發表
"連通"的定義，就是圖中對所有的兩個頂點u,v，一定存在一條路徑，使得u跟v可以連在一起，就是你一定有辦法從u走到v

而否則就是將原命題給變成否命題，就是存在兩個頂點a,b使得對任意一條路徑都沒辦法讓它們連通

"對所有"的相反就是"存在"，反之亦然

假設一個圖G是不連通圖，則他裡面至少存在兩個圖是連通圖，也就是一個連通圖的所有點都不能連到另一個連通圖的點

這是我從我的圖論講義硬湊出來的結果(毆)，有錯請提醒我

這句話是定理嗎？

文中所提到的圖G是指附件中的圖例對吧？
這樣算是一個圖？而非算二個？

原文由 傲月光希 於 07-3-14 10:40 PM 發表
根據我講義的定義

"如果D的基礎圖G是連通的，則稱D是弱連通；如果對所有頂點u,v屬於V(D)都是有向相連，則稱D是強連通。"

因此連通是用來看整個圖的，並不是看當兩點的路徑多少能決定的

請問什麼是基礎圖？
後半句我不太能理解……
作者: 傲月光希    時間: 07-3-15 19:11
原文由闇之鬥魂 於 07-3-15 05:43 PM 發表

這句話是定理嗎？

文中所提到的圖G是指附件中的圖例對吧？
這樣算是一個圖？而非算二個？

這是定義，不是定理

我所說的圖G可以是任意一個圖，附圖只是我舉例而已

這樣也可以算是一個圖，只是可以分成兩個連通圖，整個看起來就是一個不連通圖
請問什麼是基礎圖？
後半句我不太能理解……

你把一個有向圖D的方向給去掉，就是基礎圖G

像我附圖就不是一個強連通，也就是弱連通
我用圈圈起來的個別都是一個強連通

如圖示，這整個圖中有三個強連通圖，因此它本身不是個強連通
因為"D的強連通區就是D的最大強連通子圖，很明顯的，D是強連通若且唯若D只有一個強連通區"
因為如果一個如可以分割成兩個以上的強連通區，則必存在一對頂點，分別位於不同的強連通區，使得它們兩個沒有有向相連

假如一對頂點有連通的話，當然它們只會歸類到同一個強連通區，因此引號中的說明便成立了

未命名.JPG





歡迎光臨 鐵之狂傲 (https://gamez.com.tw/)