Decision revision
Subdecks (2)
Cards (29)
- a walk is a route along edges from one vertex to the next
- a path is a walk in which no vertex is visited more than once
- a trail is a walk in which no edge is visited more than once
- a cycle is a walk in which the start and end vertex is the same and no vertex is visited more than once
- a Hamiltonian cycle is a cycle that includes every vertex
- the first-fit algorithm is done by
- Take the items in the order given
- Place items in the first available bins
- the first-fit decreasing algorithm is done by
- sort the items into descending order
- apply first-fit algorithm
- the full-bin algorithm is done by
- use combinations to fill bins
- apply first-fit algorithm
- in an undirected graph the sum of the degrees of vertices is equal to 2 times the number of edges as a consequence the number of odd vertices must be even. This is the handshaking lemma
- an isomorphic graph is a graph that shows the same information drawn differently
- how to carry out kruskals
- order arcs into ascending order of weight
- select arc of least weight to start
- if no cycle accept
- if cycle reject
- repeat
- how to carry out prims
- choose any vertex to start the tree
- select arc of least weight to join vertex
- repeat
- an eulerian graph is a trail that includes every edge and starts and finishes at the same vertex, all the vertices are even
- a semi-eularian graph is a trail that includes every edge but starts and finishes at different vertices, two odd vertices
- to carry out route inspection
- identify any vertices with an odd degree
- consider all possible pairings
- select pairings with the least sum
- add a repeated arc between both pairs
- how to formulate a linear programming problem
- define decision variables
- state objective
- write constraints as inequalities
- on a linear programming graph the unshaded area is the feasible region
- to find solutions with integer values test the last integer solution by the objective line then test the objective