D1 Flashcards
Simple graph
No loops or multiple arcs
Connected graph
All pairs of nodes are connected
Complete graph
All nodes connected by one arc to every other node (Kn = complete with n nodes)
Planar graph
Can be drawn in a plane, so that arcs only meet at nodes and don’t cross
Isomorphic graphs
Same nodes and arcs but different shapes
Trail
End node of an arc is the start node of the next
Path
No node used more than once
Cycle
Closed trail where only the first and last nodes are the same
Tree
Simple graph without cycles
Spanning tree equation for arcs
n nodes
= n-1 arcs
Euclerian
Closed trail
Every arc once
Every node has even order
Semi-Eulerian
Not closed
Every arc once
Only 2 nodes have odd order
Hamiltonian cycle
Passes every node of the graph once and returns to its starting node
Kruskal’s Algorithm
- Sort arcs into ascending order of weight
- Select least weight arc
- Select next lowest that doesn’t form cycle with anything
- Repeat until you have a spanning tree
Prim’s Algorithm
- Choose starting node
- Attach to arc of least weight
- Look at other nodes that aren’t in the tree and connect with minimum arc length to a node that’s in the tree
- Repeat until all nodes in the tree
Dijkstras Algorithm
Temporarily label each node with distances from starting node and choose lowest value
- start node labelled zero
Chinese postman Algorithm
-assuming it’s not eulerian
1-find all odd nodes
2-for each pair of odd nodes, find the connecting path of minimum weight
3-Consider all ways of pairing odd nodes and select one with minimum total weight
4-duplicate paths selected in step 3
5-find closed trail containing every arc for the new network
Chinese postman pairings
2 odd nodes = 1 pairing
4 odd nodes = 3 pairings
6 odd nodes = 15 pairings
Nearest neighbour
- choose starting
- pick min weight arc attached to it
- repeat until all nodes chosen
- add arc that joins last chosen node to first
Lower bound Algorithm
Choose a node and find total of two smallest weights incident
Ignore the node and selected arcs and find total weight of minimum connector for this network
Sum of both = estimate
Upper bound
Nearest neighbor
First fit
Each object put in first available place
First fit decreasing
Arrange in decreasing size and then use first fit
Shuttle sort
Look at 1/2
Look at 2/3
Look at 3/4…….
Swap when necessary
If you’re swapping 5/6 and it’s smaller than all the others, keep moving it down the line to correct place
