{VERSION 4 0 "IBM INTEL NT" "4.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 3 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 } {PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 8 2 0 0 0 0 0 0 -1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 0 0 0 1 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 0 }3 3 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 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {PARA 4 "" 0 "" {TEXT -1 31 "Module 7 : Discrete Mathematics" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 3 "" 0 "" {TEXT -1 16 "703 Gra ph Theory" }}{PARA 0 "" 0 "" {TEXT -1 15 "\251 Gregory Moore" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 256 "" 0 "" {TEXT -1 13 "P U R P O S E " }}{PARA 0 "" 0 "" {TEXT -1 183 "Explore the world of graphs, create \+ graphs in Maple and generate diagrams and adjacency matrices, examine \+ equivalency of graphs, and the concepts of connected and unconnected g raphs.\n" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 32 "To begin, enter these commands :" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 " restart; with( network s): with(linalg):\n" }}{PARA 7 "" 1 "" {TEXT -1 57 "Warning, the na mes charpoly and rank have been redefined\n" }}{PARA 7 "" 1 "" {TEXT -1 80 "Warning, the protected names norm and trace have been redefined and unprotected\n" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 72 "_______________________________________________________ _________________" }}{PARA 4 "" 0 "" {TEXT -1 18 "A. Creating Graphs" }}{PARA 0 "" 0 "" {TEXT -1 72 "_______________________________________ _________________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 412 "A graph is a diagram with vertex points, and edges connecting some or all of the vertices. \n\nLets consider t his example. An airline only flies to certain cities : New York, Toron to, Los Angeles, San Francisco, Chicago, Denver, and New Orleans. We c an create a set with these cities. Remember that names in Maple can no t contain blank characters, so its necessary to use an underscore betw een two word city names." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 89 "cities := \{ New_York, Toronto, Los _Angeles, San_Francisco, Chicago, Denver, New_Orleans\};" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%'citiesG<)%(TorontoG%(ChicagoG%'DenverG%.San_F ranciscoG%,New_OrleansG%,Los_AngelesG%)New_YorkG" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 84 "We\325ll inform Maple tha t we wish to create a new graph with these cities as vertices." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "new(G):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "addvertex( ci ties, G);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6)%(TorontoG%(ChicagoG%'Den verG%.San_FranciscoG%,New_OrleansG%,Los_AngelesG%)New_YorkG" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 213 "The airline does not have flights from every city t o every other city. There are flights from New York to Los Angeles, To ronto, and Chicago. We indicate this by informing Maple of connections between these cities." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "connect( \{New_York\}, \{Los_Angele s, Toronto, Chicago\}, G):" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 191 "In a similar w ay, we indicate that Los Angeles also has flights to San Francisco, De nver, and Chicago. We don\325t need to mention New York because that c onnection was already established above." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "connect( \{Los_Angele s\}, \{San_Francisco, Denver, Chicago\}, G):" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 98 "Also, there are flights from Chicago to Toronto and New Orleans , and from San Francisco to Denver." }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "connect( \{Chicago\}, \{Tor onto, New_Orleans \}, G):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "connect( \{San_Francisco\}, \{Denver\}, G):" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 63 "Now lets see what this routing looks like by drawing the graph. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "draw(G);" }}{PARA 13 "" 1 "" {GLPLOT2D 400 300 300 {PLOTDATA 2 "6:-%%TEXTG6$7$$\"+D!)*[B'!#5$!+>[J=yF)Q(Toronto6\"-F$6$7$$!+J$4_A#F)$ !+C\"z#\\(*F)Q.San_FranciscoF--%'POINTSG6#F&-F76#F0-F76#7$$!+z')o4!*F) $!+!RP)QVF)-F$6$F=Q)New_YorkF--F$6$7$F>$\"+#RP)QVF)Q,New_OrleansF--F$6 $7$$!+R$4_A#F)$\"+A\"z#\\(*F)Q,Los_AngelesF--F76#FG-F76#FM-F$6$7$$\"\" \"\"\"!$FfnFfnQ(ChicagoF--F76#7$$\"+=!)*[B'F)$\"+D[J=yF)-F$6$F[oQ'Denv erF--F76#FY-%'CURVESG6$7$F&F=-%'COLOURG6&%$RGBGFfn$\"#5!\"\"Ffn-Ffo6$7 $FYF=Fio-Ffo6$7$F0FMFio-Ffo6$7$F[oF0Fio-Ffo6$7$FYFGFio-Ffo6$7$F&FYFio- Ffo6$7$FYFMFio-Ffo6$7$F[oFMFio-Ffo6$7$FMF=Fio-%*AXESSTYLEG6#%%NONEG" 1 2 0 1 10 0 2 9 1 1 2 1.000000 45.000000 45.000000 0 0 "Curve 1" "Cur ve 2" "Curve 3" "Curve 4" "Curve 5" "Curve 6" "Curve 7" "Curve 8" "Cur ve 9" "Curve 10" "Curve 11" "Curve 12" "Curve 13" "Curve 14" "Curve 15 " "Curve 16" "Curve 17" "Curve 18" "Curve 19" "Curve 20" "Curve 21" "C urve 22" "Curve 23" }}}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 221 "As we can see, there are plenty of connections. Howeve r, not every city is connected to every other one by a direct flight. \+ For example, there is no direct flight from Denver to Chicago, New Yor k, Toronto, or New Orleans." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 72 "____________________ ____________________________________________________" }}{PARA 4 "" 0 " " {TEXT -1 21 "B. Adjacency Matrices" }}{PARA 0 "" 0 "" {TEXT -1 72 "_ ______________________________________________________________________ _" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 755 "It can b e difficult to work graphs as diagrams. A more convenient way to analy ze graphs mathematically is to represent them as matrices. A matrix re presentation for a graph is called an adjacency matrix\323. \n\nThe wa y it works is this. For each vertex, there is a row and column of the \+ matrix. For example if there are six vertices, then the matrix will be six by six. If there is a connection between vertex 2 and vertex 5, t hen there will be a 1 in row 2, column 5 and also in row 5, column 2. \+ The 1 appears in two places to indicate a path from 2 to 5 and from 5 \+ to 2. If there is no connection between vertex 3 and vertex 4, then th ere will be a zero in row 3 column 4 and row 4 column 3. Maple will cr eate these matrices for us. Lets see this in action." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "points := \{ A,B,C,D,E,F\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'pointsG<(%\"DG%\"CG%\"AG%\"EG%\"BG%\"FG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "new(G1):" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 23 "addvertex( points, G1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6(%\"DG%\"CG%\"AG%\"EG%\"BG%\"FG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "connect( \{A\},\{B,C\}, G1):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "connect( \{B\}, \{E\}, G1):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "connect( \{C\}, \{D,F\}, G1):" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "draw(G1);" }}{PARA 13 "" 1 " " {GLPLOT2D 400 300 300 {PLOTDATA 2 "64-%'POINTSG6#7$$\"\"\"\"\"!$F)F) -%%TEXTG6$F&Q\"A6\"-F$6#7$$\"+-+++]!#5$\"+PSDg')F5-F,6$F2Q\"BF/-F$6#7$ $!+(*******\\F5$\"+SSDg')F5-F,6$7$$!+2+++]F5$!+MSDg')F5Q\"EF/-F$6#7$$ \"+\"*******\\F5$!+VSDg')F5-F,6$FLQ\"FF/-F,6$F=Q\"CF/-F$6#7$$!\"\"F)$ \"+&QKz*e!#>-F,6$FYQ\"DF/-F$6#FD-%'CURVESG6$7$F&F2-%'COLOURG6&%$RGBGF) $\"#5FenF)-F_o6$7$F=F&Fbo-F_o6$7$FDF2Fbo-F_o6$7$F=FLFbo-F_o6$7$FYF=Fbo -%*AXESSTYLEG6#%%NONEG" 1 2 0 1 10 0 2 9 1 1 2 1.000000 45.000000 45.000000 0 0 "Curve 1" "Curve 2" "Curve 3" "Curve 4" "Curve 5" "Curve 6" "Curve 7" "Curve 8" "Curve 9" "Curve 10" "Curve 11" "Curve 12" "Cu rve 13" "Curve 14" "Curve 15" "Curve 16" "Curve 17" }}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "A1 := adjacency(G1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#A1G-%'matrixG6#7(7(\"\"!\"\"\"F+F*F*F*7(F+F*F*F*F+F* 7(F+F*F*F+F*F+7(F*F*F+F*F*F*7(F*F+F*F*F*F*F." }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 451 "This matrix represents a ll of the connections between the vertices. Vertex A is connected to v ertices B and C. We can see that in the matrix by looking down the fir st column and seeing 1\325s in the 2nd and 3rd rows. Vertex B is conne cted to A, and E. This is indicated by looking down the 2nd column and seeing 1\325s in the 1st and 5th locations. C is connected to A, D, a nd F, so the 3rd column has 1\325s in the 1st, 4th, and 6th positions. And so forth.\n\n" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 72 "_______________________________________________________________ _________" }}{PARA 4 "" 0 "" {TEXT -1 20 "C. Equivalent Graphs" }} {PARA 0 "" 0 "" {TEXT -1 72 "_________________________________________ _______________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 948 "\nSometimes two graphs appear to be diff erent graphs, however in reality they are essentially the same graph w ith the vertices re-arranged, with the connections in the correspondin g places. For example if you start with any graph diagram, and simply \+ move some of the vertices to a new location, keeping the connections a ttached, it would cause the graph to appear different, but actually it would be contain the same connection information as before the altera tion. It can be very hard to see that two graphs are equivalent just b y inspecting the diagram. Also, at times two graphs can appear to be e quivalent but actually be different. \n\nThere is a method to determin e if two graphs are equivalent using their adjacency matrices. Even tw o equivalent graphs can have different adjacency matrices. However, in terchanging vertices on the graph is equivalent to interchanging rows \+ and columns of the matrices. Lets consider an example with two graphs. \n" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "restart; with(networks): with(linalg):" }}{PARA 7 "" 1 "" {TEXT -1 57 "Warning, the names charpoly and rank have been redef ined\n" }}{PARA 7 "" 1 "" {TEXT -1 80 "Warning, the protected names no rm and trace have been redefined and unprotected\n" }}}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "points := \+ \{X,Y,Z,W\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'pointsG<&%\"YG%\"XG %\"ZG%\"WG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "new(G1) : add vertex(points, G1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%\"YG%\"XG%\"ZG %\"WG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "connect( \{X\},\{X ,Z,W\}, G1):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "connect( \{ W\}, \{Z\}, G1):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "draw(G1) ;" }}{PARA 13 "" 1 "" {GLPLOT2D 400 300 300 {PLOTDATA 2 "6.-%'POINTSG6 #7$$\"\"\"\"\"!$F)F)-%%TEXTG6$F&Q\"W6\"-F$6#7$$!+3Q.^?!#>F'-F,6$F2Q\"X F/-F$6#7$$!\"\"F)$!+:w1-TF5-F,6$F;Q\"YF/-F$6#7$$\"+A95`hF5F<-F,6$FEQ\" ZF/-%'CURVESG6$7$F2FE-%'COLOURG6&%$RGBGF)$\"#5F=F)-FL6$7$F2F&FO-FL6$7$ FEF&FO-%*AXESSTYLEG6#%%NONEG" 1 2 0 1 10 0 2 9 1 1 2 1.000000 45.000000 45.000000 0 0 "Curve 1" "Curve 2" "Curve 3" "Curve 4" "Curve 5" "Curve 6" "Curve 7" "Curve 8" "Curve 9" "Curve 10" "Curve 11" }}}} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "po ints := \{X,Y,Z,W\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'pointsG<&% \"YG%\"XG%\"ZG%\"WG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "new( G2) : addvertex(points, G2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%\"YG% \"XG%\"ZG%\"WG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "connect( \+ \{X\},\{X,Z,W\}, G2):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "co nnect( \{W\}, \{Z\}, G2):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "draw(G2);" }}{PARA 13 "" 1 "" {GLPLOT2D 400 300 300 {PLOTDATA 2 "6.-% 'POINTSG6#7$$\"\"\"\"\"!$F)F)-%%TEXTG6$F&Q\"W6\"-F$6#7$$!+3Q.^?!#>F'-F ,6$F2Q\"XF/-F$6#7$$!\"\"F)$!+:w1-TF5-F,6$F;Q\"YF/-F$6#7$$\"+A95`hF5F<- F,6$FEQ\"ZF/-%'CURVESG6$7$F2FE-%'COLOURG6&%$RGBGF)$\"#5F=F)-FL6$7$F2F& FO-FL6$7$FEF&FO-%*AXESSTYLEG6#%%NONEG" 1 2 0 1 10 0 2 9 1 1 2 1.000000 45.000000 45.000000 0 0 "Curve 1" "Curve 2" "Curve 3" "Curve \+ 4" "Curve 5" "Curve 6" "Curve 7" "Curve 8" "Curve 9" "Curve 10" "Curve 11" }}}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 76 " Now lets look at their adjacency matrices which are apparently not the same." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "A1 := adjacency(G1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#A1G-%'matrixG6#7&7&\"\"!\"\"\"F*F+7&F+\"\"#F*F+7&F*F*F*F*7&F+F+F *F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "A2 := adjacency(G2); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#A2G-%'matrixG6#7&7&\"\"!\"\"\"F *F+7&F+\"\"#F*F+7&F*F*F*F*7&F+F+F*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 67 "if equal(A1, A2) then print('same') else print(`not t he same`); fi;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%sameG" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 73 "Lets define a mat rix function that will interchange two rows and columns." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "inter change := (A,i, j) -> evalm( swaprow(swapcol(A,i,j),i,j) );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%,interchangeGR6%%\"AG%\"iG%\"jG6\"6$%)oper atorG%&arrowGF*-%&evalmG6#-%(swaprowG6%-%(swapcolG6%9$9%9&F8F9F*F*F*" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 141 "Now i f we interchange the 2nd and 3rd rows and columns of A2 we see that we get A1! This means that these two graphs are actually equivalent." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "interchange( A2,2,3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'matrix G6#7&7&\"\"!F(\"\"\"F)7&F(F(F(F(7&F)F(\"\"#F)7&F)F(F)F(" }}}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 329 "How do we know wh ich rows and columns to interchange? If you look very long and hard at the matrices you can sometimes see which rows and columns to swap. We can create a little Maple procedure that will check all of the possib ilities and then tell us if the matrices are equivalent, and if so, wh ich vertices need to be swapped." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 413 " check := proc(A,B)\n \011\011\011local i ,j, n, equiv;\n\011\011\011n := rowdim(A); eq uiv := false; \n\011\011\011for i from 1 to (n-1) do \n\011 \011\011for j from (i+1) to n do\n\011\011\011if \011equal( A, swapro w( swapcol(B,i,j),i,j)) \n\011\011\011then \011equiv := true; \n\011 \011\011\011print(`( Interchange vertices `,i,j,`)`); fi;\n\011\011 \011od; od; \n\011\011\011if equiv then print(`The Graphs are Equiv alent !`); \n\011\011\011else print(`The Graphs are NOT equivalent`); \+ fi;\n\011\011\011end:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 " check(A1, A2);\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%8(~Interchange~v ertices~G\"\"\"\"\"%%\")G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#% " 0 "" {MPLTEXT 1 0 30 " points := \{ A,B,C,D,E,F \} ;\n\011\011" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'pointsG<(%\"DG%\"EG% \"AG%\"BG%\"CG%\"FG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 " new (G1): \n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "\011\011 addver tex( points, G1 );\n\011\011" }}{PARA 11 "" 1 "" {XPPMATH 20 "6(%\"DG% \"EG%\"AG%\"BG%\"CG%\"FG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 " connect( \{A\}, \{B,C\}, G1):\n\011\011" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 29 " connect( \{D\}, \{E,F\}, G1):\n\011\011" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 " draw(G1);" }}{PARA 13 "" 1 "" {GLPLOT2D 400 300 300 {PLOTDATA 2 "63-%'POINTSG6#7$$!\"\"\"\"!$\"+& QKz*e!#>-%%TEXTG6$7$$\"+-+++]!#5$\"+PSDg')F3Q\"B6\"-F$6#7$$!+(******* \\F3$\"+SSDg')F3-F.6$7$$\"\"\"F)$F)F)Q\"AF7-F$6#F0-F$6#FA-F$6#7$$\"+\" *******\\F3$!+VSDg')F3-F$6#7$$!+2+++]F3$!+MSDg')F3-F.6$F&Q\"DF7-F.6$F: Q\"CF7-%'CURVESG6$7$FAF:-%'COLOURG6&%$RGBGF)$\"#5F(F)-Fin6$7$F&FSF\\o- Fin6$7$FAF0F\\o-Fin6$7$F&FLF\\o-F.6$FSQ\"EF7-F.6$FLQ\"FF7-%*AXESSTYLEG 6#%%NONEG" 1 2 0 1 10 0 2 9 1 1 2 1.000000 45.000000 45.000000 0 0 "Cu rve 1" "Curve 2" "Curve 3" "Curve 4" "Curve 5" "Curve 6" "Curve 7" "Cu rve 8" "Curve 9" "Curve 10" "Curve 11" "Curve 12" "Curve 13" "Curve 14 " "Curve 15" "Curve 16" }}}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 139 "Notice that the g raph is composed of two smaller graphs which are not connected to each other. How is demonstrated by the adjacency matrix?" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 " A1 := adj acency(G1);\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#A1G-%'matrixG6#7(7 (\"\"!\"\"\"F+F*F*F*7(F+F*F*F*F*F*F,7(F*F*F*F*F+F+7(F*F*F*F+F*F*F." }} }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 381 "Notice the matrix is a block diagonal \323 matrix. If you draw a vertical line between the 3rd and 4th colum ns, and a horizontal line between the 3rd and 4th rows, it splits the \+ matrix up into 4 smaller 3 by 3 matrices. Only upper left corner sub-m atrix and the lower right corner sub-matrix are non-zero. \n\nHere is \+ another disconnected graph. Lets see if the same thing happens again. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 " points := \{ A,B,C,D,E,F \};\n\011" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'pointsG<(%\"DG%\"EG%\"AG%\"BG%\"CG%\"FG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 " new(G1): \n" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 28 " addvertex( points, G1 );\n\011\011" }}{PARA 11 "" 1 "" {XPPMATH 20 "6(%\"DG%\"EG%\"AG%\"BG%\"CG%\"FG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 " connect( \{A\}, \{B,E\}, G1):\n \011\011" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 " connect( \{D\} , \{C,F\}, G1):\n\011" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 " d raw(G1);\n\011\011" }}{PARA 13 "" 1 "" {GLPLOT2D 400 300 300 {PLOTDATA 2 "63-%'CURVESG6$7$7$$!\"\"\"\"!$\"+&QKz*e!#>7$$!+(*******\\ !#5$\"+SSDg')F1-%'COLOURG6&%$RGBGF*$\"#5F)F*-%'POINTSG6#F'-%%TEXTG6$7$ $\"+-+++]F1$\"+PSDg')F1Q\"B6\"-F;6#F.-F>6$7$$\"\"\"F*$F*F*Q\"AFF-F;6#F @-F;6#FK-F$6$7$7$$!+2+++]F1$!+MSDg')F1FKF4-F;6#7$$\"+\"*******\\F1$!+V SDg')F1-F;6#FW-F>6$F'Q\"DFF-F>6$F.Q\"CFF-F$6$7$FKF@F4-F$6$7$F'FhnF4-F> 6$FWQ\"EFF-F>6$FhnQ\"FFF-%*AXESSTYLEG6#%%NONEG" 1 2 0 1 10 0 2 9 1 1 2 1.000000 45.000000 45.000000 0 0 "Curve 1" "Curve 2" "Curve 3" "Curv e 4" "Curve 5" "Curve 6" "Curve 7" "Curve 8" "Curve 9" "Curve 10" "Cur ve 11" "Curve 12" "Curve 13" "Curve 14" "Curve 15" "Curve 16" }}}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 " A1 := adjacency(G1);\n" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#A1G-%'matrixG6#7(7(\"\"!\"\"\"F*F*F +F*7(F+F*F*F*F*F*7(F*F*F*F+F*F*7(F*F*F+F*F*F+F,F-" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 288 "This matrix is not a block diagonal matrix. However, we can in terchange vertices to transform it into a block diagonal matrix. First we interchange E and F, the 5th and 6th vertices, then C and F, the 3 rd and 6th vertices. The result is a block diagonal matrix where each \+ block is 3 by 3." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 32 " A2 := interchange( A1, 5,6);\n\011" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#A2G-%'matrixG6#7(7(\"\"!\"\"\"F*F*F*F+7(F +F*F*F*F*F*7(F*F*F*F+F*F*7(F*F*F+F*F+F*F-F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 " interchange(A2, 3,6);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'matrixG6#7(7(\"\"!\"\"\"F)F(F(F(7(F)F(F(F(F(F(F*7(F( F(F(F(F)F)7(F(F(F(F)F(F(F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "2 0" 1 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 } {PAGENUMBERS 0 1 2 33 1 1 }