Новое в системе Wolfram Mathematica 9 › Расширенная поддержка графов и сетей

Задачи о назначениях

Факультет математики хотел бы предложить семь курсов. На факультете имеются восемь профессоров, каждый из которых хотел бы преподавать определённые курсы. Найдём максимальное соответствие, в котором каждый профессор преподаёт только выбранные им курсы.

Построим двудольный граф, сопоставляющий профессоров и курсы, которые они хотели бы преподавать.

In[1]:=

g = \!\(\*
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}]\);

Максимальный поток от всех профессоров ко всем курсам даёт искомое соответствие.

In[2]:=

In[3]:=

Out[3]=