Application Areas

Independent Edge Sets

The maximum independent edge set suggests who should marry whom.

In[1]:=

g = \!\(\*

GraphicsBox[

NamespaceBox["NetworkGraphics",

DynamicModuleBox[{Typeset`graph = HoldComplete[

Graph[{"Rudy", "Oscar", "Michael", "Larry", "John", "James", "David",

"Ben", "Nora", "Nancy", "Linda", "Julia", "Felicia",

"Elisabeth", "Dorothy", "Carol", "Arlene", "Anna"}, {

Null, {{7, 10}, {4, 11}, {1, 18}, {6, 17}, {4, 14}, {2,

16}, {2, 12}, {4, 18}, {6, 13}, {8, 15}, {5, 15}, {4, 15}, {

3, 18}, {7, 17}, {8, 9}, {7, 11}, {5, 16}, {4, 10}, {6,

10}, {3, 17}}}, {EdgeStyle -> {

Thickness[Large]}, ImageSize -> {350, Automatic},

PlotRange -> {{-0.2, 1.3}, {-0.6, 0.6}},

VertexCoordinates -> {{0., -0.4153465511805146}, {

0., -0.29667610798608185`}, {0., -0.17800566479164912`}, {

0., -0.059335221597216374`}, {0., 0.059335221597216374`}, {

0., 0.17800566479164912`}, {0., 0.29667610798608185`}, {0.,

0.4153465511805146}, {1., -0.5340169943749473}, {

1., -0.4153465511805146}, {1., -0.29667610798608185`}, {

1., -0.17800566479164912`}, {1., -0.059335221597216374`}, {

1., 0.059335221597216374`}, {1., 0.17800566479164912`}, {

1., 0.29667610798608185`}, {1., 0.4153465511805146}, {1.,

0.5340169943749473}}, VertexLabels -> {"Nancy" -> Placed[

Style["Nancy", FontFamily -> "Verdana"], After], "Michael" -> Placed[

Style["Michael", FontFamily -> "Verdana"], Before], "Oscar" -> Placed[

Style["Oscar", FontFamily -> "Verdana"], Before], "David" -> Placed[

Style["David", FontFamily -> "Verdana"], Before], "Rudy" -> Placed[

Style["Rudy", FontFamily -> "Verdana"], Before], "Larry" -> Placed[

Style["Larry", FontFamily -> "Verdana"], Before], "Arlene" -> Placed[

Style["Arlene", FontFamily -> "Verdana"], After], "James" -> Placed[

Style["James", FontFamily -> "Verdana"], Before], "Anna" -> Placed[

Style["Anna", FontFamily -> "Verdana"], After], "John" -> Placed[

Style["John", FontFamily -> "Verdana"], Before], "Felicia" -> Placed[

Style["Felicia", FontFamily -> "Verdana"], After], "Linda" -> Placed[

Style["Linda", FontFamily -> "Verdana"], After], "Nora" -> Placed[

Style["Nora", FontFamily -> "Verdana"], After], "Julia" -> Placed[

Style["Julia", FontFamily -> "Verdana"], After], "Dorothy" -> Placed[

Style["Dorothy", FontFamily -> "Verdana"], After], "Carol" -> Placed[

Style["Carol", FontFamily -> "Verdana"], After], "Ben" -> Placed[

Style["Ben", FontFamily -> "Verdana"], Before], "Elisabeth" -> Placed[

Style["Elisabeth", FontFamily -> "Verdana"], After]},

VertexSize -> {Large}}]], Typeset`boxes = GraphicsGroupBox[{{

Directive[

Hue[0.6, 0.2, 0.8],

EdgeForm[

Directive[

GrayLevel[0],

Opacity[0.7]]]],

TagBox[{

TagBox[

DiskBox[{0., -0.4153465511805146}, 0.02373408863888654],

"DynamicName", BoxID -> "VertexID$1"],

InsetBox[

FormBox[

StyleBox["\"Rudy\"", FontFamily -> "Verdana", StripOnInput -> False],

TraditionalForm],

Offset[{-2, 0},

DynamicLocation["VertexID$1", Automatic, Left]],

ImageScaled[{1, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$1"],

TagBox[{

TagBox[

DiskBox[{0., -0.29667610798608185`}, 0.02373408863888654],

"DynamicName", BoxID -> "VertexID$2"],

InsetBox[

FormBox[

StyleBox["\"Oscar\"", FontFamily -> "Verdana", StripOnInput -> False],

TraditionalForm],

Offset[{-2, 0},

DynamicLocation["VertexID$2", Automatic, Left]],

ImageScaled[{1, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$2"],

TagBox[{

TagBox[

DiskBox[{0., -0.17800566479164912`}, 0.02373408863888654],

"DynamicName", BoxID -> "VertexID$3"],

InsetBox[

FormBox[

StyleBox["\"Michael\"", FontFamily -> "Verdana",

StripOnInput -> False], TraditionalForm],

Offset[{-2, 0},

DynamicLocation["VertexID$3", Automatic, Left]],

ImageScaled[{1, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$3"],

TagBox[{

TagBox[

DiskBox[{0., -0.059335221597216374`}, 0.02373408863888654],

"DynamicName", BoxID -> "VertexID$4"],

InsetBox[

FormBox[

StyleBox["\"Larry\"", FontFamily -> "Verdana", StripOnInput -> False],

TraditionalForm],

Offset[{-2, 0},

DynamicLocation["VertexID$4", Automatic, Left]],

ImageScaled[{1, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$4"],

TagBox[{

TagBox[

DiskBox[{0., 0.059335221597216374`}, 0.02373408863888654],

"DynamicName", BoxID -> "VertexID$5"],

InsetBox[

FormBox[

StyleBox["\"John\"", FontFamily -> "Verdana", StripOnInput -> False],

TraditionalForm],

Offset[{-2, 0},

DynamicLocation["VertexID$5", Automatic, Left]],

ImageScaled[{1, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$5"],

TagBox[{

TagBox[

DiskBox[{0., 0.17800566479164912`}, 0.02373408863888654],

"DynamicName", BoxID -> "VertexID$6"],

InsetBox[

FormBox[

StyleBox["\"James\"", FontFamily -> "Verdana", StripOnInput -> False],

TraditionalForm],

Offset[{-2, 0},

DynamicLocation["VertexID$6", Automatic, Left]],

ImageScaled[{1, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$6"],

TagBox[{

TagBox[

DiskBox[{0., 0.29667610798608185`}, 0.02373408863888654],

"DynamicName", BoxID -> "VertexID$7"],

InsetBox[

FormBox[

StyleBox["\"David\"", FontFamily -> "Verdana", StripOnInput -> False],

TraditionalForm],

Offset[{-2, 0},

DynamicLocation["VertexID$7", Automatic, Left]],

ImageScaled[{1, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$7"],

TagBox[{

TagBox[

DiskBox[{0., 0.4153465511805146}, 0.02373408863888654], "DynamicName",

BoxID -> "VertexID$8"],

InsetBox[

FormBox[

StyleBox["\"Ben\"", FontFamily -> "Verdana", StripOnInput -> False],

TraditionalForm],

Offset[{-2, 0},

DynamicLocation["VertexID$8", Automatic, Left]],

ImageScaled[{1, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$8"],

TagBox[{

TagBox[

DiskBox[{1., -0.5340169943749473}, 0.02373408863888654],

"DynamicName", BoxID -> "VertexID$9"],

InsetBox[

FormBox[

StyleBox["\"Nora\"", FontFamily -> "Verdana", StripOnInput -> False],

TraditionalForm],

Offset[{2, 0},

DynamicLocation["VertexID$9", Automatic, Right]],

ImageScaled[{0, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$9"],

TagBox[{

TagBox[

DiskBox[{1., -0.4153465511805146}, 0.02373408863888654],

"DynamicName", BoxID -> "VertexID$10"],

InsetBox[

FormBox[

StyleBox["\"Nancy\"", FontFamily -> "Verdana", StripOnInput -> False],

TraditionalForm],

Offset[{2, 0},

DynamicLocation["VertexID$10", Automatic, Right]],

ImageScaled[{0, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$10"],

TagBox[{

TagBox[

DiskBox[{1., -0.29667610798608185`}, 0.02373408863888654],

"DynamicName", BoxID -> "VertexID$11"],

InsetBox[

FormBox[

StyleBox["\"Linda\"", FontFamily -> "Verdana", StripOnInput -> False],

TraditionalForm],

Offset[{2, 0},

DynamicLocation["VertexID$11", Automatic, Right]],

ImageScaled[{0, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$11"],

TagBox[{

TagBox[

DiskBox[{1., -0.17800566479164912`}, 0.02373408863888654],

"DynamicName", BoxID -> "VertexID$12"],

InsetBox[

FormBox[

StyleBox["\"Julia\"", FontFamily -> "Verdana", StripOnInput -> False],

TraditionalForm],

Offset[{2, 0},

DynamicLocation["VertexID$12", Automatic, Right]],

ImageScaled[{0, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$12"],

TagBox[{

TagBox[

DiskBox[{1., -0.059335221597216374`}, 0.02373408863888654],

"DynamicName", BoxID -> "VertexID$13"],

InsetBox[

FormBox[

StyleBox["\"Felicia\"", FontFamily -> "Verdana",

StripOnInput -> False], TraditionalForm],

Offset[{2, 0},

DynamicLocation["VertexID$13", Automatic, Right]],

ImageScaled[{0, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$13"],

TagBox[{

TagBox[

DiskBox[{1., 0.059335221597216374`}, 0.02373408863888654],

"DynamicName", BoxID -> "VertexID$14"],

InsetBox[

FormBox[

StyleBox["\"Elisabeth\"", FontFamily -> "Verdana",

StripOnInput -> False], TraditionalForm],

Offset[{2, 0},

DynamicLocation["VertexID$14", Automatic, Right]],

ImageScaled[{0, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$14"],

TagBox[{

TagBox[

DiskBox[{1., 0.17800566479164912`}, 0.02373408863888654],

"DynamicName", BoxID -> "VertexID$15"],

InsetBox[

FormBox[

StyleBox["\"Dorothy\"", FontFamily -> "Verdana",

StripOnInput -> False], TraditionalForm],

Offset[{2, 0},

DynamicLocation["VertexID$15", Automatic, Right]],

ImageScaled[{0, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$15"],

TagBox[{

TagBox[

DiskBox[{1., 0.29667610798608185`}, 0.02373408863888654],

"DynamicName", BoxID -> "VertexID$16"],

InsetBox[

FormBox[

StyleBox["\"Carol\"", FontFamily -> "Verdana", StripOnInput -> False],

TraditionalForm],

Offset[{2, 0},

DynamicLocation["VertexID$16", Automatic, Right]],

ImageScaled[{0, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$16"],

TagBox[{

TagBox[

DiskBox[{1., 0.4153465511805146}, 0.02373408863888654], "DynamicName",

BoxID -> "VertexID$17"],

InsetBox[

FormBox[

StyleBox["\"Arlene\"", FontFamily -> "Verdana",

StripOnInput -> False], TraditionalForm],

Offset[{2, 0},

DynamicLocation["VertexID$17", Automatic, Right]],

ImageScaled[{0, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$17"],

TagBox[{

TagBox[

DiskBox[{1., 0.5340169943749473}, 0.02373408863888654], "DynamicName",

BoxID -> "VertexID$18"],

InsetBox[

FormBox[

StyleBox["\"Anna\"", FontFamily -> "Verdana", StripOnInput -> False],

TraditionalForm],

Offset[{2, 0},

DynamicLocation["VertexID$18", Automatic, Right]],

ImageScaled[{0, 0.5}], BaseStyle -> "Graphics"]}, "DynamicName",

BoxID -> "VertexLabelID$18"]}, {

Directive[

Opacity[0.7],

Hue[0.6, 0.7, 0.5]],

Thickness[Large],

StyleBox[

LineBox[{

DynamicLocation["VertexID$1", Automatic, Center],

DynamicLocation["VertexID$18", Automatic, Center]}],