資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中圖的孤立頂點數最大值和最小值
給定邊數Noe和頂點數Nov，目標是找到在沒有邊和No個頂點計數的圖中可能存在的孤立頂點的最小值和最大值。
孤立頂點是沒有連線到它的邊的頂點。
- 對於孤立頂點的最小值
我們將確保每條邊都是孤立的。（沒有兩條邊具有公共頂點）每條邊只需要2個頂點，所以：
非孤立頂點數 = 2 * 邊數
孤立頂點數 = 總頂點數 - 非孤立頂點數。
如果頂點數 <= 2 * 邊數，則表示所有頂點都連線到一條邊。所以孤立頂點數為0。
- 對於孤立頂點的最大值
為此，我們將嘗試建立一個多邊形，使得所有邊都與最少的頂點連線。當我們有一個多邊形，每個頂點對之間也有對角線時，這是可能的。
對於給定的5個頂點和6條邊，正方形是一個多邊形，它有6條邊和2條對角線，因此只有4個頂點被佔用。1個頂點成為孤立頂點，這是最大值。
n邊多邊形中從一個頂點到另一個頂點的對角線條數為n*(n-3)/2。總邊數=n*(n-1)/2
輸入
No. of vertices 5, edges 6
輸出
Minimum isolated vertices 0. Maximum isolated vertices 1.
解釋
如上圖所示。
輸入 - 頂點數2，邊數=1
輸出 - 孤立頂點的最小值0。孤立頂點的最大值0。
解釋 - 邊至少由兩個頂點形成。
下面程式中使用的演算法如下
整數noe和nov包含邊數和頂點數。
函式findisolatedvertices(int v, int e) 將邊數和頂點數作為引數，並列印可能的孤立頂點的最小值和最大值。
如果頂點數 <= 2*e，則表示沒有孤立頂點。否則，非孤立頂點數為2*e（最大值），所以最小孤立頂點數為v-2*e。
為了計算孤立頂點的最大值，從i=1開始到頂點數，如果(i * (i - 1) / 2 >= e)則中斷，因為只有i個頂點足以構成e條邊。
i儲存可能的最大孤立頂點數。
示例
#include <bits/stdc++.h>
using namespace std;
void findisolatedvertices(int v, int e){
//one edge has 2 vertices
if (v <= 2 * e) //means all veritces have a connected edge
cout << "Minimum no. of isolated vertices: " << 0 << endl;
else {
int niso=2*e; //maximum non isolated vertices
cout << "Minimum no. of isolated vertices: " << v - niso << endl;
}
// To find out maximum number of isolated
// vertices
// Loop to find out value of number of
// vertices that are connected
int i;
for (i = 1; i <= v; i++) {
if (i * (i - 1) / 2 >= e)
break;
}
cout <<endl<< "Maximum no. of isolated vertices: " <<v-i;
}
int main(){
// Number of vertices
int nov = 5;
// Number of edges
int noe = 2;
// Calling the function to maximum and
// minimum number of isolated vertices
findisolatedvertices(nov, noe);
return 0;
}輸出
Minimum no. of isolated vertices: 1 Maximum no. of isolated vertices: 2
更新於：2020年8月3日
396次瀏覽
廣告