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

一個有n個頂點的無向圖最多有多少條邊？

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