definitions Flashcards
What is the order of an algorithm?
The order tells you how changes in the size of the problem affect its run time. Increasing the size of the problem from n to m will increase the run time by a factor of f(m)/f(n).
What is a subgraph?
A graph including vertices and edges belonging to its main graph.
What is the degree/valency/order of a vertex?
The number of edges connected to the vertex.
What is a walk?
A route through a graph along edges from one vertex to the next.
What is a path?
A walk where no vertex can be visited more than once.
What is a trail?
A walk where no edge is visited more than once.
What is a cycle?
A walk that starts and ends at the same vertex and no vertex is visited more than once.
What is a Hamiltonian cycle?
A cycle where every vertex is visited.
What is Euler’s handshaking lemma?
The sum of the degrees of the vertices = 2x number of edges. Therefore the sum of odd vertices must be even.
What is a tree and what is a spanning tree.
A tree is a connected graph with no cycles, and a spanning tree is a subgraph and a tree that includes every vertex.
What is a complete graph?
A graph in which every vertex is directly connected by a single edge to each of the other vertices.
What is an isomorphic graph?
Graphs that represent the same information but drawn differently.
What is a planar graph?
A graph that can be drawn so that no two edges cross each other except at a vertex.
What is a Eulerian graph?
A graph that has a trail that starts and ends at the same vertex and contains every edge. If all the vertices of a graph are even, the graph is Eulerian.
What is a semi-Eulerian graph?
A graph that has a trail that starts and ends at different vertices and contains every edge. If exactly two vertices are odd, the graph is semi-Eulerian.
What is a tour?
A walk which visits every vertex and returns to its starting vertex. (can visit vertices more than once)
What is the aim of the TSP?
To find a tour of minimum weight.
What is the difference between the classical and practical TSP?
Classical: each vertex is visited exactly once before returning to the start.
Practical: each vertex is visited at least once before returning to the start.
