กลุ่มสูงสุดอธิบายด้วยสายตา

กลุ่มสูงสุดเป็นเทคนิคที่ใช้ในการค้นหาคลัสเตอร์จุดยอดที่ใหญ่ที่สุดโดยที่จุดยอดแต่ละจุดเชื่อมต่อถึงกัน ลองดูตัวอย่าง. เราจะตรวจสอบแต่ละจุดยอดและดูว่ากลุ่มที่ยิ่งใหญ่ที่สุดของกราฟต่อไปนี้จะเป็นเท่าใด

มาดูจุดยอดแรกกัน จุดยอด 1 เชื่อมต่อกับจุดยอด 2, 4 และ 6 เราจำเป็นต้องตรวจสอบให้แน่ใจว่าจุดยอดแต่ละจุดนั้นเชื่อมโยงถึงกันเช่นกัน

• จุดยอด 2 เชื่อมต่อกับจุดยอด 4 หรือไม่ ใช่
• จุดยอด 2 เชื่อมต่อกับจุดยอด 6 หรือไม่ ใช่
• จุดยอด 4 เชื่อมต่อกับจุดยอด 6 หรือไม่ ใช่

ดูเหมือนว่าจุดยอดทั้งหมดจะเชื่อมต่อถึงกัน ดังนั้นกลุ่มสูงสุดในปัจจุบันที่เราสังเกตจึงประกอบด้วยจุดยอด 4 จุด: 1, 2, 4 และ 6

มาตรวจสอบจุดยอด 2 กัน จุดยอด 2 เชื่อมต่อกับจุดยอด 1, 4, 3 และ 5 เราจำเป็นต้องตรวจสอบให้แน่ใจว่าจุดยอดแต่ละจุดนั้นเชื่อมโยงถึงกันเช่นกัน

• จุดยอด 1 เชื่อมต่อกับจุดยอด 3 หรือไม่ เลขที่

ไม่มีประโยชน์ที่จะดำเนินการต่อ ดูเหมือนว่าเราไม่สามารถใช้จุดยอดนั้นเป็นจุดศูนย์กลางของการสร้างกลุ่มสูงสุดได้ หากต้องการให้จุดยอด 2 เป็นจุดศูนย์กลางของกลุ่มสูงสุด จุดยอดทั้งหมดจะต้องเชื่อมต่อกันดังภาพด้านล่าง

มาตรวจสอบจุดยอด 3 กัน จุดยอด 3 เชื่อมต่อกับจุดยอด 2 และ 8

• จุดยอด 2 เชื่อมต่อกับจุดยอด 8 หรือไม่ เลขที่

หากต้องการเป็นส่วนหนึ่งของกลุ่ม จำเป็นต้องมีขอบที่เชื่อมต่อจุดยอด 2 ถึง 8

มาตรวจสอบจุดยอด 4 กัน จุดยอด 4 เชื่อมต่อกับจุดยอด 1, 2, 4, 5 และ 6 เราจำเป็นต้องตรวจสอบให้แน่ใจว่าจุดยอดแต่ละจุดนั้นเชื่อมโยงถึงกันเช่นกัน

• จุดยอด 1 เชื่อมต่อกับจุดยอด 2 หรือไม่ ใช่
• จุดยอด 1 เชื่อมต่อกับจุดยอด 5 หรือไม่ เลขที่

เราไม่สามารถใช้จุดยอด 4 เป็นจุดศูนย์กลางของการสร้างกลุ่มสูงสุดได้ ในการสร้างกลุ่ม จุดยอด 1 ต้องมีขอบถึงจุดยอด 5

มาตรวจสอบจุดยอด 5 กัน จุดยอด 5 เชื่อมต่อกับจุดยอด 2, 4, 6, 7 และ 8 เราจำเป็นต้องตรวจสอบให้แน่ใจว่าจุดยอดแต่ละจุดนั้นเชื่อมโยงถึงกันเช่นกัน

• จุดยอด 4 เชื่อมต่อกับ 6 หรือไม่ ใช่
• จุดยอด 4 เชื่อมต่อกับ 7 หรือไม่ เลขที่

เราไม่สามารถใช้จุดยอด 5 เป็นจุดศูนย์กลางของการสร้างกลุ่มสูงสุดได้ หากต้องการสร้างกลุ่ม จะต้องเชื่อมต่อจุดยอดทั้งหมดดังภาพด้านล่าง

มาตรวจสอบจุดยอด 6 กัน จุดยอด 6 เชื่อมต่อกับจุดยอด 1, 2, 4, 5 และ 7 เราจำเป็นต้องตรวจสอบให้แน่ใจว่าจุดยอดแต่ละจุดนั้นเชื่อมโยงถึงกันเช่นกัน

• จุดยอด 1 เชื่อมต่อกับ 2 หรือไม่? ใช่
• จุดยอด 1 เชื่อมต่อกับ 4 หรือไม่? ใช่
• จุดยอด 1 เชื่อมต่อกับ 5 หรือไม่ เลขที่

เราไม่สามารถใช้จุดยอด 6 เป็นจุดศูนย์กลางของการสร้างกลุ่มสูงสุดได้ หากต้องการสร้างกลุ่ม จะต้องเชื่อมต่อจุดยอดทั้งหมดดังภาพด้านล่าง

มาตรวจสอบจุดยอด 7 กัน จุดยอด 7 เชื่อมต่อกับจุดยอด 5 และ 6 เราจำเป็นต้องตรวจสอบให้แน่ใจว่าจุดยอดแต่ละจุดนั้นเชื่อมโยงถึงกันเช่นกัน

• จุดยอด 5 เชื่อมต่อกับ 6 หรือไม่ ใช่

จุดยอด 5, 6 และ 7 ก่อตัวเป็นกลุ่ม อย่างไรก็ตาม เราพบกลุ่มที่ใหญ่กว่ากลุ่มนี้แล้ว ดังนั้น นี่จึงไม่ใช่กลุ่มสูงสุด

มาตรวจสอบจุดยอด 8 กัน จุดยอด 8 เชื่อมต่อกับจุดยอด 3 และ 5 เราจำเป็นต้องตรวจสอบให้แน่ใจว่าจุดยอดแต่ละจุดนั้นเชื่อมโยงถึงกันเช่นกัน

• จุดยอด 3 เชื่อมต่อกับ 5 หรือไม่ เลขที่

เราไม่สามารถใช้จุดยอด 8 เป็นจุดศูนย์กลางของการสร้างกลุ่มสูงสุดได้ หากต้องการสร้างกลุ่ม จะต้องเชื่อมต่อกับจุดยอด 3 กับจุดยอด 5

เราได้ดูแต่ละจุดยอดเสร็จแล้ว กลุ่มสูงสุดที่เราพบคือกลุ่มที่ประกอบด้วยจุดยอด 1, 2, 4 และ 6

หากคุณชอบสิ่งที่คุณอ่าน ลองดูหนังสือของฉัน An Illustrative Introduction to Algorithms