เราได้รับจำนวนขอบ Noe และจำนวนจุดยอดพฤศจิกายน เป้าหมายคือการหาจุดยอดที่แยกได้ขั้นต่ำและสูงสุดที่เป็นไปได้ในกราฟดังกล่าวซึ่งไม่มีขอบและไม่มีการนับจุดยอด
จุดยอดที่แยกออกมาเป็นจุดที่ไม่มีขอบเชื่อมต่ออยู่
- สำหรับจุดยอดแยกต่ำสุด
เราจะทำให้แน่ใจว่าทุกขอบถูกแยกออกจากกัน ( ไม่มีสองขอบที่มีจุดยอดร่วมกัน ) แต่ละขอบต้องการเพียง 2 จุดยอด ดังนั้น ,
นับจุดยอดไม่แยก =2 * ไม่ ของขอบ
การนับจุดยอดแยก =ยอดรวม - การนับจุดยอดที่ไม่แยก
ถ้าหมายเลข ของจุดยอดคือ <=2 * ไม่ใช่ ของขอบ หมายความว่าจุดยอดทั้งหมดมีขอบเชื่อมต่อกัน ดังนั้นไม่ ของจุดยอดแยกเป็น 0
- สำหรับจุดยอดสูงสุดแยก
สำหรับสิ่งนี้ เราจะพยายามสร้างรูปหลายเหลี่ยมโดยที่ขอบทั้งหมดเชื่อมต่อกับจุดยอดขั้นต่ำ ซึ่งเป็นไปได้เมื่อเรามีรูปหลายเหลี่ยมโดยที่จุดยอดแต่ละคู่มีเส้นทแยงมุมระหว่างกัน
สำหรับจุดยอด 5 จุดและ 6 ขอบที่กำหนด สี่เหลี่ยมจัตุรัสคือรูปหลายเหลี่ยมที่มี 6 ขอบโดยมี 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.
คำอธิบาย
ดังแสดงในรูปด้านบน
ป้อนข้อมูล - เลขที่ ของจุดยอด 2, ขอบ=1
ผลผลิต − จุดยอดแยกต่ำสุด 0 จุดยอดสูงสุดแยก 0
คำอธิบาย − ขอบถูกสร้างขึ้นระหว่างจุดยอดอย่างน้อยสองจุด
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
จำนวนเต็ม noe และ nov มีหมายเลข ของขอบและจุดยอด
-
ฟังก์ชัน 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
