離散數學割集是什麼意思

Ⅰ 圖論中的點割集，割點是什麼意思啊，看書上的定義看不懂，能不能通俗的講解一下

在無向聯通圖 G=(V,E)中：若對於x∈V， 從圖中刪去節點x以及所有與x關聯的邊之後， G分裂成兩個或兩個以上不相連的子圖， 則稱x為G的割點。 簡而言之， 割點是無向聯通圖中的一個特殊的點， 刪去中這個點後， 此圖不再聯通， 而所以滿足這個條件的點所構成的集合即為割點集合。

例如下圖中，頂點u和v都是割點，其他頂點都不是割點。

，x在u與w間的每條路上。

Ⅱ 離散數學連通分支以及點割集和邊割集是什麼意思

在一個無向圖G中，若從結點u到結點v存在一條路，則稱從u到v是可達的，或簡稱u可達v.對於無向圖來說，兩結點的可達關系是對稱的,如果u到v可達,則v到u也可達.可達關系也是傳遞的,如果u到v可達, v到w可達,則將結點u到結點v的路與v到結點w的路連接起來得到一條u到結點w的路，因此u到w可達. 另外約定結點到自身都是可達的.
在無向圖G中，如果結點u,v可達,則稱這兩點是連通的，如果圖G中任何兩點均是連通的，則稱圖是連通的,或稱該圖為連通圖,由於結點的可達關系對於無向圖來說，是結點集合上的等價關系，因此可達關系給出結點集合的一個劃分，劃分中的元素是一些等價類,每個等價類中的結點導出一個子圖，兩結點可達當且僅當它們屬於同一個子圖，稱這種子圖為的一個連通分支，圖G的連通分支個數記為w(G).顯然如果圖G只有一個連通分圖，則G是連通圖.
從一個圖中刪去一個結點，也將把與它關聯的邊刪去，刪去一條邊即將該邊從圖中抹去即可，一般來說刪去一些結點或刪去一些邊有可能改變圖的連通性，
設圖G=<V,E>,S是V的子集，T是E的子集,從圖G中的結點集V中刪去結點集S中的所有結點或從E中刪去邊集T中所有的邊而得到的子圖的使其連通分支個數增大，則稱S為G一個點割集，T為G一個邊割集。圖看：
http://hi..com/lca001/blog/item/39ec5c1e4430bec5a68669cf.html

Ⅲ 離散數學中的割邊和邊割集的定義，通俗易懂的

設無向圖，若存在頂點子集，使G刪除(將中頂點及其關聯的邊都刪除後)後，所得子圖的連通分支數與G的連通分支數滿足，而刪除的任何真子集後，，則稱為G的一個點割集。若點割集中只有一個頂點，則稱為割點。

又若存在邊集子集，使G刪除(將中的邊從G中全部刪除)後，所得子圖的連通分支數與G的連通分支數滿足，而刪除的任何真子集後，，則稱是G的一個邊割集，若邊割集中只有一條邊，則稱為割邊或橋。

在圖7.9中，，，為點割集，不是點割集，因為它的真子集已經是點割集了，類似地，也不是點割集。

，，，，等都是邊割集，其中是橋。不是割集，因為它的真子集已是邊割集。類似地，也不是邊割集。

今後常稱邊割集為割集。

Ⅳ 離散數學圖論里的點割集和邊割集的區別是什麼

一、指代不同

1、點割集：V是一些頂點的集合，如果刪除V中的所有頂點之後，G不在連通，但是對於V的任何真子集V1,刪除V1後G仍然連通。

2、邊割集：E是一些邊的集合，如果刪除E里的所有邊之後G不在連通，但是對於E的任何真子集E1,刪除E1之後G仍然連通，則稱E是邊割集。

二、性質不同

1、點割集：連通圖G的一個割集C至少包含G的任意生成樹的一個樹枝。

2、邊割集：如果把C移去而仍有一棵樹T存在，則圖是連通的，那麼C將不是一個割集。

三、特點不同

1、點割集：同一割集的所有支路上的電流滿足KCL。當割集中的所有支路都連接在同一結點上時，割集上的KCI方程就變成了結點上的KCL方程。

2、邊割集：一個連通圖，可以列出與割集數目相等的KCI方程，但這些方程並非都是線性獨立的。對於結點數為n支路數為b的連通圖來說，其獨立的KCI方程數為n-1個。

Ⅳ 離散數學的基本割集和基本迴路的定義是看書看不懂啊.

你說的問題在連通圖的生成樹這一節
基本割集是求最大生成樹以後剩的邊集設為A,則A並任意一條最大生成樹的邊都形成一個割集,把所有的割集放在一起形成基本割集系統.
基本迴路是在A中任取一條邊加入最大生成樹,則一定形成一條迴路,這條迴路就是基本迴路,所有的這樣的基本迴路放在一起就形成了基本迴路系統.

Ⅵ 離散數學連通分支以及點割集和邊割集是什麼意思

把一個大塊分成幾個小塊，每個小塊之間不連通，但是小塊內部連通，每一個小塊就是這個大塊的連通分支。
對於一個連通圖來說，把點割集的元素全刪了後，圖就不連通了，但是如果只刪了點割集的真子集，圖還是連通的。邊割集類似點割集。
這是我對這幾個東西的理解，希望能對你有幫助！