MaxCut Problem
Student Exam Room Assignment
The Challenge
You are a proctor organizing an exam and need to assign students to two separate rooms. The challenge is that students who are friends with each other are more likely to cheat if they're placed in the same room. Your goal is to minimize the number of friendships within each room while maximizing the friendships that span across the two rooms.
Understanding the MaxCut Problem
This scenario represents a classic problem in computer science called the Maximum Cut (MaxCut) problem. In graph theory terms:
- Nodes (vertices) represent students
- Edges represent friendships between students
- The cut is the division of students into two rooms
- Goal: Maximize the number of edges that cross between the two groups
Student Exam Room Assignment
Each node represents a student, and lines show friendships. Assign students to rooms to minimize cheating opportunities!
Results
How to Use
Color Mode: Click on students to cycle through room assignments. Students are colored based on their assigned room.
Room Mode: Toggle to show room areas. You can either click students to assign rooms or drag them directly into the room areas.
Edge Visualization: Solid lines indicate students in the same room (potential cheating risk). Dashed lines show separated friendships (good for preventing cheating).