모서리 수 Noe와 정점 수 Nov가 주어집니다. 목표는 모서리가 없고 정점 수가 없는 그래프에서 가능한 최소 및 최대 고립 정점 수를 찾는 것입니다.
격리된 정점은 연결된 가장자리가 없는 정점입니다.
- 최소 격리 정점의 경우
우리는 모든 가장자리가 격리되었는지 확인합니다. ( 두 모서리에는 공통 정점이 없습니다 ) 각 모서리에는 2 개의 정점만 필요합니다. 그래서,
분리되지 않은 정점 수 =2 * 아니요. 가장자리
고립된 정점의 수 =총 정점 - 고립되지 않은 정점의 수.
아니오. 정점의 수는 <=2 * no입니다. 모서리 수는 모든 정점에 모서리가 연결되어 있음을 의미합니다. 격리된 정점의 개수는 0입니다.
- 최대 격리 정점용
이를 위해 우리는 모든 가장자리가 최소 정점으로 연결되도록 다각형을 만들려고 합니다. 각 정점 쌍이 그들 사이에 대각선을 갖도록 다각형이 있을 때 가능합니다.
5개의 꼭짓점과 6개의 모서리가 있는 경우 정사각형은 4개의 꼭짓점만 차지하도록 2개의 대각선이 있는 6개의 모서리가 있는 다각형입니다. 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.
설명 - 2개 이상의 꼭지점 사이에 에지가 형성된다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
정수 no와 nov는 no를 포함합니다. 가장자리와 꼭짓점.
-
findisolatedvertices(int v, int e) 함수는 모서리와 꼭짓점을 매개변수로 취하고 가능한 최소 및 최대 격리 꼭짓점을 인쇄합니다.
-
아니오. 정점의 수는 <=2*e이며, 고립된 정점이 없음을 의미합니다. 다른 격리되지 않은 정점은 2*e(최대)이므로 최소 격리는 v-2*e가 됩니다.
-
최대 격리 정점을 계산하려면 i=1에서 시작하여 no로 설정합니다. (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