decision terminology

algorithm

algorithm

finite sequence of step by step instructions carried out to solve a problem

order (of an algorithm)

a function of the size of the algorithm

subgraph

a graph where all of the vertices and edges belong to the original graph

degree/valency/order

the number of edges attached to a vertex

walk

finite sequence of edges where the end vertex of one edge is the start vertex of another

path

a walk in which no vertex is visited more than once

trail

a walk in which no edge is visited more than once

cycle

a walk where the end vertex is the same as the start vertex and no other vertex is visited more than once

hamiltonian cycle

a cycle that includes every vertex

loop

an edge that starts and finishes at the same vertex

simple graph

no loops or multiple edges

Euler’s handshaking lemma

sum of degrees of vertices = 2 x number of edges

tree

connected graph with no cycles

spanning tree

subgraph which is also a tree

complete graph

a graph where every vertex is connected to every other vertex with one edge

isomorphic graphs

graphs which display the same information but are drawn differently

adjacency matrix

describes the number of arcs between vertices

distance matrix

describes the weight of arcs between vertices

planar graph

can be drawn in a plane such that no two edges meet except at a vertex

Eulerian graph

trail that includes every edge, starts and finishes at the same vertex, and has only even vertices

Semi-Eulerian graph

trail that includes every edge, but starts and finishes at different vertices, and has exactly two odd vertices

tour

a walk which visits every vertex and returns to its starting vertex

classical problem

each vertex is visited exactly once before returning to the start

practical problem

each vertex is visited at least once before returning to the start

difference between Dijkstra’s and Floyd’s

Dijkstra’s finds the shortest path between two vertices, Floyd’s finds the shortest path between every pair of vertices