12GMA - Unit 4 - Ch11 Terminology (Cambridge)

A graph that has no loops, multiple edges nor cycles.

• Tree

• Spanning Tree

• Prim's Algorithm

• Assignment Problem

A tree that connects all the vertices of a particular graph

• Assignment Problem

• Spanning Tree

• Minimum Spanning Tree

• Bipartite Graph

The spanning tree that has the smallest possible total weight for that graph

• Light Spanning Tree

• Maximal Spanning Tree

• Minimum Spanning Tree

• Optimal Spanning Tree

An algorithm used to determine the minimum spanning tree for a graph.

• Hungarian Algorithm

• Hamilton's Algorithm

• Katniss' Algorithm

• Prim's Algorithm

Problems where it is important to minimise the total weight of connections between objects or locations. The weights in connector problems can be length, time, cost or other physical quantity.

These problems are solved by finding the minimum spanning tree for the graph that represents the problem.

• Connector Problems

• Plot tension Problems

• Output problems

• Shortest Route problems.

Problems that involve matching the objects in one group to objects in another group, so that the overall cost in terms of time, money or other quantity is minimised.

These problems are solved with bipartite graphs and/or the Hungarian algorithm.

• Exam Problems

• Assignment Problems

• Matching problems

• 99 Problems

A graph where the vertices exist in separate groups. The edges of a bipartite graph connect vertices in one group with vertices in the other.

• Tree

• Eulerian Graph

• Hamiltonian Graph

• Bipartite Graph

A bipartite graph in which every vertex in one group of the bipartite graph is connected by an edge to every vertex in the other group

• Hungarian Algorithm

• Complete Bipartite Graph

• Minimum Spanning Tree

• Flow Graph

A table of weights for a complete bipartite graph. It contains the cost (eg. time, money, etc) of assigning objects from one group to objects in another.

• Cost Matrix

• Assignment Matrix

• Problem Table

• Adjacency Matrix

An algorithm that is used to determine the best allocation in an assignment problem that will minimise the total cost.

• The Swedish Algorithm

• The Hungarian Algorithm

• Prim's Algorithm

• Hamilton's Algorithm