โปรแกรม C++ คำนวณ Edge Cover ของกราฟ

บทนำ

กำหนดจำนวนจุด (vertices) n ของกราฟ ต้องการคำนวณ Edge Cover ซึ่งคือจำนวนขอบ (edges) น้อยที่สุดที่ต้องใช้เพื่อครอบคลุมทุกจุดในกราฟ

ตัวอย่าง

• n = 5 → Edge Cover = 3
• n = 8 → Edge Cover = 4

แนวคิด

Edge Cover = ceil(n / 2.0) คือ ค่าปัดขึ้นของ n หาร 2

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int edge(int n) {
    float val = 0;
    val = ceil(n / 2.0);
    return val;
}

int main() {
    int n = 10;
    cout << "minimum number of edges required are: " << edge(n);
    return 0;
}

ผลลัพธ์

minimum number of edges required are: 5