数据结构
网络
关系数据库管理系统 (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次浏览
广告