AQA A Level Further Maths ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
flashcards (Discrete) exam with ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
correct answers ||\\||\\
1. What is a connected graph?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
2. What is a walk?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
3. What is a trail?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
4. What is a path?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
5. What is a cycle?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
1. When there is a path between each pair of vertices.
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
2. A type of route in a graph. A sequence of edges where
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
you can go through vertices and edges more than once.
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
3. A trail is a walk where you can't repeat any edges.
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
4. A path is a walk where you can't repeat any edges or
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
vertices
5. A cycle is a type of path which starts and ends at the
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
same vertex. eg. BCDB (don't forget to write B again), and
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
no other vertex is visited more than once.
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
1. How would you prove that a graph is Hamiltonian?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
,2. Connected graphs can be Eulerian, Semi-Eulerian or...
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
3. What is the number of possible Hamiltonian cycles for a
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
complete network with n nodes?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
4. What are the conditions for an Eulerian graph?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
1. A graph is Hamiltonian if it contains a Hamiltonian
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
Cycle. [1] ||\\||\\
Give an example of a Hamiltonian cycle [1]
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
2. ... Non-Eulerian
||\\||\\ ||\\||\\
3. ½(n-1)! (since route forwards = route backwards)
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
4. Every vertex is of even degree and the graph is
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
connected
1. What is a subdivision?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
2. What is a tree?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
3. What is an adjacency matrix?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
4. What is a minimum spanning tree?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
, 1. Adding new vertices on an edge, splitting it into 2
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
edges.
(Don't forget to label the new vertex) ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
2. A graph with no cycles
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
3. A table which shows the number of direct connections
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
each vertex has to the other vertices ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
4. A spanning tree where the total weight of the arcs is as
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
small as possible ||\\||\\ ||\\||\\
What are the names for the 2 formula for planar graphs ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
and what are the formulas? ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
Euler's formula: ||\\||\\
no of edges = no of vertices + no of faces - 2
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
Kuratowski's theorum: ||\\||\\
A graph is only planar if it does not contain a subgraph
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
that is a subdivision of K₅ or K₃,₃ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
1. What is a distance table?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
2. How do you do Prim's on a table?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
flashcards (Discrete) exam with ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
correct answers ||\\||\\
1. What is a connected graph?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
2. What is a walk?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
3. What is a trail?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
4. What is a path?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
5. What is a cycle?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
1. When there is a path between each pair of vertices.
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
2. A type of route in a graph. A sequence of edges where
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
you can go through vertices and edges more than once.
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
3. A trail is a walk where you can't repeat any edges.
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
4. A path is a walk where you can't repeat any edges or
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
vertices
5. A cycle is a type of path which starts and ends at the
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
same vertex. eg. BCDB (don't forget to write B again), and
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
no other vertex is visited more than once.
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
1. How would you prove that a graph is Hamiltonian?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
,2. Connected graphs can be Eulerian, Semi-Eulerian or...
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
3. What is the number of possible Hamiltonian cycles for a
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
complete network with n nodes?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
4. What are the conditions for an Eulerian graph?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
1. A graph is Hamiltonian if it contains a Hamiltonian
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
Cycle. [1] ||\\||\\
Give an example of a Hamiltonian cycle [1]
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
2. ... Non-Eulerian
||\\||\\ ||\\||\\
3. ½(n-1)! (since route forwards = route backwards)
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
4. Every vertex is of even degree and the graph is
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
connected
1. What is a subdivision?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
2. What is a tree?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
3. What is an adjacency matrix?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
4. What is a minimum spanning tree?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
, 1. Adding new vertices on an edge, splitting it into 2
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
edges.
(Don't forget to label the new vertex) ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
2. A graph with no cycles
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
3. A table which shows the number of direct connections
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
each vertex has to the other vertices ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
4. A spanning tree where the total weight of the arcs is as
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
small as possible ||\\||\\ ||\\||\\
What are the names for the 2 formula for planar graphs ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
and what are the formulas? ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
Euler's formula: ||\\||\\
no of edges = no of vertices + no of faces - 2
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
Kuratowski's theorum: ||\\||\\
A graph is only planar if it does not contain a subgraph
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
that is a subdivision of K₅ or K₃,₃ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
1. What is a distance table?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
2. How do you do Prim's on a table?
||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\ ||\\||\\
