定義
-
完全圖
也稱(chēng)簡(jiǎn)單完全圖。一個(gè)圖任意兩個(gè)頂點(diǎn)之間都有邊的話，該圖就稱(chēng)為完全圖。 -
連通圖（一般都是指無(wú)向圖）
如果圖中任意倆頂點(diǎn)都連通，則該圖為連通圖。 -
有向圖
由點(diǎn)和弧所構(gòu)成的圖（強(qiáng)連通圖必然是有向圖，因?yàn)閺?qiáng)連通和弱連通的概念只在有向圖中存在） -
無(wú)向圖
由點(diǎn)和邊所構(gòu)成的圖 -
無(wú)向完全圖
在n個(gè)頂點(diǎn)的無(wú)向圖中，若有n(n-1)/2條邊，即任意兩個(gè)頂點(diǎn)之間有且僅有一條邊，則稱(chēng)此圖為無(wú)向完全圖 -
有向完全圖
在n個(gè)頂點(diǎn)的有向圖中，若有n(n-1)條邊，即任意兩個(gè)頂點(diǎn)之間有且僅有方向相反的邊，則稱(chēng)此圖為有向完全圖
一些總結(jié)
一個(gè)n個(gè)頂點(diǎn)的強(qiáng)連通圖，其邊數(shù)至少為n；
一個(gè)n個(gè)頂點(diǎn)的無(wú)向圖，其邊數(shù)至少為n-1;
一個(gè)n個(gè)頂點(diǎn)的無(wú)向完全圖，其邊數(shù)至少為n(n-1)/2 ;
一個(gè)n個(gè)頂點(diǎn)的有向完全圖，其邊數(shù)至少為n(n-1) ;
對(duì)于n個(gè)頂點(diǎn)的無(wú)向圖G，
若G是連通圖，則最少有n-1條邊；
若G是非連通圖，則最多有(n-1)(n-2)/2條邊
一個(gè)n個(gè)頂點(diǎn)的無(wú)向圖，保證其在任何情況下連通，其邊數(shù)至少為(n-1)(n-2)/2+1；
一個(gè)n個(gè)頂點(diǎn)的有向圖，保證其在任何情況下連通，其邊數(shù)至少為n(n-1)+1【待重新推導(dǎo)】
一個(gè)n個(gè)頂點(diǎn)的無(wú)向圖，若不連通，則它至多有(n-1)(n-2)/2個(gè)邊。
一個(gè)n個(gè)頂點(diǎn)的有向圖，若不連通，則它至多有n(n-1)【待重新推導(dǎo)】個(gè)邊。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-402288.html
注：筆者是在準(zhǔn)備數(shù)據(jù)結(jié)構(gòu)期末考試的時(shí)候?qū)懙倪@篇文章，當(dāng)時(shí)水平尚淺，有諸多錯(cuò)漏之處，現(xiàn)已改正部分。如果還有錯(cuò)漏之處和需要補(bǔ)充的地方，歡迎評(píng)論區(qū)留言。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-402288.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)|連通圖、完全圖、無(wú)向圖、有向圖的邊數(shù)計(jì)算問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
