有n個頂點的無向連通圖,最少有幾條邊

時間 2022-02-01 20:17:11

1樓:諾諾百科

一、有n個頂點的強連通圖最多有n(n-1)條邊,最少有n條邊。

首先,有向連通的一個必要條件是圖的無向底圖連通,這意味著e >= n-1。

其次,證明e > n-1。因當e=n-1時,無向底圖為樹,任取兩頂點s,t,從s到t有且只有一條無向路徑,若有向路徑s->t連通,則有向路徑t->s必不存在。得證:

再次,證明e可以=n。設n個頂點v1,v2,...vn,順次連線有向邊v1v2,v2v3...vn-1vn,vnv1,這個環是有向連通的。

因此最少有n條邊。

二、最多的情況:即n個頂點中兩兩相連,若不計方向,n個點兩兩相連有n(n-1)/2條邊,而由於強連通圖是有向圖,故每條邊有兩個方向,n(n-1)/2×2=n(n-1),故有n個頂點的強連通圖最多有n(n-1)條邊。

2樓:獨孤求答獎

設邊數為e

首先,有向連通的一個必要條件是圖的無向底圖連通,這意味著e >= n-1

其次,證明e > n-1.因當e=n-1時,無向底圖為樹,任取兩頂點s,t,從s到t有且只有一條無向路徑,若有向路徑s->t連通,則有向路徑t->s必不存在.得證

再次,證明e可以=n.設n個頂點v1,v2,...vn,順次連線有向邊v1v2,v2v3...vn-1vn,vnv1,這個環是有向連通的.

因此最少有n條邊.

對於一個具有n個頂點的無向圖,要連通所有頂點至少需要多少條邊

3樓:假面

連通是兩個頂點之間有路徑即連通,n-1條就夠了。

無向圖中的邊均是頂點的無序對,無序對通常用圓括號表示。

【例】無序對(vi,vj)和(vj,vi)表示同一條邊。

完全圖具有最多的邊數。任意一對頂點間均有邊相連。

4樓:匿名使用者

3個頂點,需要3條邊

4個頂點,需要6條邊

5個頂點,需要10條邊

。。。。。。

n個頂點,需要n(n-1)/2條邊

5樓:手屋一草

連通是兩個頂點之間有路徑即連通,n-1條就夠了

n個頂點的有向強連通圖最少有幾條邊!

6樓:希望有好大學讀

強連通圖必須從任何一點出發都可以回到原處,每個節點至少要一條出路。

所以至少有n條邊,正好可以組成一個環。

強連通圖是指在有向圖g中,如果對於每一對vi、vj,vi≠vj,從vi到vj和從vj到vi都存在路徑,則稱g是強連通圖。有向圖中的極大強連通子圖稱做有向圖的強連通分量。

7樓:墨汁諾

一、有n個頂點的強連通圖最多有n(n-1)條邊,最少有n條邊。

首先,有向連通的一個必要條件是圖的無向底圖連通,這意味著e >= n-1。

其次,證明e > n-1。因當e=n-1時,無向底圖為樹,任取兩頂點s,t,從s到t有且只有一條無向路徑,若有向路徑s->t連通,則有向路徑t->s必不存在。得證:

再次,證明e可以=n。設n個頂點v1,v2,...vn,順次連線有向邊v1v2,v2v3...vn-1vn,vnv1,這個環是有向連通的。

因此最少有n條邊。

二、最多的情況:即n個頂點中兩兩相連,若不計方向,n個點兩兩相連有n(n-1)/2條邊,而由於強連通圖是有向圖,故每條邊有兩個方向,n(n-1)/2×2=n(n-1),故有n個頂點的強連通圖最多有n(n-1)條邊。

8樓:匿名使用者

強連通圖必須從任何一點出發都可以回到原處,每個節點至少要一條出路(單節點除外)

至少有n條邊,正好可以組成一個環。

一個有n個頂點的無向連通圖,最少有幾條邊

9樓:假面

最少有n條邊。

設邊數為e。

首先,有向連通的一個必要條件是圖的無向底圖連通,這意味著e >= n-1。

其次,證明e > n-1。因當e=n-1時,無向底圖為樹,任取兩頂點s,t,從s到t有且只有一條無向路徑,若有向路徑s->t連通,則有向路徑t->s必不存在。得證:

再次,證明e可以=n。設n個頂點v1,v2,...vn,順次連線有向邊v1v2,v2v3...vn-1vn,vnv1,這個環是有向連通的。

因此最少有n條邊。

任意一條邊都代表u連v以及v連u。無向圖是相對於有向圖來說明的,就是說每條邊都是雙向邊,而有向圖每條邊都是單向邊,也就是說只能由一個點指向另一個點。

10樓:河傳楊穎

有n個頂點的強連通圖最多有n(n-1)條邊,最少有n條邊。

強連通圖是指一個有向圖中任意兩點v1、v2間存在v1到v2的路徑(path)及v2到v1的路徑的圖。

