เราได้รับจำนวนเส้นขอบ (Noe) และจำนวนโหนด (Nov) เป้าหมายคือหาจำนวนโหนดโดดเดี่ยว (isolated vertices) น้อยที่สุดและมากที่สุดที่เป็นไปได้ในกราฟที่มีเส้นขอบและโหนดตามจำนวนนั้น
โหนดโดดเดี่ยวคือโหนดที่ไม่มีเส้นขอบเชื่อมต่อ
- สำหรับโหนดโดดเดี่ยวน้อยที่สุด (Minimum isolated vertices)
เราจะทำให้ทุกเส้นขอบโดดเดี่ยว (ไม่มีเส้นขอบ 2 เส้นใช้โหนดร่วมกัน) แต่ละเส้นขอบต้องการ 2 โหนด ดังนั้น
จำนวนโหนดที่ไม่โดดเดี่ยว = 2 * จำนวนเส้นขอบ
จำนวนโหนดโดดเดี่ยว = โหนดทั้งหมด - โหนดที่ไม่โดดเดี่ยว
หากจำนวนโหนด <= 2 * เส้นขอบ หมายความว่าโหนดทุกตัวมีเส้นขอบเชื่อม โหนดโดดเดี่ยว = 0
- สำหรับโหนดโดดเดี่ยวมากที่สุด (Maximum isolated vertices)
เราจะพยายามสร้างรูปหลายเหลี่ยมที่เส้นขอบทั้งหมดเชื่อมต่อด้วยโหนดน้อยที่สุด ซึ่งเป็นไปได้เมื่อมีรูปหลายเหลี่ยมที่ทุกคู่โหนดมีเส้นทแยงมุมเชื่อมกัน
ตัวอย่าง: 5 โหนด 6 เส้นขอบ รูปสี่เหลี่ยมมี 6 เส้นขอบ (4 ด้าน + 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.
คำอธิบาย
ตามรูปภาพด้านบน
อินพุต − no. of vertices 2, edges = 1
เอาต์พุต − Minimum isolated vertices 0. Maximum isolated vertices 0.
คำอธิบาย − เส้นขอบต้องมีอย่างน้อย 2 โหนด
วิธีการที่ใช้ในโปรแกรมด้านล่าง
- ตัวแปร noe และ nov เก็บจำนวนเส้นขอบและโหนด
- ฟังก์ชัน findisolatedvertices(int v, int e) พิมพ์โหนดโดดเดี่ยวน้อยที่สุดและมากที่สุด
- ถ้า v <= 2*e โหนดโดดเดี่ยว = 0 มิฉะนั้น โหนดไม่โดดเดี่ยวสูงสุด = 2*e โหนดโดดเดี่ยวน้อยที่สุด = v - 2*e
- หาโหนดโดดเดี่ยวมากที่สุด: ลูป i=1 ถึง v หาก i*(i-1)/2 >= e break (โหนด i ตัวพอสำหรับ e เส้นขอบ)
- i เก็บโหนดที่เชื่อมต่อได้ โหนดโดดเดี่ยวมากที่สุด = v - i
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
void findisolatedvertices(int v, int e) {
if (v <= 2 * e) {
cout << "Minimum no. of isolated vertices: " << 0 << endl;
} else {
int niso = 2 * e;
cout << "Minimum no. of isolated vertices: " << v - niso << endl;
}
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() {
int nov = 5;
int noe = 2;
findisolatedvertices(nov, noe);
return 0;
}
ผลลัพธ์
Minimum no. of isolated vertices: 1 Maximum no. of isolated vertices: 2
