一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有多少條邊？1、具有n個(gè)頂點(diǎn)的強(qiáng)連通圖最多有n（n-1）條邊，最少有n條邊。首先，有向連通性的一個(gè)必要條件是無(wú)向基圖連通性，即e>=n-1。其次，我們證明了E> n-

一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有多少條邊？

1、具有n個(gè)頂點(diǎn)的強(qiáng)連通圖最多有n（n-1）條邊，最少有n條邊。首先，有向連通性的一個(gè)必要條件是無(wú)向基圖連通性，即e>=n-1。其次，我們證明了E> n-1。當(dāng)e=n-1時(shí)，無(wú)向基圖是一棵樹(shù)，從s到T只有一條無(wú)向路徑，如果有向路徑s->T是連通的，則有向路徑T->S必須不存在。再次證明e=n，設(shè)n個(gè)頂點(diǎn)V1，V2，。。。VN可以依次與有向邊V1V2，v2v3連接。。。Vn-1vn，vnv1。這個(gè)環(huán)是定向連接的。所以至少有n條邊。2、 大多數(shù)情況下：即n個(gè)頂點(diǎn)成對(duì)連接。如果不考慮方向，則n個(gè)頂點(diǎn)成對(duì)連接并具有n（n-1）/2條邊。由于強(qiáng)連通圖是一個(gè)有向圖，每條邊都有兩個(gè)方向n（n-1）/2×2=n（n-1），因此一個(gè)有n個(gè)頂點(diǎn)的強(qiáng)連通圖最多有n（n-1）條邊。