{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 32 "Chapter 8 : Discrete Mathematics
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 3 "" 0 "" {TEXT -1 16 "803 G
raph 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, c
reate graphs in Maple and generate diagrams and adjacency matrices, ex
amine equivalency of graphs, and the concepts of connected and unconne
cted graphs.\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( networks): with(linalg):\n" }}{PARA 7 "" 1 "" {TEXT -1 57 "W
arning, the names charpoly and rank have been redefined\n" }}{PARA 7 "
" 1 "" {TEXT -1 80 "Warning, the protected names norm and trace have b
een redefined and unprotected\n" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 72 "_________________________________________
_______________________________" }}{PARA 4 "" 0 "" {TEXT -1 18 "A. Cre
ating Graphs" }}{PARA 0 "" 0 "" {TEXT -1 72 "_________________________
_______________________________________________" }}{PARA 0 "" 0 ""
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 412 "A graph is a diagram wit
h vertex points, and edges connecting some or all of the vertices. \n
\nLets consider this example. An airline only flies to certain cities \+
: New York, Toronto, Los Angeles, San Francisco, Chicago, Denver, and \+
New Orleans. We can create a set with these cities. Remember that name
s in Maple can not contain blank characters, so its necessary to use a
n underscore between 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<)%,Los_AngelesG%(Toront
oG%(ChicagoG%'DenverG%,New_OrleansG%.San_FranciscoG%)New_YorkG" }}}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 84 "We\325ll \+
inform Maple that we wish to create a new graph with these cities as v
ertices." }}{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( cities, G);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6)%,Los_Angele
sG%(TorontoG%(ChicagoG%'DenverG%,New_OrleansG%.San_FranciscoG%)New_Yor
kG" }}}{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 to every other city. There are flights from New York to Los
Angeles, Toronto, 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
_Angeles, Toronto, Chicago\}, G):" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 191 "In a sim
ilar way, we indicate that Los Angeles also has flights to San Francis
co, Denver, and Chicago. We don\325t need to mention New York because \+
that connection was already established above." }}{PARA 0 "" 0 ""
{TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "connect( \{L
os_Angeles\}, \{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 O
rleans, and from San Francisco to Denver." }}{PARA 0 "" 0 "" {TEXT -1
0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "connect( \{Chicago\},
\{Toronto, 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:-%'CURVESG6$7$7$$\"+D!)*[B'!#5$!+>[J=yF*7$$!+z')o4!*F*$
!+!RP)QVF*-%'COLOURG6&%$RGBG\"\"!$\"#5!\"\"F6-F$6$7$7$$\"\"\"F6$F6F6F-
F2-F$6$7$7$$!+R$4_A#F*$\"+A\"z#\\(*F*F=F2-F$6$7$FD7$$\"+=!)*[B'F*$\"+D
[J=yF*F2-F$6$7$FD7$$!+J$4_A#F*$!+C\"z#\\(*F*F2-F$6$7$F'F=F2-%'POINTSG6
#F=-%%TEXTG6$F=Q(Chicago6\"-Fgn6#FL-Fjn6$FLQ'DenverF]o-Fgn6#FD-Fjn6$FD
Q,Los_AngelesF]o-Fgn6#7$F.$\"+#RP)QVF*-Fjn6$FjoQ,New_OrleansF]o-Fgn6#F
--Fjn6$F-Q)New_YorkF]o-Fgn6#FT-Fjn6$FTQ.San_FranciscoF]o-Fgn6#F'-Fjn6$
F'Q(TorontoF]o-F$6$7$F=FjoF2-F$6$7$FLFTF2-F$6$7$FDF-F2-%*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" "Curve 13" "Curve 14" "
Curve 15" "Curve 16" "Curve 17" "Curve 18" "Curve 19" "Curve 20" "Curv
e 21" "Curve 22" "Curve 23" }}}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA
0 "" 0 "" {TEXT -1 221 "As we can see, there are plenty of connections
. However, 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 York, 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 20 "B. Adjacency Matrics" }}{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 be difficult to work graphs as diagrams. A more conveni
ent way to analyze graphs mathematically is to represent them as matri
ces. A matrix representation for a graph is called an adjacency matrix
\323. \n\nThe way it works is this. For each vertex, there is a row an
d column of the matrix. For example if there are six vertices, then th
e matrix will be six by six. If there is a connection between vertex 2
and vertex 5, then there will be a 1 in row 2, column 5 and also in r
ow 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 v
ertex 4, then there will be a zero in row 3 column 4 and row 4 column \+
3. Maple will create 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')F
5Q\"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-%'COL
OURG6&%$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" "Cur
ve 12" "Curve 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 mat
rix represents all of the connections between the vertices. Vertex A i
s connected to vertices B and C. We can see that in the matrix by look
ing down the first column and seeing 1\325s in the 2nd and 3rd rows. V
ertex B is connected to A, and E. This is indicated by looking down th
e 2nd column and seeing 1\325s in the 1st and 5th locations. C is conn
ected to A, D, and F, so the 3rd column has 1\325s in the 1st, 4th, an
d 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. Equivalen
t Graphs" }}{PARA 0 "" 0 "" {TEXT -1 72 "_____________________________
___________________________________________" }}{PARA 0 "" 0 "" {TEXT
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 942 "\nSometimes two graphs appear \+
to be different graphs, however in reality they are essentially the sa
me graph with the vertices re-arranged with the connections the corres
ponding places. For example if you start with any graph diagram, and s
imply move some of the vertices to new location, keeping the connectio
ns attached, it would cause the graph to appear different, but actuall
y it would be contain the same connection information as before the al
teration. It can be very hard to see that two graphs are equivalent ju
st by inspecting the diagram. Also, at times two graphs can appear to \+
be equivalent but actually be different. \n\nThere is a method to dete
rmine if two graphs are equivalent using their adjacency matrices. Eve
n two equivalent graphs can have different adjacency matrices. However
, interchanging vertices on the graph is equivalent to interchanging r
ows and columns of the matrices. Lets consider an example with two gra
phs.\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%\"WG
%\"XG%\"ZG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "new(G1) : add
vertex(points, G1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%\"YG%\"WG%\"XG
%\"ZG" }}}{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$$\"+A95`h!#>$!\"\"\"\"!-%%TEXTG6$7$F*$!+:w1-TF)Q\"Y6\"-F$6#F0-%'CUR
VESG6$7$7$$!+3Q.^?F)$\"\"\"F,F;-%'COLOURG6&%$RGBGF,$\"#5F+F,-F86$7$7$F
>$F,F,F;F@-F.6$F&Q\"ZF4-F86$7$FIF&F@-F86$7$F;F&F@-F$6#FI-F.6$F;Q\"XF4-
F$6#F;-F.6$FIQ\"WF4-%*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" }}}}{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 "points := \{X,Y,Z,W\};" }}{PARA 11 "" 1 ""
{XPPMATH 20 "6#>%'pointsG<&%\"YG%\"WG%\"XG%\"ZG" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 32 "new(G2) : addvertex(points, G2);" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6&%\"YG%\"WG%\"XG%\"ZG" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 26 "connect( \{X\},\{X,Z,W\}, G2):" }}}{EXCHG {PARA 0 "
> " 0 "" {MPLTEXT 1 0 23 "connect( \{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$$\"+A95`h!#>$!\"\"
\"\"!-%%TEXTG6$7$F*$!+:w1-TF)Q\"Y6\"-F$6#F0-%'CURVESG6$7$7$$!+3Q.^?F)$
\"\"\"F,F;-%'COLOURG6&%$RGBGF,$\"#5F+F,-F86$7$7$F>$F,F,F;F@-F.6$F&Q\"Z
F4-F86$7$FIF&F@-F86$7$F;F&F@-F$6#FI-F.6$F;Q\"XF4-F$6#F;-F.6$FIQ\"WF4-%
*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" }}}
}{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%\"AG%
\"BG%\"CG%\"EG%\"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%
\"AG%\"BG%\"CG%\"EG%\"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-%'CURVESG6$7$7$$!\"\"\"\"!$\"
+&QKz*e!#>7$$\"+\"*******\\!#5$!+VSDg')F1-%'COLOURG6&%$RGBGF*$\"#5F)F*
-F$6$7$F'7$$!+2+++]F1$!+MSDg')F1F4-F$6$7$7$$\"\"\"F*$F*F*7$$!+(*******
\\F1$\"+SSDg')F1F4-F$6$7$FE7$$\"+-+++]F1$\"+PSDg')F1F4-%%TEXTG6$F.Q\"F
6\"-%'POINTSG6#F'-FW6$F'Q\"DFZ-Ffn6#F=-FW6$F=Q\"EFZ-Ffn6#FI-FW6$FIQ\"C
FZ-FW6$FEQ\"AFZ-Ffn6#FQ-FW6$FQQ\"BFZ-Ffn6#F.-Ffn6#FE-%*AXESSTYLEG6#%%N
ONEG" 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" "Curve 13" "Curve 14" "Cu
rve 15" "Curve 16" }}}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "
" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 139 "Notice that the graph \+
is composed of two smaller graphs which are not connected to each othe
r. How is demonstrated by the adjacency matrix?" }}{PARA 0 "" 0 ""
{TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 " A1 := adjac
ency(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 matr
ix. If you draw a vertical line between the 3rd and 4th columns, 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-matrix and
the lower right corner sub-matrix are non-zero. \n\nHere is another d
isconnected graph. Lets see if the same thing happens again." }}{PARA
0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 " p
oints := \{ A,B,C,D,E,F \};\n\011" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>
%'pointsG<(%\"DG%\"AG%\"BG%\"CG%\"EG%\"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%\"AG%\"BG%\"CG%\"EG%\"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 " draw(G1);\n
\011\011" }}{PARA 13 "" 1 "" {GLPLOT2D 400 300 300 {PLOTDATA 2 "63-%'C
URVESG6$7$7$$!\"\"\"\"!$\"+&QKz*e!#>7$$\"+\"*******\\!#5$!+VSDg')F1-%'
COLOURG6&%$RGBGF*$\"#5F)F*-F$6$7$7$$\"\"\"F*$F*F*7$$\"+-+++]F1$\"+PSDg
')F1F4-%%TEXTG6$F.Q\"F6\"-%'POINTSG6#F'-FG6$F'Q\"DFJ-FL6#7$$!+2+++]F1$
!+MSDg')F1-FG6$FSQ\"EFJ-FL6#7$$!+(*******\\F1$\"+SSDg')F1-FG6$FgnQ\"CF
J-FG6$F=Q\"AFJ-FL6#FA-FG6$FAQ\"BFJ-F$6$7$F'FgnF4-F$6$7$F=FSF4-FL6#F.-F
L6#F=-%*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" "Cur
ve 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 ma
trix is not a block diagonal matrix. However, we can interchange verti
ces to transform it into a block diagonal matrix. First we interchange
E and F, the 5th and 6th vertices, then C and F, the 3rd and 6th vert
ices. 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 "60 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1
2 33 1 1 }