Chúng ta được cho số cạnh Noe và số đỉnh Nov. 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ị có số cạnh và đỉnh như vậy.
Một đỉnh cô lập là đỉnh không có cạnh nào kết nối với nó.
- Đối với đỉnh cô lập tối thiểu
Chúng ta sẽ đảm bảo mọi cạnh đều cô lập. (Không có hai cạnh chia sẻ đỉnh chung) Mỗi cạnh chỉ cần 2 đỉnh. Vì vậy,
số đỉnh không cô lập = 2 * số cạnh
số đỉnh cô lập = tổng đỉnh - số đỉnh không cô lập.
Nếu số đỉnh <= 2 * số cạnh, nghĩa là tất cả đỉnh đều có cạnh kết nối. Vì vậy số đỉnh cô lập là 0.
- Đối với đỉnh cô lập tối đa
Để làm điều này, chúng ta sẽ cố gắng tạo một đa giác sao cho tất cả các cạnh được kết nối với số đỉnh tối thiểu. Điều này có thể khi chúng ta có một đa giác mà mỗi cặp đỉnh cũng có đường chéo giữa chúng.
Với 5 đỉnh và 6 cạnh, hình vuông là đa giác có 6 cạnh với 2 đường chéo nên chỉ chiếm 4 đỉnh. 1 đỉnh trở nên cô lập và đó là tối đa.
Số đường chéo từ một đỉnh đến đỉnh khác trong đa giác n cạnh là n*(n-3)/2. Tổng cạnh = n*(n-1)/2.
Ví dụ
Đầu vào
Số đỉnh 5, cạnh 6
Đầu ra
Đỉnh cô lập tối thiểu 0. Đỉnh cô lập tối đa 1.
Giải thích − Như hình vẽ trên.
Đầu vào − số đỉnh 2, cạnh = 1
Đầu ra − Đỉnh cô lập tối thiểu 0. Đỉ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 sử dụng trong chương trình dưới đây
- Số nguyên noe và nov chứa số cạnh và đỉnh.
- Hàm findisolatedvertices(int v, int e) nhận số cạnh và đỉnh làm tham số và in ra đỉnh cô lập tối thiểu và tối đa có thể.
- Nếu số đỉnh <= 2*e, nghĩa là không có đỉnh cô lập. Ngược lại đỉnh không cô lập là 2*e (tối đa), nên đỉnh cô lập tối thiểu sẽ là v - 2*e.
- Để tính đỉnh cô lập tối đa, bắt đầu từ i=1 đến số đỉnh, nếu (i * (i - 1) / 2 >= e) break vì chỉ cần i đỉnh cho e cạnh.
- i lưu số đỉnh cô lập tối đa có thể.
Ví dụ mã nguồn
#include <bits/stdc++.h>
using namespace std;
void findisolatedvertices(int v, int e) {
// một cạnh có 2 đỉnh
if (v <= 2 * e) // nghĩa là tất cả đỉnh có cạnh kết nối
cout << "Số đỉnh cô lập tối thiểu: " << 0 << endl;
else {
int niso = 2 * e; // tối đa đỉnh không cô lập
cout << "Số đỉnh cô lập tối thiểu: " << v - niso << endl;
}
// Tìm số đỉnh cô lập tối đa
// Vòng lặp tìm giá trị số đỉnh được kết nối
int i;
for (i = 1; i <= v; i++) {
if (i * (i - 1) / 2 >= e)
break;
}
cout << endl << "Số đỉnh cô lập tối đa: " << v - i;
}
int main() {
// Số đỉnh
int nov = 5;
// Số cạnh
int noe = 2;
// Gọi hàm tìm đỉnh cô lập tối đa và tối thiểu
findisolatedvertices(nov, noe);
return 0;
}
Kết quả
Số đỉnh cô lập tối thiểu: 1 Số đỉnh cô lập tối đa: 2