1樓：假面
最少有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。無向圖是相對於有向圖來說明的，就是說每條邊都是雙向邊，而有向圖每條邊都是單向邊，也就是說只能由乙個點指向另乙個點。
2樓：河傳楊穎
有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，而反之不成立。
3樓：匿名使用者
設邊數為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條邊.
4樓：我本熱情
一、有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）條邊。
5樓：匿名使用者
強連通圖必須從任何一點出發都可以回到原處，每個節點至少要一條出路(單節點除外)至少有n條邊，正好可以組成乙個環。
所以最少有n條邊。
對於乙個具有n個頂點的無向圖，要連通所有頂點至少需要多少條邊
6樓：假面
連通是兩個頂點之間有路徑即連通，n-1條就夠了。
無向圖中的邊均是頂點的無序對，無序對通常用圓括號表示。
【例】無序對(vi，vj)和(vj，vi)表示同一條邊。
完全圖具有最多的邊數。任意一對頂點間均有邊相連。
7樓：匿名使用者
3個頂點，需要3條邊
4個頂點，需要6條邊
5個頂點，需要10條邊
。。。。。。
n個頂點，需要n(n-1)/2條邊
8樓：手屋一草
連通是兩個頂點之間有路徑即連通，n-1條就夠了
設無向連通圖g有n個頂點，證明g至少有（n-1）條邊。
9樓：假面
設連通圖g有（n+1）個頂點，若每個頂點連出至少兩條邊，那麼此時至少有n+1條邊(任意圖上所有頂點度數和等於邊數的兩倍),結論已經成立。否則，那麼至少有乙個頂點只連出一條邊。
不妨設為a，由於去掉這條邊ab後不影響其他點的連通性，那麼剩下的n個點之間有歸納假設至少有（n-1)條邊，所以g至少有n條邊。
任意一條邊都代表u連v以及v連u。無向圖是相對於有向圖來說明的，就是說每條邊都是雙向邊，而有向圖每條邊都是單向邊，也就是說只能由乙個點指向另乙個點。
資料結構 要連通具有n個頂點的有向圖，至少需要n條邊，這是為什麼啊
10樓：angela韓雪倩
設邊數為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條邊。
連通圖G的頂點數字N，則G的生成樹的邊數是多少
飛若谷愈壬 首先完全圖是每一對頂點之間恰好有一條邊，乙個有n個頂點的完全圖，共有n n 1 2條邊。生成樹是原圖的極小連通子圖，包含原圖所有n個節點，並且保持圖連通的同時，邊最少。乙個有n個頂點的完全圖其生成樹有n 1條邊。生成樹中頂點數和邊數分別為n,n 1。這個問題十分簡單,上面兩位已給出了正確...
G是n階簡單無向圖，如果圖G中任意兩點的度數之和大於等於n
鈺瀟 先假設g不是連通的，則g至少有兩個連通分支g1和g2,有 g1 g2 g n 任取g1中一點v1,g2中一點v2，則d v1 g1 1,d v2 g2 1 d v1 d v2 g1 g2 2 n 2，與條件矛盾，故g只能是連通圖。在圖論中，連通圖基於連通的概念。在乙個無向圖 g 中，若從頂點i...
IP位址是固定的嗎？我怎麼查N次IP有N個結果
你用的是動態ip,是撥號的服務商 如電信 動態分配給你的，自然每啟動一次機器，可能在公網上的ip就變一次。如果要電信分給你固定ip,那是要花錢的。如果你是想在自己的電腦上作 可以用動態ip網域名稱解析軟體。n個結果只是埠號不同而已。一般在家上網的都不是固定ip 每重起一次機器ip就變。網咖的一般都有...