Chúng tôi được cung cấp với số cạnh Noe và số đỉnh tháng 11. Mục tiêu là tìm số đỉnh cô lập tối thiểu và tối đa có thể có trong các đồ thị không có cạnh và không đếm đỉnh.
Đỉnh cô lập là đỉnh không có cạnh nào kết nối với nó.
- Đối với các đỉnh biệt lập nhỏ nhất
Chúng tôi sẽ đảm bảo rằng mọi cạnh đều được cách ly. (Không có hai cạnh nào có đỉnh chung) Mỗi cạnh chỉ yêu cầu 2 đỉnh. Vì vậy,
số đỉnh không cô lập =2 * không. của các cạnh
đếm các đỉnh cô lập =tổng số đỉnh - số lượng các đỉnh không cô lập.
Nếu không. của đỉnh là <=2 * không. của các cạnh, có nghĩa là tất cả các đỉnh đều có một cạnh được nối. của các đỉnh cô lập là 0.
- Đối với các đỉnh biệt lập tối đa
Đối với điều này, chúng tôi sẽ cố gắng tạo ra một đa giác sao cho tất cả các cạnh đều được nối với các cạnh cực tiểu.
Với 5 đỉnh và 6 cạnh đã cho, hình vuông là hình đa giác có 6 cạnh với 2 đường chéo mà chỉ có 4 đỉnh bị chiếm. 1 đỉnh trở nên bị cô lập và nó là cực đại.
Số đường chéo từ đỉnh này sang đỉnh khác của đa giác n cạnh là n * (n-3) / 2. Tổng số cạnh =n * (n-1) / 2
Đầu vào
No. of vertices 5, edges 6
Đầu ra
Minimum isolated vertices 0. Maximum isolated vertices 1.
Giải thích
Như trong hình trên.
Đầu vào - không. đỉnh 2, cạnh =1
Đầu ra - Các đỉnh cô lập tối thiểu 0. Các đỉnh cô lập tối đa 0.
Giải thích - Một cạnh được hình thành giữa ít nhất hai đỉnh.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Các số nguyên noe và nov chứa số không. của các cạnh và đỉnh.
-
Hàm findisolatedvertices (int v, int e) lấy các cạnh và đỉnh làm tham số và in các đỉnh cô lập tối thiểu và tối đa có thể.
-
Nếu không. của đỉnh là <=2 * e, nghĩa là không có đỉnh biệt lập. Các đỉnh không bị cô lập khác là 2 * e (tối đa), do đó, tối thiểu bị cô lập sẽ là v-2 * e.
-
Để tính toán các đỉnh cô lập tối đa, hãy bắt đầu từ i =1 đến không. trong số các đỉnh, nếu (i * (i - 1) / 2> =e) phá vỡ vì chỉ có đỉnh i là đủ cho các cạnh e.
-
tôi lưu trữ các đỉnh cô lập tối đa có thể.
Ví dụ
#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;
} Đầu ra
Minimum no. of isolated vertices: 1 Maximum no. of isolated vertices: 2