Graphs & Networks as Matrices | D1 Edexcel A-Level Maths Tutorial 7

[00:00:01]hi there and welcome to tutorial 7 which is a lesson on graphs and in particular how you can represent graphs using matrices this is the second in my tutorials on graph Theory it's for the Ed EXL Decision One maths a level course but is applicable to most other decision or discrete maths a Lev modules for any more help with your math studies gcsc or a level see my YouTube channel on my website okay let's start straight away by looking at the Ed EXL specification um for this so This Is The Ed XL specification and it tells us we need to learn various algorithms to do with graphs which I will do in future tutorials however it does say very explicitly that Matrix representation for the use in prims algorithm is expected and it tells us that drawing a network from a matrix and writing down a matrix associated with a network will be involved that is to say uh to draw a uh Matrix from a a network is required knowledge in particular maybe for prim's algorithm and we need to go both ways around we need to from a graph or network be able to uh draw a matrix and conversely from a matrix um draw the associated graph or network okay let's start by looking at examples straight away right firstly we need to know about adjacency matrices and we need to be able to draw these matrices from the graph what is an adjacency Matrix well it's simply a matrix that's a row or array of numbers in like in a table form that records the number of direct links between the vertices in particular let's look at this case here right let's take a between A and B there is one direct link between these vertices between a and C there's one Link Between A and D there's in fact two links between E and F there's one link between f and g there's one link between G and D there's one link between D and F there's one link between C and D there are two links and between D and B uh sorry C and B there are one link there is one link now what about B we're actually going to record a loop remember this is a loop um as two links because we could think of it as an arc coming out that way and going into b or coming out this way and going into B that way so we're always going to record that as two and also let's say between a and g how many links none between B and E none Etc so we want to record this in a table or a matrix as we call it an adjacency Matrix first thing to do is list your vertices across as the headings of the column and list your vertices down as the headings of the row and then we're simply going to fill in this table recording the links between each of these right between a and a there are no links between A and B there is one between a and C there is one between A and D there is none between A and E there are two between a and F there are none and between a and g there are none now because directions not important here um we the looking down this column we have the same answers as across here because it's answering the same question for example how many links between e and and a well that's the same as how many links between A and E so we can just fill this in directly down because direction is not important so here it will be 0 1 1 0 2 0 0 okay let's go to B between b and a we know there is one between B and B we've called that two between B and C is one between B and D there's none between B and E there's none between B and F there's none and between B and G there's none and we can copy this down here 1 2 1 0 0 0 0 1 2 1 0 0 0 and zero Okay C we know between C and A there's one and between C and B there's one and that's recorded between C and D there are uh between C and C there are none between C and D there are two between c and e there are none C and F there is one okay between C and G there are none we can fill this across 1 one 0 2 0 1 0 1 one 0 2 0 1 and zero okay D we know between d and a there are none between D and B there are none between D and C there are two between D and D there are none between d and e there are none between D and F there is one and between D and G there is one 0 02 0 0 1 1 1 0 0 2 0 0 1 and one okay and E well e is connected to a only and F so it's two connected to a and it's one connected to F it's not connected to anything else so it would be z z here and it would follow the same pattern down here and we would have a one here and a zero and F Well we've mostly filled out f is not connected to a b but is connected to C once is connected to D once is connected to e once is not connected to itself and is connected to G so 01 and here would be a one here as well to have the Symmetry here and lastly G well we know G was only connected to D and um f and that's already recorded how many times it connected to itself none and that is the adjacency Matrix for this particular graph and it tells us in particular so if we look at if we were looking at it this way around and trying to interpret if we look say here it tells us that there is one link between C and F and because everything is symmetrical in this particular uh Matrix I symmetrical either side of this line here we know that direction is not important right you pause the video now I would like you to have a go at drawing The adjacency Matrix for this particular graph and in 10 seconds I'll go through the answer you mark your work and here was my adjacency Matrix for this here I got the following so do make sure um you got the following uh same answer as I got there and as in the case before it was symmetric about that line there because um Direction didn't matter it was not a diaph okay and I'd like to move on now let's move on to the next thing we need to talk about it's still about adjacency matrices but this time can we from one of the matrices draw the graph from it so here's an example here remember what this is telling me well it's telling me that between a and C there are no links between A and B there are one Etc now let's just see if this is a symmetrical graph 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 1 um 0 02 1 0 02 1 and 1 1 1 0 1 1 1 0 it is symmetrical about this line that's telling me direction in the graph is not important now I've got four vertices so the way I like to do the these things is just put them in a square the obvious shape for me is to put them in a square and then just play around with them okay A and A there's none A and B there's one so I'm going to draw in straight away A Link Between A and B okay and I'm just going to let's say tick off as I do it so ticked off ticked up between a and C there are none between A and D there is one so I'm going to put one in between a and let's say d okay between B and A there is one but I've already done this one I've done these down here by the same virtue okay between B and B there's none between B and C there's none between B and D there is one so I need to put that one in like that and I've done these here by symmetry between C and A I've done between C and B I've done between C and C there is two now the only way you can have two between C and D C and C is if you have a Loop going on here so I'm just going to draw in for us there's a loop going on here okay and between C and D there's one so let's draw that in between C and D there's one okay and I have done this one by the same virtue between D and D there's none so there you go I have drawn myself uh a graph um from that adjacency Matrix there there are many ways of drawing that graph out isomorphic to this but I found it easier to draw in a square format now I'd like you to pause the video have a go at this adjacency Matrix below see if you can draw the graph represented by that adjacency Matrix I'll go through the answer in 10 seconds okay here are the answers I would have firstly drawn out um the vertices like that let's just fill it in um together this time again I won't go ahead between between a and a B and B C and C D and D there are none so I know there are no Loops okay and everything is still symmetrical about this here so it's symmetrical so I know once I've done one I've done the other side between A and B there are two so there's one there and let's draw another one in let's say as follows another one like that okay so I've done that one between a and C there are none between A and D there is one so let's draw that in between A and D there's one there um and I've done that and I've done that and that and that by the same virtue okay between B and C there is one so between B and C there's one and between B and D there's none okay so I've done that one and that one one and that one and that one now and between C and D there's one and I have done these two so between C and D there's one and I've got it looking something like that now yours may be different if you had the C there and the D there for example A B C D it would look slightly different but it has the same um it's isomorphic to that graph it's got the same connections the same number of vertices the same number of arcs okay let's move on now to the next thing we need to talk about and the next thing thing is distance matrices now what do you think these are well distance matrices records the weights on the edges of the graph it's not about Connections and how many connections there are this time it's weights on the edges okay so take a look at this graph here this is got uh vertices a b c d and e and it tells us various weights between these these could be distances um prices or uh anything to that effect okay time Etc so I'm going to record these in the distance Matrix exactly as before I'm going to label um my table as follows ABCDE e across the top ABCDE e across the bottom but this time um one thing is I'm labeling in weights now between a and a B and B C and C D and D e and e between a and a there's no weight so there will never be an answer along this diagonal here there can't be a weight Associated um with just a point okay cuz there's no Edge there the weights are always associated with edges okay now between A and B is 17 between a and C there's 18 between A and D there isn't anything so so we won't put zero but we'll just say there's no assigned weight there between A and E there's no no no assigned weight there now there are no directions associated with this graph it's a normal graph it's not a DI graph so it's going to be symmetrical just like before okay so if we had nothing 17 18 nothing nothing we're can have nothing 17 18 nothing nothing going down because they just mean the same thing okay from b 17 to a 15 uh nothing to be itself 15 to C 19 to D and 23 to e and we can just copy that down as well 15 19 and 23 okay and then we're going to move on to C well we've done C we've said that's 18 that's 15 C is only then connected to D and that's 20 so 20 and not applicable 20 and not applicable then D well we've done it connected to C and B already we just need to talk about it connection to e which is 16 so it's connected to e at 16 connected there to e at 16 and there we go that is uh the um distance Matrix associated with that graph okay now a diagraph this is a diagraph because there's some direction here associated with some of the um arcs okay so that's quite important to us when we're drawing out our graph so let's do it as we did before label the columns okay r s S T U V and W and let's just fill it in now R to R is nothing is not applicable R to S is four R to T is 11 R to U is not applicable R to V is not applicable and R to W is not applicable okay s S2 R is four S to S is not applicable s to T is not applicable s to U is 9 s to V not applicable s to W is 10 okay from t t to R we know is 11 T to S not applicable T to T not applicable T to U is 8 T to V not applicable T to W not applicable okay let's go for U here right U to R not applicable U to S is 9 UM U to T is 8 U to U is not applicable U to V now U to V is six because you're going from U to V so that's six and U to W is not applicable now let's go from v v to R not applicable V to S not applicable V to T not applicable V to U now it's seven this time because we're going from V to to U so it's seven okay and V to V not applicable V to W well V to W is not applicable you can't go from V to W because you can only go from W to V so not applicable okay and lastly W will W to R not applicable W to S is 10 W to T not applicable W to U not applicable W to V yes is nine and W to W not applicable now the thing to notice it the difference between a graph and a diaph let's just point out clearly a graph is symmetrical about that diagonal Point okay it's symmetrical that everything's the same but along the diagonal here okay we don't have symmetry for example okay it's different from V to W it was not applicable than is from W to V okay and that's because direction is associated with a diph okay now it's time for you to have an a go an example yourself pause the video have a go in 10 seconds I'll go through Mark your work here we go and the answers in this case here let's just take a look now Mark your work here's the uh Matrix I got associated with that graph there okay last thing we've got to do we have now got to go from a matrix a distance Matrix to a graph and see if we can fill that in so let's do an example then you're going to have a go right um here we've got 1 2 3 4 5 six six um nose or vertices so I always draw it in the shape of a hexon 1 2 3 4 5 and six and we're just going to try and fill in from that a to a obviously nothing A to B there's no connection a to c there's no connection a to d there's no connection a to e there is a connection so let's draw in a to e okay and a to F there's a connection and we know that the distances here a to e is 15 and a to F is 8 and we know it's the same this way okay as well so we've covered off all of these here okay now let's go for b b uh to C there is a connection so let's draw it in B to D there is a connection so let's draw it in uh B to e there is a connection so let's draw it in and B to F there is a connection so let's draw it in and let's draw all our numbers in there B to C okay is 9 B to D is 13 B to e is 17 B to F is 11 okay and it was symmetrical down here as well so we've done all these 9 13 17 11 13 17 and 11 we're done okay let's go from C Okay C to D there is a connection so let's draw it in C to D okay and that's it the there's no other ones here so C to D and there's no others and that was eight and is symmetrical so we've done it this way D there was an only connection with e so let's cross all these off and we know that d goes to e and it's got a distance or weight of 10 and we've done these two as well and E and F are not connected in any way so we can cross these off and that is our Associated graph from that Matrix okay um it's quite easy um so you just have to be consistent in how you do it and do watch if things are symmetrical or not because if they're not that will affect things so don't just cross just because you've done a cross don't cross off down check it symmetrical okay your turn now there's a question Below have a go and then uh I'll go through it and you can mark your work okay and now it's time to mark your work so take a look here here is the answer and and you make sure you mark your work against that okay and that's it that's everything we need to know about converting from a graph or network to a matrix and then converting back from a matrix to a network or graph two types of matrices we need to know adjacency Matrix which records the links between each of the vertices and the distance Matrix which records the weights of the various arcs okay then to finish with um homework and further study um you should read chapter 2 page 34 to 39 and work through the examples on those and then you should do exercise 2B which is on page 35 and 36 questions 7 8 9 and 10 next thing I suggest you do is the past paper questions video seven which are the questions that have come up in regard to matrices adjacency matrices and um distance matrices just so you practice the ones that have come up for the exam purposes thank you for watching this video I hope you found it useful in your study for decision one