最多的情況:即n個頂點中兩兩相連,若不計方向,n個點兩兩相連有n(n-1)/2條邊,而由於強連通圖是有向圖,故每條邊有兩個方向,n(n-1)/2×2=n(n-1),故有n個頂點的強連通圖最多有n(n-1)條邊。

最少的情況:即n個頂點圍成一個圈,且圈上各邊方向一致,即均為順時針或者逆時針,此時有n條邊。

1、充分性:如果g中有一個迴路,它至少包含每個節點一次,則g中任兩個節點都是互相可達的,故g是強連通圖。

2、必要性:如果有向圖是強連通的,則任兩個節點都是相互可達。故必可做一回路經過圖中所有各點。

若不然則必有一回路不包含某一結點v,並且v與迴路上的個節點就不是相互可達,與強連通條件矛盾。

一個無向圖 g=(v,e) 是連通的,那麼邊的數目大於等於頂點的數目減一:|e|>=|v|-1,而反之不成立。

11樓:匿名使用者

設邊數為e

首先,有向連通的一個必要條件是圖的無向底圖連通,這意味著e >= n-1

其次,證明e > n-1.因當e=n-1時,無向底圖為樹,任取兩頂點s,t,從s到t有且只有一條無向路徑,若有向路徑s->t連通,則有向路徑t->s必不存在.得證

再次,證明e可以=n.設n個頂點v1,v2,...vn,順次連線有向邊v1v2,v2v3...vn-1vn,vnv1,這個環是有向連通的.

因此最少有n條邊.

12樓:我本熱情

一、有n個頂點的強連通圖最多有n(n-1)條邊,最少有n條邊。 首先,有向連通的一個必要條件是圖的無向底圖連通,這意味著e >= n-1。 其次,證明e > n-1。

因當e=n-1時,無向底圖為樹,任取兩頂點s,t,從s到t有且只有一條無向路徑,若有向路徑s->t連通,則有向路徑t->s必不存在。得證: 再次,證明e可以=n。

設n個頂點v1,v2,...vn,順次連線有向邊v1v2,v2v3...vn-1vn,vnv1,這個環是有向連通的。

因此最少有n條邊。 二、最多的情況:即n個頂點中兩兩相連,若不計方向,n個點兩兩相連有n(n-1)/2條邊,而由於強連通圖是有向圖,故每條邊有兩個方向,n(n-1)/2×2=n(n-1),故有n個頂點的強連通圖最多有n(n-1)條邊。

13樓:匿名使用者

強連通圖必須從任何一點出發都可以回到原處,每個節點至少要一條出路(單節點除外)至少有n條邊,正好可以組成一個環。

所以最少有n條邊。

設無向連通圖g有n個頂點,證明g至少有(n-1)條邊。

14樓:假面

設連通圖g有(n+1)個頂點,若每個頂點連出至少兩條邊,那麼此時至少有n+1條邊(任意圖上所有頂點度數和等於邊數的兩倍),結論已經成立。否則,那麼至少有一個頂點只連出一條邊。

不妨設為a,由於去掉這條邊ab後不影響其他點的連通性,那麼剩下的n個點之間有歸納假設至少有(n-1)條邊,所以g至少有n條邊。

任意一條邊都代表u連v以及v連u。無向圖是相對於有向圖來說明的,就是說每條邊都是雙向邊,而有向圖每條邊都是單向邊,也就是說只能由一個點指向另一個點。

n頂點無向連通圖最多幾條邊

15樓:一切自有巴自意

n!/[2! * (n-2)!]-1

就是n取2進行全組合再減去1, n取2進行全組合 為連通圖的邊數,減去1條邊就為非連通圖的最多的邊數了。

!就是階乘,4!就是4*3*2*1

n!就是n*(n-1)*(n-2)*……*2*1/ 為除號

N個頂點的有向強連通圖最少有幾條邊

希望有好大學讀 強連通圖必須從任何一點出發都可以回到原處,每個節點至少要一條出路。所以至少有n條邊,正好可以組成一個環。強連通圖是指在有向圖g中,如果對於每一對vi vj,vi vj,從vi到vj和從vj到vi都存在路徑,則稱g是強連通圖。有向圖中的極大強連通子圖稱做有向圖的強連通分量。 墨汁諾 一...

無向圖G有14條邊,有4度頂點 3度頂點,其餘頂點的

試卷代號 1009 廣播電視大學2007 2008學年度第二學期 開放本科 期末考試 半開卷 離散數學 本 試題 2008年7月 一 單項選擇題 每小題3分,本題共15分 1 設a b r1,r2,r3,是a到b的二元關係,且r1 r2 r3 則 不是從a到b的函式。a r1和r2 b r2 c.r...

設無向圖G有16條邊,4度頂點,3度頂點,其餘頂點的度數均大於3,請問G中至多有幾個頂點

angela韓雪倩 對於無向圖度數就是這個點連了多少邊,所以一個無向邊是對首尾兩個節點各貢獻一個度數,所以16條邊的無向圖,節點總度數是32,減去3個4度節點和4個3度節點,還剩8個度數,其餘節點的度數均不超過2。所以還剩至少4個節點,加起來是3個4度節點和4個3度節點和4個2度節點,至少11個節點...