Hey there! Sign in to join this conversationNew here? Join for free
x Turn on thread page Beta
    • Thread Starter
    Offline

    12
    ReputationRep:
    I can do the algorithm however after I finish it all the lines do not connect and I need to pick a line to connect this. Is there a way without drawing a diagram that I can do this?
    Also when I write my lines like this
    EG 13
    AC 15
    AB 18
    DE 19
    FG 27

    do they have to be in size order to get the marks or doesn't it matter?]

    EDIT: Kruskals algorithm not prims wrong title
    • Very Important Poster
    Offline

    21
    ReputationRep:
    Very Important Poster
    (Original post by Sayless)
    I can do the algorithm however after I finish it all the lines do not connect and I need to pick a line to connect this. Is there a way without drawing a diagram that I can do this?
    Also when I write my lines like this
    EG 13
    AC 15
    AB 18
    DE 19
    FG 27

    do they have to be in size order to get the marks or doesn't it matter?
    For your first question, look at all the possible options and pick the one with the least weight. There can't be that many of them left!

    For your second question, I'm not familiar with AQA but I would hope that it doesn't matter which order you write them in.
    • Thread Starter
    Offline

    12
    ReputationRep:
    (Original post by SeanFM)
    For your first question, look at all the possible options and pick the one with the least weight. There can't be that many of them left!

    For your second question, I'm not familiar with AQA but I would hope that it doesn't matter which order you write them in.
    Thanks, do you have to draw all the lines out in order to decide which one will connect them all together?
    Offline

    1
    ReputationRep:
    If you've done the algorithm correctly you should be able to get from one point to any other point, without drawing an additional line. all the lines don't need to be connected, but you shouldn't have any points that can't reach any other.

    you should write them out in the order that you select each line, that's what you'll get the marks for, more than the answer, is the method. So write them down in the order you work them out
    • Very Important Poster
    Offline

    21
    ReputationRep:
    Very Important Poster
    (Original post by Sayless)
    Thanks, do you have to draw all the lines out in order to decide which one will connect them all together?
    That would be the best way to do it - if you're not given a template then you could make a neat shape depending on how many vertices you have (maybe a square of some sort).
    Offline

    14
    ReputationRep:
    (Original post by Sayless)
    I can do the algorithm however after I finish it all the lines do not connect and I need to pick a line to connect this. Is there a way without drawing a diagram that I can do this?
    Also when I write my lines like this
    EG 13
    AC 15
    AB 18
    DE 19
    FG 27

    do they have to be in size order to get the marks or doesn't it matter?]

    EDIT: Kruskals algorithm not prims wrong title
    With 7 vertices you'll need 6 edges (number of vertices - 1).
    I don't know how AQA questions are worded, but since Kruskal involves picking the smallest edge first, etc, you can only show that you have applied the algorithm properly if you list the edges in ascending length, i.e. in the order that you picked them.
    • Thread Starter
    Offline

    12
    ReputationRep:
    (Original post by tiny hobbit)
    With 7 vertices you'll need 6 edges (number of vertices - 1).
    I don't know how AQA questions are worded, but since Kruskal involves picking the smallest edge first, etc, you can only show that you have applied the algorithm properly if you list the edges in ascending length, i.e. in the order that you picked them.
    what are vertices?

    also i use the algorithm and do the first 6 in correct ascending order, then i draw the diagram to find the 7th one which connects them all together and stick that one at the end e.g looking something like this

    EG 13
    AC 15
    AB 18
    DE 19
    FG 27
    BE 21 (One which connects them all together)

    would that be right since i don't know how to find it out without drawing the diagarm and using that to visually see there is a gap, then i pick the smallest unused length
    Offline

    14
    ReputationRep:
    (Original post by Sayless)
    what are vertices?

    also i use the algorithm and do the first 6 in correct ascending order, then i draw the diagram to find the 7th one which connects them all together and stick that one at the end e.g looking something like this

    EG 13
    AC 15
    AB 18
    DE 19
    FG 27
    BE 21 (One which connects them all together)

    would that be right since i don't know how to find it out without drawing the diagarm and using that to visually see there is a gap, then i pick the smallest unused length
    A vertex (plural vertices) is another word for a node.

    If you are using Kruskal's algorithm properly, your sequence of edges (arcs) must be in increasing size all the way, so you can't have 27 then 21.

    I don't understand why you would be doing this without already having a diagram. Having looked at a few AQA exam papers, there is always a drawing of the original graph. You should therefore mark on the edges as you include them, so that you know when it is joined up. But you should always consider the edges starting with the shortest and then the second shortest, etc. The safest way (even if it is a bit tedious) is to make a list of all the edges in order of size and then go through deciding whether to include them on your tree or not, by deciding whether they make a cycle (in which case don't use them).
    • Thread Starter
    Offline

    12
    ReputationRep:
    (Original post by tiny hobbit)
    A vertex (plural vertices) is another word for a node.

    If you are using Kruskal's algorithm properly, your sequence of edges (arcs) must be in increasing size all the way, so you can't have 27 then 21.

    I don't understand why you would be doing this without already having a diagram. Having looked at a few AQA exam papers, there is always a drawing of the original graph. You should therefore mark on the edges as you include them, so that you know when it is joined up. But you should always consider the edges starting with the shortest and then the second shortest, etc. The safest way (even if it is a bit tedious) is to make a list of all the edges in order of size and then go through deciding whether to include them on your tree or not, by deciding whether they make a cycle (in which case don't use them).
    Theres a diagram on the question but it is a fully connected diagram not a minimum span diagram.

    I use Kurskal's algorithm to get the smallest sides in order however, if I have AB and CA I won't use another AB line since I already have an A and B component in use already.

    I do this in order then at the end I draw a minimum spam diagram, then if I look at it then it is missing a connection, so it is broken. I will relook at the pre minimum span diagram given in the question and looking for the shortest unused side which when drawn on my minimum span diagram, will connect it all together.

    I add the smallest unused side at the end of all of my algorithm since I can only do it at the end as thats the only time I know when a side is unused and/if my minimum span diagram is fully connected or not.

    I do it increasing all the way, without using the same letter twice as stated above, then at the end I will put it the smallest unused side in order to connect it together as a minimum span diagram.
    Offline

    14
    ReputationRep:
    (Original post by Sayless)
    Theres a diagram on the question but it is a fully connected diagram not a minimum span diagram.

    I use Kurskal's algorithm to get the smallest sides in order however, if I have AB and CA I won't use another AB line since I already have an A and B component in use already.

    I do this in order then at the end I draw a minimum spam diagram, then if I look at it then it is missing a connection, so it is broken. I will relook at the pre minimum span diagram given in the question and looking for the shortest unused side which when drawn on my minimum span diagram, will connect it all together.

    I add the smallest unused side at the end of all of my algorithm since I can only do it at the end as thats the only time I know when a side is unused and/if my minimum span diagram is fully connected or not.

    I do it increasing all the way, without using the same letter twice as stated above, then at the end I will put it the smallest unused side in order to connect it together as a minimum span diagram.
    Are A, B etc your nodes (vertices, points) or are they your edges (arcs, lines)?

    If A, B etc are your nodes, what you are doing is not Kruskal's algorithm.
    • Thread Starter
    Offline

    12
    ReputationRep:
    (Original post by tiny hobbit)
    Are A, B etc your nodes (vertices, points) or are they your edges (arcs, lines)?

    If A, B etc are your nodes, what you are doing is not Kruskal's algorithm.
    AB is an edge, A is a point on the edge, yeah it is kruskals algorithm though

    e.g F-----------G
    that is the edge FG
    Offline

    14
    ReputationRep:
    (Original post by Sayless)
    AB is an edge, A is a point on the edge, yeah it is kruskals algorithm though

    e.g F-----------G
    that is the edge FG
    Right then. Once you have chosen AB, there is no reason why you can't next choose another edge going from A or B. In fact, if one of those is the next shortest, then you must choose that edge. What you must not do is choose an edge which causes you to draw a cycle, e.g a triangle or a quadrilateral. Drawing the edges that you have already chosen on the diagram of the whole graph helps you to look out for cycles.
    • Thread Starter
    Offline

    12
    ReputationRep:
    (Original post by tiny hobbit)
    Right then. Once you have chosen AB, there is no reason why you can't next choose another edge going from A or B. In fact, if one of those is the next shortest, then you must choose that edge. What you must not do is choose an edge which causes you to draw a cycle, e.g a triangle or a quadrilateral. Drawing the edges that you have already chosen on the diagram of the whole graph helps you to look out for cycles.
    Thats prims algorithm, prims algorithm is starting from A and going from there for the shortest unused sides, not jumping around.

    kruskals is just choosing the smalling unused side and putting it in order without making a cycle,

    but i understand the part about drawing the edges on the whole graph to look for cycles i'll do that in future to help me notice it, i guess i could always do my method then cross it all out and rewrite it but in order and they'll never know
    Offline

    14
    ReputationRep:
    (Original post by Sayless)
    Thats prims algorithm, prims algorithm is starting from A and going from there for the shortest unused sides, not jumping around.

    No, Prim's goes to the nearest vertex, which may mean that the edges you pick are not gradually increasing in size.

    kruskals is just choosing the smalling unused side and putting it in order without making a cycle,

    Yes, but that smallest unused side may come from one of the vertices you've already used. You are ignoring some of the possible options.

    but i understand the part about drawing the edges on the whole graph to look for cycles i'll do that in future to help me notice it, i guess i could always do my method then cross it all out and rewrite it but in order and they'll never know
    They will notice you've done it wrongly if your tree is not the shortest possible, which it may well not be, the way you are doing it.

    You could have a look at https://www.youtube.com/watch?v=5XkK88VEILk

    I suggest that you don't argue too much with people who try to help you by telling you where you are going wrong. It may be that they know better than you.
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: October 18, 2015
Poll
Do I go to The Streets tomorrow night?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.