Decision Year 1 Terms Flashcards
Algorthim
A finite sequence of instructions for solving a problem.
Bipartite graph
A graph with two sets of nodes such that arcs only connect to nodes from one set to the other.
Complete graph, Kn
A simple graph such that each of its n nodes is directly connected by an arc to every other node.
Connected graph
A graph such there is a path between any two nodes of the graph.
Cycle
A closed trail where only the initial and final nodes are the same.
Digraph
A graph with directed arcs.
Euler’s relationship
R + N = A + 2
Eulerian graph
A connected graph which has a closed trail containing every arc precisely once.
Graph
A set of points (called nodes or vertices) joined by lines (called arcs or edges).
Greedy algorthim
An algorithm where the immediately ‘best’ step is made without any concern about the long-term consequences of this choice.
Hamiltonian cycle
A cycle which passes through every node on a graph.
Minimum connector
A spanning tree whose arcs have the minimum possible total weight.
Network
A graph with numbers (called weights) associated with its arcs.
Order (of a node)
The number of arcs meeting at that node.
Order (of an algorithm)
A measure of the ‘run-time’ of the algorithm as a function of the size of the problem.
Path
A trail such that no node is passed more than once.
Planar graph
A graph which can be drawn in a plane in such a way that arcs only meet at nodes.
Semi-Eularian graph
A connected graph with a trail which is not closed that contains every arc precisely once.
Simple graph
A graph without loops or multiple arcs.
Spanning tree
A subgraph which is a tree connecting all the nodes of the graph.
Subgraph of G
A graph whose nodes and arcs are all in the graph G.
Trail
A sequence of arcs such that the end node of one arc is the start node of the next.
Travelling salesperson problem
A classical problem of finding a Hamiltonian cycle of minimum weight. (In the practical problem, nodes and arcs may be revisited).
Tree
A connected graph with no cycles.
