ค้นหา minimum cut ส่วนที่ 1
Connectivity บอกเราว่าต้องตัดกราฟออกเป็นสองกราฟย่อยที่แตกต่างกันอย่างน้อยกี่ครั้ง igraph มีสองฟังก์ชันที่ช่วยบอกได้ว่า vertex ใดถูกตัดออกเป็นสองกราฟย่อย และต้องตัดกี่ครั้ง ฟังก์ชันแรกคือ min_cut() ซึ่งจะคืนค่าการตัดทั้งหมด จำนวนครั้งที่ตัด และสองกราฟย่อยที่ได้ จำนวนครั้งที่ตัดจะแตกต่างกันระหว่างกราฟแบบมีทิศทางและไม่มีทิศทาง ในกราฟแบบมีทิศทาง จำนวนการตัดขั้นต่ำจะนับเฉพาะเส้นเชื่อมขาเข้า ส่วนกราฟแบบไม่มีทิศทางจะนับการตัดจากเส้นเชื่อมทั้งหมด
แบบฝึกหัดนี้เป็นส่วนหนึ่งของหลักสูตร
กรณีศึกษา: การวิเคราะห์เครือข่ายใน R
แบบฝึกหัดเชิงโต้ตอบแบบลงมือทำ
ลองทำแบบฝึกหัดนี้โดยเติมโค้ดตัวอย่างนี้ให้สมบูรณ์
# Calculate the minimum number of cuts
ud_cut <- min_cut(___, value.only = ___)
# See the result
ud_cut