{VERSION 3 0 "IBM INTEL NT" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 256 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "TXT CMD" -1 260 "MS Sans Serif" 0 0 128 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "Bookmark" 20 261 "" 0 0 0 128 0 1 1 0 0 0 0 1 0 0 0 }{CSTYLE "word" -1 262 "" 0 0 128 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "bookmark" -1 263 "" 0 0 0 128 0 1 0 0 0 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 0 0 128 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Plot" 0 13 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Title" 0 18 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 }{PSTYLE "n ewpage" -1 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 1 0 -1 0 }{PSTYLE "vfill" -1 257 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "Definition" -1 258 1 {CSTYLE "" -1 -1 "" 0 0 0 64 128 1 0 0 0 0 0 0 0 0 0 }0 0 0 -1 4 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Theorem" -1 259 1 {CSTYLE "" -1 -1 "" 0 0 219 36 36 1 0 0 0 0 0 0 0 0 0 }0 0 0 -1 4 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Problem" -1 260 1 {CSTYLE "" -1 -1 "" 0 0 0 0 255 1 0 0 0 0 0 0 0 0 0 }0 0 0 -1 4 4 3 4 0 0 0 0 -1 0 } {PSTYLE "dblnorm" -1 261 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 2 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "code" 2 262 1 {CSTYLE "" -1 -1 "Comic Sans MS" 0 0 128 0 128 1 0 1 0 0 0 0 3 0 0 }0 0 0 -1 -1 -1 3 12 0 0 0 0 -1 0 }{PSTYLE "asis" 0 263 1 {CSTYLE "" -1 -1 "Arial Narrow" 1 12 128 64 0 1 0 0 0 0 0 1 3 0 0 }0 0 0 -1 -1 -1 3 6 0 0 0 0 0 0 }{PSTYLE "subproblem" 0 264 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "dia gram" -1 265 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "dblnorm.mws" -1 266 1 {CSTYLE " " -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 2 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Item" 0 267 1 {CSTYLE "" -1 -1 "Lucida Sans" 1 12 0 0 0 1 0 0 0 0 0 0 0 0 0 }0 0 0 -1 6 -1 3 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 16 "Graph operators." }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 2 "A " }{TEXT 256 14 "graph operator" }{TEXT -1 175 " is a function which assigns to each graph another grap h. As an example, we can look at the operator f which throws away th e loose ends of a graph. To be more precise, an " }{TEXT 257 8 "endp oint" }{TEXT -1 116 " of a graph G is a vertex of G which is an end of exactly one edge of G. Such an edge would naturally be called a " } {TEXT 258 12 "loose edge. " }{TEXT -1 222 " So f(G) is defined to be t he graph whose vertices are the vertices of G which are not endpoints \+ of G and whose edges are the edges of G which are not loose. We can c ompute values of f using the networks package in Maple." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "with(networks);" }}{PARA 12 "" 1 " " {XPPMATH 20 "6#7go%)acycpolyG%(addedgeG%*addvertexG%*adjacencyG%)all pairsG%)ancestorG%)arrivalsG%-bicomponentsG%)charpolyG%*chrompolyG%+co mplementG%)completeG%+componentsG%(connectG%-connectivityG%)contractG% *countcutsG%+counttreesG%%cubeG%&cycleG%*cyclebaseG%)daughterG%*degree seqG%'deleteG%+departuresG%)diameterG%&dinicG%+djspantreeG%-dodecahedr onG%%drawG%*duplicateG%&edgesG%%endsG%(eweightG%%flowG%)flowpolyG%(fun dcycG%)getlabelG%&girthG%&graphG%*graphicalG%&gsimpG%'gunionG%%headG%, icosahedronG%*incidenceG%)incidentG%)indegreeG%'induceG%)isplanarG%*ma xdegreeG%'mincutG%*mindegreeG%*neighborsG%$newG%+octahedronG%*outdegre eG%%pathG%)petersenG%'randomG%%rankG%)rankpolyG%.shortpathtreeG%%showG %'shrinkG%%spanG%)spanpolyG%)spantreeG%%tailG%,tetrahedronG%*tuttepoly G%(vdegreeG%)verticesG%%voidG%(vweightG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 431 "noloose := proc(G)\n local H,e,v,i,ed,n;\n new(H);\n ed := NULL; #initialize endpoints\n for v in vertices(G) do\n n : = 0:\n for e in edges(G) do\n if member(v,\{op(ends(e,G))\}) t hen n := n+1:\n if n = 2 then addvertex(v,H) ; break; fi fi;\n \+ od:\n if n < 2 then ed := ed,v fi;\n od;\n for i from 1 to nops (edges(G)) do \n if \{op(ends(e.i,G))\} intersect \{ed\} = \{\} \n \+ then addedge(ends(e.i,G),H) fi;\n od;\n H end: " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 31 "Test this out on a golf club L." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "new(L):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "addvertex(\{0,1,2,3,4\},L):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "addedge(\{\{0,1\},\{1,2\},\{2,0\},\{2,3\} ,\{3,4\}\},L);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6'%#e1G%#e2G%#e3G%#e4G %#e5G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "draw(L);" }}{PARA 13 "" 1 "" {GLPLOT2D 400 300 300 {PLOTDATA 2 "62-%'CURVESG6$7$7$$\"\" \"\"\"!F*7$$\"+Q*p,4$!#5$\"+l^c5&*F.-%'COLOURG6&%$RGBGF*$\"#5!\"\"F*-% %TEXTG6$7$$\"+l*p,4$F.$!+c^c5&*F.Q\"46\"-%'POINTSG6#F;-F96$7$$!+M*p,4) F.$!+PD&y(eF.Q\"3FA-F96$7$$!+]*p,4)F.$\"+9D&y(eF.Q\"2FA-FC6#FG-F96$F+Q \"1FA-FC6#FO-FC6#F+-F96$F'Q\"0FA-FC6#F'-F$6$7$F'FOF1-F$6$7$FOFGF1-F$6$ 7$F+FOF1-F$6$7$FGF;F1-%*AXESSTYLEG6#%%NONEG" 1 2 0 1 0 2 9 1 1 2 1.000000 45.000000 45.000000 0 }}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "draw(noloose(L));" }}{PARA 13 "" 1 "" {GLPLOT2D 400 300 300 {PLOTDATA 2 "6/-%'CURVESG6$7$7$$!\"\"\"\"!$!+:w1-T!#>7$$\"+A95`hF-F(-% 'COLOURG6&%$RGBGF*$\"#5F)F*-F$6$7$7$$\"\"\"F*F*7$$!+2Q.^?F-F;F1-%%TEXT G6$F.Q\"36\"-F$6$7$F=F'F1-%'POINTSG6#F=-FI6#F.-FA6$F'Q\"2FD-FI6#F'-FA6 $F=Q\"1FD-F$6$7$F:F'F1-FA6$F:Q\"0FD-FI6#F:-%*AXESSTYLEG6#%%NONEG" 1 2 0 1 0 2 9 1 1 2 1.000000 45.000000 45.000000 0 }}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 19 "This seems to work." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 260 "" 0 "" {TEXT -1 115 "Problem: what are the fixed graph s of the loose ends operator? That is, describe the graphs G such t hat f(G)=G." }}}}{MARK "4 0 0" 31 }{VIEWOPTS 1 1 0 1 1 1803 }