WorksheetsEdexcel Decision Maths 1 - Definitions
Total questions: 20
Worksheet time: 13mins
Select all the words that define "the number of edges incident to a vertex".
Degree
Order
Node
Weight
Valency
A _________ of G is a graph, each of whose vertices belongs to G and each of whose edges belongs to G.
Subgraph
Tree
Vertex
Minimum Spanning Tree
Another name for a vertex is... ?
Node
Degree
Valency
Order
Another name for an edge is... ?
Arc
Node
Vertex
Face
A finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once.
Path
Walk
Trail
Cycle
A path in which you are permitted to return to vertices more than once.
Walk
Trail
Cycle
Hamiltonian cycle
A walk which visits every vertex, returning to its starting vertex.
Tour
Path
Digraph
Tree
*Select all correct answers*
If a graph has a number associated with each edge then the graph is called a ... ?
Weighted graph
Network
Digraph
Hamiltonian Cycle
*Select all correct answers*
A closed path, i.e. the end vertex of the last edge is the start vertex of the first edge.
Cycle
Circuit
Walk
Network
Two vertices are _______ if there is a path between them.
Connected
Odd
Even
Weighted
If the edges of a graph have a direction associated with them, the graph is known as a ________.
Digraph
Network
Weighted graph
Minimum Spanning Tree
A connected graph with no cycles.
Tree
Walk
Path
Circuit
A graph with every vertex of even degree.
Eulerian graph
Hamiltonian graph
Newtonian graph
Gaussian graph
A graph with exactly two vertices of odd degree.
Semi-Eulerian graph
Eulerian graph
Hamiltonian graph
Semi-Hamiltonian graph
A cycle that passes through every vertex of a graph once and only once, and returns to its start vertex.
Hamiltonian cycle
Eulerian cycle
Newtonian cycle
Gaussian cycle
A graph that can be drawn in a plane in such a way that no two edges meet each other, except at a vertex to which they are both incident, is called a ... ?
Planar graph
Eulerian graph
Semi-Eulerian graph
Hamiltonian cycle
Two graphs are ________ if they have the same number of vertices and the degrees of corresponding vertices are the same.
Isomorphic
Connected
Similar
Eulerian
For three vertices A, B and C, the triangular inequality (where AB is the longest length) is ... ?
length AB ≤ length AC + length BC
length AC ≤ length AB + length BC
length BC ≤ length AC + length AB
In the classical travelling salesperson problem ...
each vertex must be visited exactly once before returning to the start.
each vertex must be visited at least once before returning to the start.
each arc must be traversed exactly once before returning to the start.
each arc must be traversed at least once before returning to the start.
In the practical travelling salesperson problem ...
each vertex must be visited exactly once before returning to the start.
each vertex must be visited at least once before returning to the start.
each arc must be traversed exactly once before returning to the start.
each arc must be traversed at least once before returning to the start.
