Decision maths Flashcards
What is a bipartite Graph?
A graph whose vertices are divided into two distinct sets. All edges go from a vertex in one set to a vertex in the other set.
How do you denote a bipartite graph?
with M vertices in one set, and N vertices in the other set:
Km,n
What is a subgraph?
A graph whose graph vertices and graph edges form subsets of the graph vertices and graph edges of a given graph.
What is a subdivision of a graph?
A subdivision occurs when a new vertex is added on an edge so that the edge becomes two edges.
What is a loop?
An edge that starts and finishes and the same vertex
When do vertices have multiple edges?
When there is more than one edge that connects them
What type of graph has no loops and no multiple edges?
A SIMPLE graph
What type of graph has one or more edges that have an arrow to indicate that you can only go in one direction?
A digraph
What is a trail?
A trail is a sequence of edges in which the end of one edge ( except the last ) is the beginning of the next, and no edge is repeated
What is a cycle?
A cycle is a closed trail in which no vertex is repeated.
What is a hamiltonian cycle?
A cycle that visits every vertex only once
What is a tree?
A simple connected graph with no cycles
What is a graph that has numbers (weights) associated with the edges?
A network, (can also be presented as a graph)
What is Euler’s formula for connected Planar graphs?
v - e + f = 2
v = number of vertices e = edges f = number of faces
What makes a graph planar?
A graph is planar if it can be drawn in two dimensions without any edges crossing
What’s Kruskal’s algorithm?
- Select the shortest edge
- At each stage, select the next shortest edge that is not connected to the vertices that are already connected
What’s Prim’s algorithm?
- Select any vertex to start from
- Correct the nearest node that is not already connected
- Repeat until all nodes are connected
What are methods of finding the minimum spanning tree?
Prim’s and Kruskal’s algorithm
How do you find the lower bounds of a route ( Travelling Salesperson Problem)
- Remove a node
- Complete a minimum spanning tree for the remaining nodes
- Add the two shortest routes from the removed node back in
If this results in a tour, this is the optimal tour available
How do you find the upper bound of a route?
Travelling Salesperson Problem
- Choose an arbitary starting node
- Add in the smallest arc to this node that is not yet in the tour
- Repeat until all nodes are in the tour
- Add an arc back to the start node ( shortest )
How do you convert a classical problem to a practical problem?
Add on arcs between points that aren’t connected
What is the route inspection algorithm?
- Find the total weight of the network
- Identify the odd vertices
- Pair the odd vertices, and add up the pairs to find the smallest selection
- Add this to the total weight of the network
