11.1.2. Bipartite Graph

Now, what we have to do is allocate these courses to the teachers. Obviously, each course is going to be taught by exactly one teacher, but also we would like that each teacher teaches only one course and that course should be something that the teacher is willing to teach. So, we would not like an allocation for example, which asks Abbas to teach Math, because he has indicated that he is not comfortable in teaching Math. So, we want to find such an allocation that each course is taught by a single instructor, each instructor teaches only one course and that is a course which he or she is willing to teach.

The matching problem in this context involves assigning teaching responsibilities to teachers based on their preferences. Each course needs one teacher, and each teacher can only take on one course that they are comfortable teaching. This restriction ensures a viable and effective allocation of resources, which, in this case, are teachers and courses.

Think of a group of students selecting group projects. Each student has a list of projects they like to work on, just like teachers have preferences for the courses they want to teach. If each student can only take one project and each project requires one student, we must find the best way to match students to projects based on their preferences. Just as with teachers and courses, this ensures that everyone is engaged in a project they are interested in.

So, what is a bipartite graph? A bipartite graph is one in which the vertices come in two groups which we call v0 and v1 and all the edges go from v0 to v1. So, there are no edges inside v0. This is an example here, the teachers are v0 and the courses are v1. Now there are no edges between courses, there are no edges between teachers, all the edges are from a teacher to a course.

A bipartite graph consists of two distinct sets of vertices where edges only connect vertices from one set to the other. In our case, one set contains teachers (v0) and the other contains courses (v1). This structure prevents teachers from being connected directly and allows them to be matched only to the courses they are willing to teach.

Visualize a party where guests (teachers) can only talk to food tables (courses) set up around the room. Each guest prefers certain dishes, but they cannot interact with each other. The only connections in this scenario are between guests and food tables, illustrating the nature of a bipartite graph.

So, we want to find edges, such that no two of them share an endpoint. In this example, if two of them share an endpoint on the left, it means that the same teacher is being asked to teach two courses. If two edges share an endpoint on the right, it means that the same course has been taught to two different teachers. Either of it is which we want. So, you want a matching, we want a matching which is a subset of edges, so that no two of them share an endpoint.

In a bipartite matching, the goal is to select pairs (edges) such that no teacher is assigned more than one course, and no course is taught by more than one teacher. This means that we can visualize the matching as a connection where there are no overlaps; each selected pair uniquely identifies one teacher with one course.

Think about a dating app where users (teachers) can connect with potential dates (courses). Each user can only date one person, and likewise, each person can only be dated by one user at a time. A successful match means no one is double-booked, ensuring each pairing is exclusive.

And in particular, if we have an equal number of nodes on each side in a bipartite graph, then we can expect or hope that everything on the left is matched to something on the right. If we do not have an equal number of courses, something has been left out. But each edge would match out two people, suppose we have five teachers and four courses, then one teacher will not teach a course or we have four teachers and five courses, then some course will not be taught unless the teachers take two courses. But you have four teachers and four courses, you could ask whether there is a way of matching them up, so that every teacher teaches a course and every course is taught by a teacher. This is what is called a perfect match.

A perfect matching occurs when every member of one set (teachers) is matched to a unique member of another set (courses) without any leftover. This can only happen when the number of teachers equals the number of courses. If they are mismatched, it’s impossible to have a perfect assignment.

Imagine an organized seating arrangement at a school event where every student (teacher) must sit with a unique parent (course), ensuring that no two students or parents share the same seat. If there are an equal number of students and parents, perfect seating ensures that everyone is paired correctly.

So, here is how we can answer this question using network flows. We add a spurious source node feeding into the teachers and we add a spurious target node, a sink node coming out of the courses. So, now, we are trying to flow something from left to right. Now, what we want is to assign capacity one to everything, so every edge in this has capacity one.

To solve the matching problem with network flows, we introduce additional nodes (source and sink). All connections are directed from the source through the teachers to the sink at courses, with each connection restricted to a capacity of one. This prevents any pair from being matched more than once, mirroring the constraints of a bipartite matching scenario.

Imagine a water distribution system where a reservoir (source) supplies a set number of schools (teachers) with limited water (courses). Each school can receive only one unit of water at a time, ensuring that no school is overwhelmed with multiple supplies from the reservoir. This model helps visualize and control the flow of resources effectively.

--