# Assignment Problems

A math department would like to offer seven courses. There are eight professors, each of whom is willing to teach certain courses. Find a maximal matching where professors only teach courses they are interested in teaching.

#### Build a bipartite graph between professors and courses they are interested in teaching.

 In[1]:= Xg = \!\(\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{"Anne", "Kathy", "Erica", "Josh", "Rose", "Tim", "Vince", "Emmy", "M501", "M347", "M448", "M425", "M507", "M515", "M444"}, {{{2, 9}, {5, 9}, {2, 10}, {5, 10}, {8, 10}, {4, 11}, {6, 11}, {7, 11}, {1, 12}, {2, 12}, {7, 12}, {4, 13}, { 5, 13}, {2, 14}, {8, 14}, {1, 15}, {3, 15}, {4, 15}}, Null}, {GraphLayout -> "BipartiteEmbedding", VertexLabels -> { Placed["Name", Center]}, VertexLabelStyle -> { Directive[FontFamily -> "Ariel", 9.5, Bold]}, VertexSize -> {0.8}}]], Typeset`boxes, Typeset`boxes\$s2d = GraphicsGroupBox[{{ Arrowheads[0.040554001611066946`], Directive[ Opacity[0.7], Hue[0.6, 0.7, 0.5]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$1", Automatic, Center], DynamicLocation["VertexID\$12", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$1", Automatic, Center], DynamicLocation["VertexID\$15", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$2", Automatic, Center], DynamicLocation["VertexID\$9", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$2", Automatic, Center], DynamicLocation["VertexID\$10", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$2", Automatic, Center], DynamicLocation["VertexID\$12", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$2", Automatic, Center], DynamicLocation["VertexID\$14", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$3", Automatic, Center], DynamicLocation["VertexID\$15", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$4", Automatic, Center], DynamicLocation["VertexID\$11", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$4", Automatic, Center], DynamicLocation["VertexID\$13", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$4", Automatic, Center], DynamicLocation["VertexID\$15", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$5", Automatic, Center], DynamicLocation["VertexID\$9", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$5", Automatic, Center], DynamicLocation["VertexID\$10", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$5", Automatic, Center], DynamicLocation["VertexID\$13", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$6", Automatic, Center], DynamicLocation["VertexID\$11", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$7", Automatic, Center], DynamicLocation["VertexID\$11", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$7", Automatic, Center], DynamicLocation["VertexID\$12", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$8", Automatic, Center], DynamicLocation["VertexID\$10", Automatic, Center]}]], ArrowBox[ LineBox[{ DynamicLocation["VertexID\$8", Automatic, Center], DynamicLocation["VertexID\$14", Automatic, Center]}]]}, { Directive[ Hue[0.6, 0.2, 0.8], EdgeForm[ Directive[ GrayLevel[0], Opacity[0.7]]]], TagBox[{ TagBox[ DiskBox[{0., -0.4840169943749475}, 0.055316227928565415`], "DynamicName", BoxID -> "VertexID\$1"], InsetBox[ FormBox[ StyleBox["\"Anne\"", Directive[FontFamily -> "Ariel", 9.5, Bold], StripOnInput -> False], TraditionalForm], DynamicLocation["VertexID\$1", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID\$1"], TagBox[{ TagBox[ DiskBox[{0., -0.345726424553534}, 0.055316227928565415`], "DynamicName", BoxID -> "VertexID\$2"], InsetBox[ FormBox[ StyleBox["\"Kathy\"", Directive[FontFamily -> "Ariel", 9.5, Bold], StripOnInput -> False], TraditionalForm], DynamicLocation["VertexID\$2", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID\$2"], TagBox[{ TagBox[ DiskBox[{0., -0.20743585473212037`}, 0.055316227928565415`], "DynamicName", BoxID -> "VertexID\$3"], InsetBox[ FormBox[ StyleBox["\"Erica\"", Directive[FontFamily -> "Ariel", 9.5, Bold], StripOnInput -> False], TraditionalForm], DynamicLocation["VertexID\$3", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID\$3"], TagBox[{ TagBox[ DiskBox[{0., -0.06914528491070679}, 0.055316227928565415`], "DynamicName", BoxID -> "VertexID\$4"], InsetBox[ FormBox[ StyleBox["\"Josh\"", Directive[FontFamily -> "Ariel", 9.5, Bold], StripOnInput -> False], TraditionalForm], DynamicLocation["VertexID\$4", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID\$4"], TagBox[{ TagBox[ DiskBox[{0., 0.06914528491070679}, 0.055316227928565415`], "DynamicName", BoxID -> "VertexID\$5"], InsetBox[ FormBox[ StyleBox["\"Rose\"", Directive[FontFamily -> "Ariel", 9.5, Bold], StripOnInput -> False], TraditionalForm], DynamicLocation["VertexID\$5", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID\$5"], TagBox[{ TagBox[ DiskBox[{0., 0.20743585473212037`}, 0.055316227928565415`], "DynamicName", BoxID -> "VertexID\$6"], InsetBox[ FormBox[ StyleBox["\"Tim\"", Directive[FontFamily -> "Ariel", 9.5, Bold], StripOnInput -> False], TraditionalForm], DynamicLocation["VertexID\$6", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID\$6"], TagBox[{ TagBox[ DiskBox[{0., 0.345726424553534}, 0.055316227928565415`], "DynamicName", BoxID -> "VertexID\$7"], InsetBox[ FormBox[ StyleBox["\"Vince\"", Directive[FontFamily -> "Ariel", 9.5, Bold], StripOnInput -> False], TraditionalForm], DynamicLocation["VertexID\$7", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID\$7"], TagBox[{ TagBox[ DiskBox[{0., 0.4840169943749475}, 0.055316227928565415`], "DynamicName", BoxID -> "VertexID\$8"], InsetBox[ FormBox[ StyleBox["\"Emmy\"", Directive[FontFamily -> "Ariel", 9.5, Bold], StripOnInput -> False], TraditionalForm], DynamicLocation["VertexID\$8", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID\$8"], TagBox[{ TagBox[ DiskBox[{1.1063245585713086`, -0.41487170946424073`}, 0.055316227928565415`], "DynamicName", BoxID -> "VertexID\$9"], InsetBox[ FormBox[ StyleBox["\"M501\"", Directive[FontFamily -> "Ariel", 9.5, Bold], StripOnInput -> False], TraditionalForm], DynamicLocation["VertexID\$9", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID\$9"], TagBox[{ TagBox[ DiskBox[{1.1063245585713086`, -0.27658113964282716`}, 0.055316227928565415`], "DynamicName", BoxID -> "VertexID\$10"], InsetBox[ FormBox[ StyleBox["\"M347\"", Directive[FontFamily -> "Ariel", 9.5, Bold], StripOnInput -> False], TraditionalForm], DynamicLocation["VertexID\$10", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID\$10"], TagBox[{ TagBox[ DiskBox[{1.1063245585713086`, -0.13829056982141358`}, 0.055316227928565415`], "DynamicName", BoxID -> "VertexID\$11"], InsetBox[ FormBox[ StyleBox["\"M448\"", Directive[FontFamily -> "Ariel", 9.5, Bold], StripOnInput -> False], TraditionalForm], DynamicLocation["VertexID\$11", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID\$11"], TagBox[{ TagBox[ DiskBox[{1.1063245585713086`, 0.}, 0.055316227928565415`], "DynamicName", BoxID -> "VertexID\$12"], InsetBox[ FormBox[ StyleBox["\"M425\"", Directive[FontFamily -> "Ariel", 9.5, Bold], StripOnInput -> False], TraditionalForm], DynamicLocation["VertexID\$12", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID\$12"], TagBox[{ TagBox[ DiskBox[{1.1063245585713086`, 0.13829056982141358`}, 0.055316227928565415`], "DynamicName", BoxID -> "VertexID\$13"], InsetBox[ FormBox[ StyleBox["\"M507\"", Directive[FontFamily -> "Ariel", 9.5, Bold], StripOnInput -> False], TraditionalForm], DynamicLocation["VertexID\$13", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID\$13"], TagBox[{ TagBox[ DiskBox[{1.1063245585713086`, 0.27658113964282716`}, 0.055316227928565415`], "DynamicName", BoxID -> "VertexID\$14"], InsetBox[ FormBox[ StyleBox["\"M515\"", Directive[FontFamily -> "Ariel", 9.5, Bold], StripOnInput -> False], TraditionalForm], DynamicLocation["VertexID\$14", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID\$14"], TagBox[{ TagBox[ DiskBox[{1.1063245585713086`, 0.41487170946424073`}, 0.055316227928565415`], "DynamicName", BoxID -> "VertexID\$15"], InsetBox[ FormBox[ StyleBox["\"M444\"", Directive[FontFamily -> "Ariel", 9.5, Bold], StripOnInput -> False], TraditionalForm], DynamicLocation["VertexID\$15", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID\$15"]}}], \$CellContext`flag}, TagBox[ DynamicBox[GraphComputation`NetworkGraphicsBox[ 3, Typeset`graph, Typeset`boxes, \$CellContext`flag], { CachedValue :> Typeset`boxes, SingleEvaluation -> True, SynchronousUpdating -> False, TrackedSymbols :> {\$CellContext`flag}}, ImageSizeCache->{{7., 393.}, {-174.32000000000002`, 168.04363636363635`}}], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False, UnsavedVariables:>{\$CellContext`flag}]], DefaultBaseStyle->{ "NetworkGraphics", FrontEnd`GraphicsHighlightColor -> Hue[0.8, 1., 0.6]}, FrameTicks->None, ImageSize->{401., Automatic}]\);

#### The maximum flow from all professors to all courses show the matching.

 In[2]:= Xflowgraph = EdgeAdd[g, Union[Flatten[ EdgeList[ g] /. {a_ \[DirectedEdge] b_ :> {"s" \[DirectedEdge] a, b \[DirectedEdge] "t"}}]]];
 In[3]:= XVertexDelete[ FindMaximumFlow[flowgraph, "s", "t", "FlowGraph"], {"s", "t"}]
 Out[3]=