(* Content-type: application/vnd.wolfram.mathematica *) (*** Wolfram Notebook File ***) (* http://www.wolfram.com/nb *) (* CreatedBy='Mathematica 10.0' *) (*CacheID: 234*) (* Internal cache information: NotebookFileLineBreakTest NotebookFileLineBreakTest NotebookDataPosition[ 158, 7] NotebookDataLength[ 49015, 1054] NotebookOptionsPosition[ 47272, 995] NotebookOutlinePosition[ 47631, 1011] CellTagsIndexPosition[ 47588, 1008] WindowFrame->Normal*) (* Beginning of Notebook Content *) Notebook[{ Cell[TextData[{ StyleBox["MAT 331:", FontSize->24], " ", StyleBox["Homework 2", FontSize->24] }], "Section", CellChangeTimes->{{3.618884780257655*^9, 3.618884795191327*^9}, { 3.619013741815179*^9, 3.619013742915434*^9}, {3.6190639773624067`*^9, 3.6190639931423893`*^9}, 3.6190640316767807`*^9, {3.620115017220894*^9, 3.620115018260913*^9}}], Cell[CellGroupData[{ Cell[TextData[StyleBox["Problem 2.1", "Subsection"]], "Section", CellChangeTimes->{{3.61895751446417*^9, 3.61895752344552*^9}, { 3.620185321017673*^9, 3.620185321160325*^9}}], Cell[TextData[{ "In this problem we will explore some of the basic definitions and ", StyleBox["Mathematica", FontSlant->"Italic"], " functions for graphs. A walk in a graph consists of an alternating \ sequence of vertices and edges ", Cell[BoxData[ FormBox[ SubscriptBox["x", "0"], TraditionalForm]]], ",", Cell[BoxData[ FormBox[ RowBox[{" ", RowBox[{ SubscriptBox["e", "1"], ","}]}], TraditionalForm]]], Cell[BoxData[ FormBox[ RowBox[{" ", RowBox[{ SubscriptBox["x", "1"], ","}]}], TraditionalForm]]], "..,", Cell[BoxData[ FormBox[ RowBox[{" ", SubscriptBox["e", "n"]}], TraditionalForm]]], ", ", Cell[BoxData[ FormBox[ SubscriptBox["x", "n"], TraditionalForm]]], " such that ", Cell[BoxData[ FormBox[ SubscriptBox["e", "i"], TraditionalForm]]], "=", Cell[BoxData[ FormBox[ SubscriptBox["x", RowBox[{"i", "-", "1"}]], TraditionalForm]]], "\[Rule]", Cell[BoxData[ FormBox[ SubscriptBox["x", "i"], TraditionalForm]]], " is an edge between vertex ", Cell[BoxData[ FormBox[ SubscriptBox["x", RowBox[{"i", "-", "1"}]], TraditionalForm]]], "and vertex ", Cell[BoxData[ FormBox[ SubscriptBox["x", "i"], TraditionalForm]]], ". A walk is closed if ", Cell[BoxData[ FormBox[ SubscriptBox["x", "0"], TraditionalForm]]], "=", Cell[BoxData[ FormBox[ SubscriptBox["x", "n"], TraditionalForm]]], " and open otherwise. The number of edges is the length of a walk. The \ vertices and edges may be repeated in a walk. A path is (usually defined as) \ an open walk with no repeated vertices. A cycle is a closed walk with no \ repeated vertices, other than the first and last vertex. The problem of \ finding the shortest path between two vertices is very relevant to practical \ problems, such as finding the way out of a maze or navigating a road network. \ Cycles are also very important if traversing the whole graph in some way and \ coming back to the same place is desired instead. \nAnother relevant feature \ of graphs representing real systems is community structure, or clustering, i. \ e. the organization of vertices in clusters, with many edges joining vertices \ of the same cluster and comparatively few edges joining vertices of different \ clusters. Such clusters, or communities, can be considered as fairly \ independent compartments of a graph, playing a similar role like, e. g., the \ tissues or the organs in the human body. Detecting communities is of great \ importance in sociology, biology and computer science, disciplines where \ systems are often represented as graphs.\n" }], "Text", CellChangeTimes->{{3.618958035675892*^9, 3.61895825489732*^9}, { 3.61895828758503*^9, 3.618958309439242*^9}, {3.6190090575312862`*^9, 3.619009060737265*^9}, {3.619009133231318*^9, 3.6190091577092857`*^9}, { 3.619009297082733*^9, 3.619009305010374*^9}, {3.6190531597810783`*^9, 3.619053163786626*^9}, {3.619057974295499*^9, 3.619058008308049*^9}, { 3.619063099075738*^9, 3.619063221510716*^9}, {3.620104581154149*^9, 3.620104624460071*^9}, 3.620104952514773*^9, {3.620105306189464*^9, 3.62010549225408*^9}, {3.620106757254405*^9, 3.620106783973249*^9}, { 3.62010690214373*^9, 3.6201069404389887`*^9}, {3.620107003675831*^9, 3.620107046135168*^9}, {3.6201072140945473`*^9, 3.6201072521827602`*^9}, { 3.620107296382296*^9, 3.620107686022007*^9}, {3.6201087715394707`*^9, 3.620108772193202*^9}, {3.620108906139463*^9, 3.620108911090001*^9}, { 3.620108943078869*^9, 3.620108945423254*^9}, 3.620113287306345*^9, { 3.620113350538128*^9, 3.620113413916574*^9}, {3.620113448356659*^9, 3.620113599560532*^9}, {3.620114665213971*^9, 3.620114736951397*^9}, { 3.6201148474850683`*^9, 3.6201148752584467`*^9}, {3.620114909764741*^9, 3.620114911396558*^9}, {3.6201149523365803`*^9, 3.62011500488629*^9}, { 3.620189964186058*^9, 3.620189986023975*^9}, {3.620190318682701*^9, 3.6201903257366133`*^9}, {3.620190423660921*^9, 3.620190427915267*^9}, { 3.620197347691531*^9, 3.620197365990987*^9}, {3.6201974043855877`*^9, 3.620197406994176*^9}}, TextJustification->1.], Cell[TextData[{ "Consider the directed graph G depicted below (", StyleBox["you may need to click on Enable Dynamics first, to view the graph", FontSlant->"Italic"], "):" }], "Text", CellChangeTimes->{{3.6201088254037437`*^9, 3.62010883341857*^9}, { 3.620108999214017*^9, 3.6201090327446947`*^9}, {3.6201097490808372`*^9, 3.620109753687277*^9}, {3.620199452441346*^9, 3.6201995060514*^9}}], Cell[BoxData[ GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{1, 9, 3, 2, 7, 5, 4, 8, 6, 10}, {{{1, 2}, {1, 3}, {4, 5}, {4, 6}, {3, 5}, {3, 7}, {7, 1}, {7, 8}, { 7, 4}, {7, 3}, {6, 2}, {9, 5}, {5, 8}, {5, 4}, {9, 8}, {5, 10}, {8, 9}, {8, 5}, {2, 4}, {2, 10}, {10, 4}}, Null}, { GraphStyle -> "SmallNetwork"}]], Typeset`boxes, Typeset`boxes$s2d = GraphicsGroupBox[{{ Directive[ Hue[0.625, 0.5, 0.7], Thickness[Large], Opacity[1]], { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$1", Automatic, Center], DynamicLocation["VertexID$2", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$1", Automatic, Center], DynamicLocation["VertexID$3", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$2", Automatic, Center], DynamicLocation["VertexID$4", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$2", Automatic, Center], DynamicLocation["VertexID$10", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$3", Automatic, Center], DynamicLocation["VertexID$5", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[ BezierCurveBox[{ DynamicLocation["VertexID$3", Automatic, Center], { 1.2521758235132747`, 0.3224713563831371}, DynamicLocation["VertexID$7", Automatic, Center]}]]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[ BezierCurveBox[{ DynamicLocation["VertexID$4", Automatic, Center], { 1.7039073655713781`, 1.106986659948274}, DynamicLocation["VertexID$5", Automatic, Center]}]]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$4", Automatic, Center], DynamicLocation["VertexID$6", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[ BezierCurveBox[{ DynamicLocation["VertexID$5", Automatic, Center], { 1.7242314952054933`, 1.4914715959983922`}, DynamicLocation["VertexID$4", Automatic, Center]}]]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[ BezierCurveBox[{ DynamicLocation["VertexID$5", Automatic, Center], { 0.7882824365493453, 1.0382961292334352`}, DynamicLocation["VertexID$8", Automatic, Center]}]]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$5", Automatic, Center], DynamicLocation["VertexID$10", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$6", Automatic, Center], DynamicLocation["VertexID$2", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$7", Automatic, Center], DynamicLocation["VertexID$1", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[ BezierCurveBox[{ DynamicLocation["VertexID$7", Automatic, Center], { 1.430855793355474, 0.2567704632783701}, DynamicLocation["VertexID$3", Automatic, Center]}]]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$7", Automatic, Center], DynamicLocation["VertexID$4", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$7", Automatic, Center], DynamicLocation["VertexID$8", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[ BezierCurveBox[{ DynamicLocation["VertexID$8", Automatic, Center], { 0.6816787070144086, 1.297819607054366}, DynamicLocation["VertexID$5", Automatic, Center]}]]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[ BezierCurveBox[{ DynamicLocation["VertexID$8", Automatic, Center], { 0.04912696992132462, 1.3181829268598682`}, DynamicLocation["VertexID$9", Automatic, Center]}]]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$9", Automatic, Center], DynamicLocation["VertexID$5", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[ BezierCurveBox[{ DynamicLocation["VertexID$9", Automatic, Center], { 0.2912989031832586, 1.4301426967270374`}, DynamicLocation["VertexID$8", Automatic, Center]}]]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$10", Automatic, Center], DynamicLocation["VertexID$4", Automatic, Center]}]}}, { Directive[ Hue[0.125, 0.7, 0.9], EdgeForm[]], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{ 2.1777381533230855`, -0.09331463002505179}, { 2.2710527833481375`, -0.09331463002505179}, { 2.317710098360663, -0.09331463002505179}, { 2.317710098360663, -0.046657315012525895`}, {2.317710098360663, 0.046657315012525895`}, {2.317710098360663, 0.09331463002505179}, { 2.2710527833481375`, 0.09331463002505179}, {2.1777381533230855`, 0.09331463002505179}, {2.13108083831056, 0.09331463002505179}, { 2.13108083831056, 0.046657315012525895`}, { 2.13108083831056, -0.046657315012525895`}, { 2.13108083831056, -0.09331463002505179}, { 2.1777381533230855`, -0.09331463002505179}}}], "DynamicName", BoxID -> "VertexID$1"], InsetBox[ FormBox["1", TraditionalForm], DynamicLocation["VertexID$1", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$1"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{2.8654719148876495`, 0.8713615956483732}, {2.9587865449127015`, 0.8713615956483732}, { 3.005443859925227, 0.8713615956483732}, {3.005443859925227, 0.9180189106608991}, {3.005443859925227, 1.011333540685951}, { 3.005443859925227, 1.0579908556984767`}, {2.9587865449127015`, 1.0579908556984767`}, {2.8654719148876495`, 1.0579908556984767`}, { 2.818814599875124, 1.0579908556984767`}, {2.818814599875124, 1.011333540685951}, {2.818814599875124, 0.9180189106608991}, { 2.818814599875124, 0.8713615956483732}, {2.8654719148876495`, 0.8713615956483732}}}], "DynamicName", BoxID -> "VertexID$2"], InsetBox[ FormBox["9", TraditionalForm], DynamicLocation["VertexID$2", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$2"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{ 1.1949731331477447`, -0.07534167379319866}, { 1.2882877631727963`, -0.07534167379319866}, { 1.3349450781853223`, -0.07534167379319866}, { 1.3349450781853223`, -0.028684358780672763`}, {1.3349450781853223`, 0.06463027124437903}, {1.3349450781853223`, 0.11128758625690492`}, {1.2882877631727963`, 0.11128758625690492`}, {1.1949731331477447`, 0.11128758625690492`}, {1.1483158181352187`, 0.11128758625690492`}, {1.1483158181352187`, 0.06463027124437903}, { 1.1483158181352187`, -0.028684358780672763`}, { 1.1483158181352187`, -0.07534167379319866}, { 1.1949731331477447`, -0.07534167379319866}}}], "DynamicName", BoxID -> "VertexID$3"], InsetBox[ FormBox["3", TraditionalForm], DynamicLocation["VertexID$3", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$3"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{2.2519462753051824`, 1.1750156331862343`}, {2.3452609053302345`, 1.1750156331862343`}, { 2.39191822034276, 1.1750156331862343`}, {2.39191822034276, 1.2216729481987603`}, {2.39191822034276, 1.3149875782238118`}, { 2.39191822034276, 1.3616448932363379`}, {2.3452609053302345`, 1.3616448932363379`}, {2.2519462753051824`, 1.3616448932363379`}, { 2.205288960292657, 1.3616448932363379`}, {2.205288960292657, 1.3149875782238118`}, {2.205288960292657, 1.2216729481987603`}, { 2.205288960292657, 1.1750156331862343`}, {2.2519462753051824`, 1.1750156331862343`}}}], "DynamicName", BoxID -> "VertexID$4"], InsetBox[ FormBox["2", TraditionalForm], DynamicLocation["VertexID$4", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$4"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{1.082877955446641, 1.236813362709653}, {1.1761925854716926`, 1.236813362709653}, { 1.2228499004842186`, 1.236813362709653}, {1.2228499004842186`, 1.283470677722179}, {1.2228499004842186`, 1.3767853077472305`}, { 1.2228499004842186`, 1.4234426227597565`}, {1.1761925854716926`, 1.4234426227597565`}, {1.082877955446641, 1.4234426227597565`}, { 1.036220640434115, 1.4234426227597565`}, {1.036220640434115, 1.3767853077472305`}, {1.036220640434115, 1.283470677722179}, { 1.036220640434115, 1.236813362709653}, {1.082877955446641, 1.236813362709653}}}], "DynamicName", BoxID -> "VertexID$5"], InsetBox[ FormBox["7", TraditionalForm], DynamicLocation["VertexID$5", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$5"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{3.4555756873492647`, 1.40941210116583}, {3.5488903173743167`, 1.40941210116583}, { 3.5955476323868423`, 1.40941210116583}, {3.5955476323868423`, 1.456069416178356}, {3.5955476323868423`, 1.5493840462034076`}, { 3.5955476323868423`, 1.5960413612159337`}, {3.5488903173743167`, 1.5960413612159337`}, {3.4555756873492647`, 1.5960413612159337`}, { 3.408918372336739, 1.5960413612159337`}, {3.408918372336739, 1.5493840462034076`}, {3.408918372336739, 1.456069416178356}, { 3.408918372336739, 1.40941210116583}, {3.4555756873492647`, 1.40941210116583}}}], "DynamicName", BoxID -> "VertexID$6"], InsetBox[ FormBox["5", TraditionalForm], DynamicLocation["VertexID$6", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$6"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{1.3947438536959587`, 0.46795423340437736`}, {1.4880584837210102`, 0.46795423340437736`}, {1.5347157987335363`, 0.46795423340437736`}, {1.5347157987335363`, 0.5146115484169033}, { 1.5347157987335363`, 0.6079261784419551}, {1.5347157987335363`, 0.654583493454481}, {1.4880584837210102`, 0.654583493454481}, { 1.3947438536959587`, 0.654583493454481}, {1.3480865386834326`, 0.654583493454481}, {1.3480865386834326`, 0.6079261784419551}, { 1.3480865386834326`, 0.5146115484169033}, {1.3480865386834326`, 0.46795423340437736`}, {1.3947438536959587`, 0.46795423340437736`}}}], "DynamicName", BoxID -> "VertexID$7"], InsetBox[ FormBox["4", TraditionalForm], DynamicLocation["VertexID$7", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$7"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{0.29376855809205626`, 0.9126731135285098}, {0.38708318811710807`, 0.9126731135285098}, { 0.43374050312963397`, 0.9126731135285098}, {0.43374050312963397`, 0.9593304285410357}, {0.43374050312963397`, 1.0526450585660874`}, { 0.43374050312963397`, 1.0993023735786134`}, {0.38708318811710807`, 1.0993023735786134`}, {0.29376855809205626`, 1.0993023735786134`}, {0.24711124307953036`, 1.0993023735786134`}, {0.24711124307953036`, 1.0526450585660874`}, {0.24711124307953036`, 0.9593304285410357}, { 0.24711124307953036`, 0.9126731135285098}, {0.29376855809205626`, 0.9126731135285098}}}], "DynamicName", BoxID -> "VertexID$8"], InsetBox[ FormBox["8", TraditionalForm], DynamicLocation["VertexID$8", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$8"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{-0.046657315012525895`, 1.649023250007331}, {0.046657315012525895`, 1.649023250007331}, { 0.09331463002505179, 1.649023250007331}, {0.09331463002505179, 1.695680565019857}, {0.09331463002505179, 1.7889951950449086`}, { 0.09331463002505179, 1.8356525100574346`}, {0.046657315012525895`, 1.8356525100574346`}, {-0.046657315012525895`, 1.8356525100574346`}, {-0.09331463002505179, 1.8356525100574346`}, {-0.09331463002505179, 1.7889951950449086`}, {-0.09331463002505179, 1.695680565019857}, {-0.09331463002505179, 1.649023250007331}, {-0.046657315012525895`, 1.649023250007331}}}], "DynamicName", BoxID -> "VertexID$9"], InsetBox[ FormBox["6", TraditionalForm], DynamicLocation["VertexID$9", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$9"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{2.1203057332059627`, 1.767469793143102}, {2.2136203632310147`, 1.767469793143102}, { 2.2602776782435403`, 1.767469793143102}, {2.2602776782435403`, 1.814127108155628}, {2.2602776782435403`, 1.9074417381806796`}, { 2.2602776782435403`, 1.9540990531932056`}, {2.2136203632310147`, 1.9540990531932056`}, {2.1203057332059627`, 1.9540990531932056`}, { 2.073648418193437, 1.9540990531932056`}, {2.073648418193437, 1.9074417381806796`}, {2.073648418193437, 1.814127108155628}, { 2.073648418193437, 1.767469793143102}, {2.1203057332059627`, 1.767469793143102}}}], "DynamicName", BoxID -> "VertexID$10"], InsetBox[ FormBox["10", TraditionalForm], DynamicLocation["VertexID$10", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$10"]}}], $CellContext`flag}, TagBox[ DynamicBox[GraphComputation`NetworkGraphicsBox[ 3, Typeset`graph, Typeset`boxes, $CellContext`flag], { CachedValue :> Typeset`boxes, SingleEvaluation -> True, SynchronousUpdating -> False, TrackedSymbols :> {$CellContext`flag}}, ImageSizeCache->{{3.760693309010094, 355.2393066909899}, {-101.2393066909899, 97.2393066909899}}], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False, UnsavedVariables:>{$CellContext`flag}]], DefaultBaseStyle->{ "NetworkGraphics", FrontEnd`GraphicsHighlightColor -> Hue[0.8, 1., 0.6]}, FrameTicks->None, GridLinesStyle->Directive[ GrayLevel[0.5, 0.4]]]], "Input", CellChangeTimes->{3.62010900850277*^9, 3.6201839225798807`*^9}], Cell[CellGroupData[{ Cell[TextData[{ "Use the function ", StyleBox["Graph[...]", FontWeight->"Bold"], " to generate the graph G. The option GraphStyle\[Rule]\ \[CloseCurlyDoubleQuote]SmallNetwork\[CloseCurlyDoubleQuote] will give the \ same display style as above, but you are free to explore additional \ attributes as well." }], "ItemNumbered", CellChangeTimes->{{3.620108992510041*^9, 3.620108995109981*^9}, { 3.6201090352005243`*^9, 3.620109100429007*^9}, {3.620109775191825*^9, 3.6201099041043243`*^9}, {3.620110041375786*^9, 3.6201100413774767`*^9}, { 3.620111766901614*^9, 3.620111880483817*^9}, {3.620112279640234*^9, 3.620112279642049*^9}, {3.620113645184175*^9, 3.620113658784459*^9}, { 3.6201136913336887`*^9, 3.620113702341569*^9}, {3.620185538080884*^9, 3.6201855392718153`*^9}, {3.620197484060656*^9, 3.620197484916759*^9}}, TextJustification->1., FontSize->14], Cell[TextData[{ "Find the strongly connected components of G. Use ", StyleBox["HighlightGraph[...]", FontWeight->"Bold"], " to color the vertices of the graph according to the component they belong \ to." }], "ItemNumbered", CellChangeTimes->{{3.620108992510041*^9, 3.620108995109981*^9}, { 3.6201090352005243`*^9, 3.620109100429007*^9}, {3.620109775191825*^9, 3.6201099041043243`*^9}, {3.620110041375786*^9, 3.6201100413774767`*^9}, { 3.620111766901614*^9, 3.620111880483817*^9}, 3.620112279640234*^9, { 3.620112732038423*^9, 3.6201127481265593`*^9}, {3.620114073313735*^9, 3.6201141570942*^9}, {3.620175153016417*^9, 3.620175158671064*^9}, { 3.6201751904099073`*^9, 3.620175191721685*^9}, 3.620193975398938*^9}, TextJustification->1., FontSize->14], Cell[TextData[{ "Use the function ", StyleBox["FindGraphCommunities[...]", FontWeight->"Bold"], " to find a list of communities in the graph G. This function returns a list \ of communities, where each community is a list of vertices. The communities \ are ordered by their length, with the largest community first. Use the \ command ", StyleBox["HighlightGraph[...]", FontWeight->"Bold"], " to color the vertices of the graph according to the community they belong \ to." }], "ItemNumbered", CellChangeTimes->{{3.620108992510041*^9, 3.620108995109981*^9}, { 3.6201090352005243`*^9, 3.6201091532411337`*^9}, 3.620109191595594*^9, { 3.620109240695512*^9, 3.620109408841432*^9}, {3.620109460443139*^9, 3.620109461337912*^9}, {3.620111384887384*^9, 3.620111407527463*^9}, { 3.62011153093253*^9, 3.6201115391007*^9}, {3.620111577996471*^9, 3.6201115780005617`*^9}, 3.620173766498886*^9, {3.620174300224594*^9, 3.6201743006248426`*^9}, {3.620184547415868*^9, 3.620184558415969*^9}, { 3.620185578569697*^9, 3.62018559077591*^9}, {3.6201930570522738`*^9, 3.6201930733088818`*^9}, {3.620197503148827*^9, 3.62019750365256*^9}}, TextJustification->1., FontSize->14], Cell[TextData[{ StyleBox["ShortestPath[G, v1, v2]", FontWeight->"Bold"], " returns a list of vertices representing the shortest path between nodes v1 \ and v2. Use this function to find the shortest path between node 6 and node 9 \ and then use ", StyleBox["HighlightGraph[...]", FontWeight->"Bold"], " to highlight the shortest path between these nodes. First highlight only \ the vertices, then highlight the edges of the shortest path. Use ", StyleBox["GraphicsRow[...]", FontWeight->"Bold"], " to print the two highlighted graphs on the same row. " }], "ItemNumbered", CellChangeTimes->{{3.620108992510041*^9, 3.620108995109981*^9}, { 3.6201090352005243`*^9, 3.6201091532411337`*^9}, 3.620109191595594*^9, { 3.620109240695512*^9, 3.620109408841432*^9}, {3.620109460443139*^9, 3.620109461337912*^9}, {3.620111384887384*^9, 3.620111407527463*^9}, { 3.62011153093253*^9, 3.6201115391007*^9}, {3.620111577996471*^9, 3.620111628240754*^9}, {3.620111935432728*^9, 3.620112142121011*^9}, { 3.6201141514141073`*^9, 3.620114151417651*^9}, {3.620174294744739*^9, 3.620174295144485*^9}, {3.6201748785084457`*^9, 3.620174918459569*^9}, { 3.620174951663845*^9, 3.6201750179784*^9}, {3.620175268358534*^9, 3.620175269717351*^9}, {3.6201975550122128`*^9, 3.620197603106166*^9}}, TextJustification->1., FontSize->14], Cell[TextData[{ StyleBox["GraphDiameter[G]", FontWeight->"Bold"], " gives the greatest distance between any pair of vertices in the graph G. \ What is the diameter of G? Explain." }], "ItemNumbered", CellChangeTimes->{{3.620108992510041*^9, 3.620108995109981*^9}, { 3.6201090352005243`*^9, 3.6201091532411337`*^9}, 3.620109191595594*^9, { 3.620109240695512*^9, 3.620109408841432*^9}, {3.620109460443139*^9, 3.620109461337912*^9}, {3.620111384887384*^9, 3.620111407527463*^9}, { 3.62011153093253*^9, 3.6201115391007*^9}, {3.620111577996471*^9, 3.620111628240754*^9}, {3.620111935432728*^9, 3.620112142121011*^9}, { 3.6201141514141073`*^9, 3.620114152513225*^9}, {3.620114570739678*^9, 3.620114570745627*^9}}, TextJustification->1., FontSize->14] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[TextData[StyleBox["Problem 2.2", "Subsection"]], "Section", CellChangeTimes->{{3.6188834372387037`*^9, 3.618883440270814*^9}, { 3.618884618760844*^9, 3.618884619110783*^9}, {3.6189486900451593`*^9, 3.618948692316845*^9}, 3.6189488450714417`*^9, {3.619056958023197*^9, 3.6190569585670424`*^9}, {3.620185341416134*^9, 3.6201853431924257`*^9}, { 3.620187808014838*^9, 3.620187808189505*^9}}], Cell[TextData[{ "Consider the graph G from problem 2.1. The command", StyleBox[" FindCycle[G,{n}]", FontWeight->"Bold"], " returns a cycle of length n in graph G. Use this function to find a cycle \ of length 3 in G. Suppose next that we want to find all cycles of length 3 in \ G. There are several ways to do that, but we will choose to work with the \ adjacency matrix of G for this task. Use your preferred loop structures in ", StyleBox["Mathematica", FontSlant->"Italic"], " (Do, While, For) to find how many cycles of length exactly 3 are in the \ graph G and to print all of these cycles. A cycle should be displayed as a \ list of edges of the form {a\[Rule]b, b\[Rule]c, c\[Rule]a}. Do not print the \ same cycle three times! For example, {a\[Rule]b, b\[Rule]c, c\[Rule]a}, {b\ \[Rule]c, c\[Rule]a, a\[Rule]b}, {c\[Rule]a, a\[Rule]b, b\[Rule]c} are \ different ways of writing the same cycle, which should be counted only once." }], "Text", CellChangeTimes->{{3.6201877335744677`*^9, 3.6201877585037947`*^9}, { 3.620187845877626*^9, 3.6201880113610363`*^9}, {3.620188122035163*^9, 3.6201881725447407`*^9}, {3.62018826777606*^9, 3.620188330767315*^9}, { 3.62018855130685*^9, 3.6201886002735977`*^9}, {3.620188760750334*^9, 3.620188811430654*^9}, {3.6201888711261387`*^9, 3.620189100987502*^9}, { 3.620189188215624*^9, 3.620189414839512*^9}, {3.620189452773123*^9, 3.6201894653172827`*^9}, {3.620190500163907*^9, 3.620190500738941*^9}, { 3.6201905465451612`*^9, 3.620190606529562*^9}, {3.620190640540985*^9, 3.620190695213593*^9}, {3.620190738393701*^9, 3.6201907407060137`*^9}, { 3.620190785395204*^9, 3.6201908729707193`*^9}, {3.620197642196295*^9, 3.620197699905993*^9}, 3.696062259792194*^9}, TextJustification->1.] }, Open ]], Cell[CellGroupData[{ Cell[TextData[StyleBox["Problem 2.3", "Subsection"]], "Section", CellChangeTimes->{{3.6188834470493517`*^9, 3.618883458254191*^9}, { 3.6188841737965927`*^9, 3.618884177712782*^9}, {3.6188846295181627`*^9, 3.6188846297983932`*^9}, {3.619056965231044*^9, 3.619056965742797*^9}, { 3.620184812387269*^9, 3.620184812898695*^9}, {3.620185327776074*^9, 3.620185327888328*^9}, {3.62027150629076*^9, 3.620271506680812*^9}}], Cell[TextData[{ "Write a function", StyleBox[" transition[...]", FontWeight->"Bold"], " that takes as input a directed graph H with any number of nodes, \ represented as a list of directed edges, and returns the transition matrix of \ H. Recall that the (i,j) entry of the transition matrix reflects the \ probability of transition from node i to node j. A preliminary version of the \ algorithm for computing the transition matrix of a graph is done is the \ lecture notes. There are some special cases which were not covered in the \ lecture (like the case of nodes with no outgoing edges). Test your function \ on the graph from problem 1, as well as on a randomly generated directed \ graph with 10 nodes and 20 edges." }], "Text", CellChangeTimes->{{3.6190083437795057`*^9, 3.619008619778887*^9}, { 3.6190086997717037`*^9, 3.619008742318366*^9}, {3.61900877337542*^9, 3.619008846690468*^9}, {3.619063502179244*^9, 3.619063504155314*^9}, { 3.619064140835752*^9, 3.619064155080373*^9}, {3.6194770073674107`*^9, 3.6194770491064157`*^9}, {3.620075409161674*^9, 3.620075433432282*^9}, { 3.620075524069899*^9, 3.620075731127187*^9}, {3.620075775367186*^9, 3.6200758388256407`*^9}, {3.620075869795953*^9, 3.620076143652358*^9}, { 3.620076194766493*^9, 3.620076199750688*^9}, {3.620184195501205*^9, 3.6201842312101793`*^9}, {3.620184266043998*^9, 3.620184324595572*^9}, { 3.620184405840395*^9, 3.620184408351913*^9}, 3.620184440649316*^9, { 3.620184824715065*^9, 3.620184871272209*^9}, {3.620197754934945*^9, 3.620197830056409*^9}, {3.651315940412025*^9, 3.651315967426976*^9}, { 3.6513160066427402`*^9, 3.651316012073771*^9}}, TextJustification->1.] }, Open ]], Cell[CellGroupData[{ Cell[TextData[StyleBox["Problem 2.4", "Subsection"]], "Section", CellChangeTimes->{{3.6188834372387037`*^9, 3.618883440270814*^9}, { 3.618884618760844*^9, 3.618884619110783*^9}, {3.6189486900451593`*^9, 3.618948692316845*^9}, 3.6189488450714417`*^9, {3.619056958023197*^9, 3.6190569585670424`*^9}, {3.620185341416134*^9, 3.6201853431924257`*^9}, { 3.620271517080847*^9, 3.6202715175368156`*^9}, {3.651315897282497*^9, 3.6513158978093224`*^9}}], Cell["\<\ Let H be any undirected graph. If H is a connected, acyclic graph (acyclic \ means that it contains no cycles) then we say that H is a tree. Trees are \ very useful for storing, sorting and querying information that has a natural \ hierarchical structure. For instance, the file system (folders, subfolders, \ documents, etc.) in a computer uses a tree architecture. \ \>", "Text", CellChangeTimes->{{3.620196133716662*^9, 3.620196144146524*^9}, { 3.620196217571464*^9, 3.620196308719524*^9}, {3.620196484122243*^9, 3.6201965541007338`*^9}, {3.620198291212543*^9, 3.62019834065829*^9}, { 3.620198515579067*^9, 3.620198596328479*^9}, {3.620198642624853*^9, 3.620198648152766*^9}, {3.620198758304512*^9, 3.620198794975412*^9}, { 3.6201988267049007`*^9, 3.620198906570344*^9}, 3.696062247086388*^9}, TextJustification->1.], Cell[TextData[{ "To build some intuition about trees, use ", StyleBox["TreePlot[H, VertexLabeling\[Rule]True, DirectedEdges\[Rule]False]", FontWeight->"Bold"], " to plot any graph which has the properties listed above. GraphPlot[...] \ can also be used for plotting trees, however the layout is slightly \ different. Then give short mathematical arguments for the following claims:" }], "Text", CellChangeTimes->{{3.6201967476574507`*^9, 3.620196837489334*^9}, { 3.6201969383993673`*^9, 3.620197037326992*^9}, {3.6201970852004538`*^9, 3.620197251527467*^9}, {3.62019814320916*^9, 3.620198143926906*^9}, { 3.620198973380221*^9, 3.620199086498517*^9}, {3.6513160938107567`*^9, 3.651316094065241*^9}, {3.69606159913098*^9, 3.6960616121206417`*^9}, { 3.6960617069011583`*^9, 3.696061730876706*^9}}, TextJustification->1.], Cell[CellGroupData[{ Cell["\<\ Show that if H is a tree then the Adjacency Matrix of H has one eigenvalue \ equal to 0.\ \>", "ItemNumbered", CellChangeTimes->{{3.696061618538763*^9, 3.69606166295394*^9}, 3.696061739148946*^9}], Cell["\<\ Show that a graph H is a tree if and only if any one of the following \ properties is satisfied:\ \>", "ItemNumbered", CellChangeTimes->{{3.620198896225913*^9, 3.620198919138541*^9}}], Cell[CellGroupData[{ Cell["\<\ Every pair of distinct vertices of H is connected by a unique path.\ \>", "SubitemNumbered", CellChangeTimes->{{3.620196563398802*^9, 3.620196583682613*^9}, { 3.6201967373607187`*^9, 3.620196738656983*^9}}, FontSize->14], Cell["\<\ The graph H is connected, but deleting any edge disconnects H.\ \>", "SubitemNumbered", CellChangeTimes->{{3.620196563398802*^9, 3.620196617017712*^9}}, FontSize->14], Cell["\<\ The graph H is acyclic, but adding any edge to H forms a cycle.\ \>", "SubitemNumbered", CellChangeTimes->{{3.620196563398802*^9, 3.6201966421446943`*^9}}, FontSize->14], Cell["\<\ The graph H is connected and has n-1 edges, where n is the number of vertices \ of H.\ \>", "SubitemNumbered", CellChangeTimes->{{3.620196563398802*^9, 3.6201966834587317`*^9}, { 3.620198112110965*^9, 3.620198112836485*^9}}, FontSize->14] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[TextData[StyleBox["Problem 2.5", "Subsection"]], "Section", CellChangeTimes->{{3.6188834470493517`*^9, 3.618883458254191*^9}, { 3.6188841737965927`*^9, 3.618884177712782*^9}, {3.6188846295181627`*^9, 3.6188846297983932`*^9}, {3.619056965231044*^9, 3.619056965742797*^9}, { 3.620185345872222*^9, 3.620185347792323*^9}, {3.6202715249687*^9, 3.620271525544833*^9}, {3.651315901009066*^9, 3.651315901481039*^9}}], Cell[TextData[{ "In this problem, we want to use the command ", StyleBox["Manipulate[...]", FontWeight->"Bold"], " to create nice interactive models. We can wrap Manipulate[...] around any \ Wolfram command. The output you get from evaluating a Manipulate command is \ an interactive object containing one or more controls (sliders, etc.) that \ you can use to vary the value of one or more parameters." }], "Text", CellChangeTimes->{{3.620190979925646*^9, 3.6201910528403*^9}, { 3.620192158203018*^9, 3.6201922032990847`*^9}, {3.620192828033259*^9, 3.620192963196506*^9}, {3.620193001968439*^9, 3.620193037372748*^9}, { 3.620193128480073*^9, 3.620193206161715*^9}, {3.620193274821574*^9, 3.620193277397674*^9}, 3.6201933864090633`*^9, {3.620193467785057*^9, 3.6201934704644747`*^9}}, TextJustification->1.], Cell[CellGroupData[{ Cell["\<\ Let\[CloseCurlyQuote]s go back to part 4 of problem 1 and turn it into an \ interactive model. We do not want to change the graph G from problem 1, but \ we would like to build an interactive model such that for any given choice of \ nodes v and u in G, we display the graph G with the shortest path between u \ and v highlighted. Use the command Manipulate[...] to create a nice \ interactive model with controls for the parameters u and v.\ \>", "ItemNumbered", CellChangeTimes->{{3.6201934816428423`*^9, 3.6201937280435753`*^9}, { 3.620193771765559*^9, 3.620193858157958*^9}, 3.620193942124673*^9, { 3.620194950751381*^9, 3.620194963118421*^9}, {3.62019501891059*^9, 3.6201951923515797`*^9}, {3.6201952231491947`*^9, 3.620195224581388*^9}, { 3.6201957804382963`*^9, 3.6201958494975033`*^9}, {3.620195898958362*^9, 3.620195972964904*^9}, 3.620199211289741*^9, {3.620199265345017*^9, 3.620199266257238*^9}, {3.6960618550260267`*^9, 3.696061920588389*^9}, { 3.696062043368876*^9, 3.696062058151917*^9}}, TextJustification->1., FontSize->14], Cell[TextData[{ StyleBox["RandomGraph[{m,n},k]", FontWeight->"Bold"], " generates k random undirected graphs with m vertices and n edges; if we \ want to generate directed graphs, we need to set the attribute DirectedEdges \ to True, as shown in the lecture notes. Your first task is to create a nice \ interactive model that can generate k (directed or undirected!) graphs with \ ", Cell[BoxData[ FormBox["m", TraditionalForm]]], " vertices and ", Cell[BoxData[ FormBox[ FractionBox[ RowBox[{"m", "(", RowBox[{"m", "-", "1"}], ")"}], "2"], TraditionalForm]], FontSize->16], " edges. The possible values for k should be 1 and 4. The parameter m can be \ any positive integer between 4 and 10, with default value 6. You should have \ one extra parameter, called Directed, that can take the values True or False. " }], "ItemNumbered", CellChangeTimes->{{3.6201934816428423`*^9, 3.6201937280435753`*^9}, { 3.620193771765559*^9, 3.620193858157958*^9}, {3.620193942124673*^9, 3.6201939421306868`*^9}, {3.620194576842813*^9, 3.6201946279627047`*^9}, { 3.62019471306758*^9, 3.620194737413842*^9}, {3.620194874472842*^9, 3.620194890728157*^9}, {3.620195247926223*^9, 3.620195324002173*^9}, { 3.620199296627438*^9, 3.620199299579721*^9}}, TextJustification->1., FontSize->14], Cell["\<\ Build an interactive model with two controls, n and u, that generates a \ random graph called K with n vertices and 2n edges and highlights vertex u of \ graph K. When the user selects a different vertex u of K, you display graph K \ with vertex u shown with a different color and with a different size.\ \>", "ItemNumbered", CellChangeTimes->{{3.6201934816428423`*^9, 3.6201937280435753`*^9}, { 3.620193771765559*^9, 3.620193858157958*^9}, 3.620193942124673*^9, { 3.620194950751381*^9, 3.620194963118421*^9}, {3.62019501891059*^9, 3.6201951923515797`*^9}, {3.6201952231491947`*^9, 3.620195224581388*^9}, { 3.6201957804382963`*^9, 3.6201958494975033`*^9}, {3.620195898958362*^9, 3.620195972964904*^9}, 3.620199211289741*^9, {3.620199265345017*^9, 3.620199266257238*^9}, {3.6960618550260267`*^9, 3.6960619016586037`*^9}, { 3.696061988568553*^9, 3.69606201412744*^9}, {3.696062117697654*^9, 3.6960622005727587`*^9}}, TextJustification->1., FontSize->14] }, Open ]] }, Open ]] }, WindowSize->{827, 532}, WindowMargins->{{Automatic, 70}, {66, Automatic}}, FrontEndVersion->"11.0 for Mac OS X x86 (32-bit, 64-bit Kernel) (September \ 21, 2016)", StyleDefinitions->"Default.nb" ] (* End of Notebook Content *) (* Internal cache information *) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[558, 20, 359, 10, 64, "Section"], Cell[CellGroupData[{ Cell[942, 34, 177, 2, 41, "Section"], Cell[1122, 38, 4143, 97, 300, "Text"], Cell[5268, 137, 403, 9, 30, "Text"], Cell[5674, 148, 23931, 471, 221, "Input"], Cell[CellGroupData[{ Cell[29630, 623, 877, 17, 45, "ItemNumbered"], Cell[30510, 642, 778, 15, 45, "ItemNumbered"], Cell[31291, 659, 1195, 23, 79, "ItemNumbered"], Cell[32489, 684, 1350, 25, 79, "ItemNumbered"], Cell[33842, 711, 775, 15, 45, "ItemNumbered"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[34666, 732, 408, 5, 55, "Section"], Cell[35077, 739, 1773, 28, 144, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[36887, 772, 425, 5, 55, "Section"], Cell[37315, 779, 1695, 27, 125, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[39047, 811, 462, 6, 55, "Section"], Cell[39512, 819, 848, 13, 87, "Text"], Cell[40363, 834, 841, 15, 68, "Text"], Cell[CellGroupData[{ Cell[41229, 853, 211, 5, 30, "ItemNumbered"], Cell[41443, 860, 194, 4, 30, "ItemNumbered"], Cell[CellGroupData[{ Cell[41662, 868, 234, 5, 24, "SubitemNumbered"], Cell[41899, 875, 178, 4, 24, "SubitemNumbered"], Cell[42080, 881, 181, 4, 24, "SubitemNumbered"], Cell[42264, 887, 252, 6, 24, "SubitemNumbered"] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[42577, 900, 424, 5, 55, "Section"], Cell[43004, 907, 832, 15, 87, "Text"], Cell[CellGroupData[{ Cell[43861, 926, 1077, 17, 79, "ItemNumbered"], Cell[44941, 945, 1308, 28, 126, "ItemNumbered"], Cell[46252, 975, 992, 16, 62, "ItemNumbered"] }, Open ]] }, Open ]] } ] *)