Graph Theory Flashcards
Simple Graph Definition
A graph with no loops of multiple edges.
Complete Graph Defintion
A graph where every vertex is connected to every other vertex.
How many edges does a complete graph of Kn nodes have?
1/2n(n-1)
Bipartite Graphs
- A graph where the nodes are in two distinct sets
- Every edge connects a member of the first set to a member of the second set
- Vertices cannot be connected to nodes in the same set.
Connected Graph
A graph in which it is possible to go from any vertex to any other vertex (even if you have to travel through other vertices).
Degree/Order Of A Vertex
How many ends of edges there are at the vertex (how many lines go in/out of the vertex).
What does an odd total order look like?
It is not possible to draw a graph with an odd total order.
Kn Meaning
This represents a complete graph with n vertices.
How many arcs in Kn
n (n-1) / 2
Digraph Defintion
- A diagraph (directed graph) is one in which at least one edge has a direction associated with it.
- Normally has a source (original node in which all preceding arcs come from).
- Normally has an end node, called the sink, which all arcs eventually reach.
Kr,s Meaning
This represents a complete bipartite graph, where r is the number of nodes on the left, and s on the right.
Tree Defintion
A simply connected graph with the minimum number of arcs is called a tree, and with no cycles e.g triangle/square.
Network
A graph that has weights attached.
Minimum Spanning Tree
A tree that joins all vertices in a graph (as a tree) in the cheapest possible way.
Eularian Graph
- It is possible to make a trail that uses all edges once, starting and ending at the same vertex.
- Has no nodes with odd degree.
Semi-Eularian Graph
- It is possible to make a trail that uses all the edges once, starting and ending at different vertices.
- Have exactly two odd nodes, possible to make a trail if you start at one odd vertex and finish at the other.
Trail Definition
A trail is a sequence of joined up edges such that no edge comes one after another, e.g. AEBCED.
Path Definition
A path is a sequence of edges such that the end vertex on one edge is the start of the next, and in which no vertex is visited more than once (except that the first and the last may be the same), e.g. ABECD
Cycle Defintion
A cycle is a closed path, e.g. ABEA
A simply connected graph, G, has 8 vertices. What is the minimum/maximum number of edges that G could have?
Min = n - 1 = 7
Max = (n x (n-1)) / 2
8 x 7 / 2 = 56/2 = 28
What is a greedy algorithm?
A greedy algorithm is an algorithm that finds a solution to problems in the shortest time possible.
Outline how Kruskal’s Algorithm works (Minimum Spanning Tree)
1) Select the shortest edge in a network
2) Select the next shortest edge
3) Repeat this process until all vertices are connected.
4) Make sure you do not create a cycle at any point, or it is not a tree.
Outline how Prim’s Algorithm works (Minimum Spanning Tree)
1) From the starting vertex, select the shortest edge connected to that vertex.
2) Selected the shortest edge connected to all vertices already connected.
3) Repeat until all vertices are connected.
Dijkstra’s Algorithm
- Start with first node, make number = 1, final value = 0
- Add the running value in all connected nodes.
- Then take the node with the smallest running value, then we know that’s the final value.
- From that node see what you can go to (smallest weight), then others.
- Once you have exhausted a vertex, go to the next smallest working value.
What are the defining characteristics of a critical activity?
- The early and late event time at the start and end of the activity are the same.
- E.g. 3 3 and 8 8
Algorithm Definition
- An algorithm is a set of instructions
- It must have a finite number of steps
- It must work for any input
- It must have an end
What do the different shapes mean in a flowchart?
- Long ovals (rectangles with curved edges) indicate the start of end of process
- Diamonds contain questions (decisions).
- Rectangle contains a process/instruction.
Efficiency of an algorithm
- Measure of the ‘run-time’ of an algorithm and in most cases is proportional to the number of operations that must be carried out.
Size of a problem
- A measure of its complexity and so in the case of sorting algorithm the number of elements in the list.
Complexity of an algorithm
- A measure of its efficiency as a function of the size of the problem.
- We refer to the order of the algorithm to give an indication of its complexity.
Full Bin Packing Strategy
- It is a strategy and not an algorithm because it is not deterministic.
- Using common sense sort boxes into bins yourself.
First Fit + First Fit Decreasing
- Come as they serve bin packing, decreasing is just when you order the list from largest to smallest beforehand.
Heuristic Algorithms + Examples
- An algorithm that will find a good solution.
- Although it may not necessarily find an optimal solution, not to say it’s impossible, just not guaranteed.
- Both first fit and first fit decreasing algorithms fall under this category.
Bubble Sort Complexity
- Quadratic
Order for calculating the run time of an algorithm, given the complexity and times taken.
(New N / Old N) ^ Power of Complexity x Old Time = New Time
e.g. n^2, n=200, 0.03s, now n = 20000
(20,000/200)^2 x 0.03 = 300 seconds
Total Float of a path
-The maximum time that the activity can be delayed without delaying the entire project.
- Total Float = Late Finish Time - Early Start Time - Duration
1 4 —>—- 6 8 A(2)
8 - 1 - 2 = 5
Independent Float
- The amount of time an activity can be delayed without affecting any subsequent activities, assuming all previous activities finish as late as possible.
- Independent Float = Earliest Start Time of next activity − Latest Finish Time of previous activity − Duration
- If negative, make it zero.
1 4 —>—- 6 8 A(2)
8 - 1 - 2 = 5
6 - 4 - 2 = 0
Interfering Float
- The portion of the total float that, if used, will delay subsequent activities but not delay the overall project. It measures how much an activity can be delayed without affecting the total project duration, while still affecting the float of dependent activities.
- Interfering Float = Total Float − Independent Float
Gantt Chart
- Graph used to show flow in a network.
- Critical path/paths go in a row at the bottom.
- If two activates are right next to each other they are critical.
- For all others activities, draw them starting on the least time and then add the duration, then account for the latest time of the next activity by adding a dash lined extension at the end.
- Y axis is nothing, X axis is time (0 to latest possible time).
Number of arcs in complete graph
n(n-1) / 2
Minimum number of arcs in simply connected graph
n-1
Recourse Histogram
- It’s for describing how many workers are working on a problem at once, because ideally you want as little workers as possible.
- Y axis = no of workers, X is time (0 to latest possible time).
- Draw in critical path at bottom.
- Draw in rest (assuming they start earliest possible time), and draw extend empty box till the end of the row, and shade regions.
What type of complexity is first fit and first fit decreasing bin packing?
- O(n^2)
- 1/2n (n-1) is the number of comparisons made.
In a network flow, what is the start and end node called?
- The source
- The sink
Total number of comparisons required for a list with n elements
1/2 n (n-1)
Simplex Method, slack variables
- Take an equation that has <=
- If it’s less than or equal to, add a slack variable to make it an equation.
Non-Basic and Basic Variable
- The point where two variables intersect.
- At intersections, two variables will be non-basic, the rest will be basic.
- Non 1s and 0s
How to draw initial tableau
- Take each constraint, and if needed, turn into into the form X + Y <= P
- As in, it must have a less than or equal to.
- Then convert it into an equation using slack variables.
- Make the objective function from P = x + ky to P - x - ky = 0
- Fill in with the P at the top.
What to do after getting initial tableau
- Choose a pivot, and choose the most negative number. That becomes the pivot column.
- Divide RHS by each value in the pivot column (ignore negative numbers & zero)
- The lowest result corresponds to value in pivot column, its now pivot value.
First iteration of simplex
- Now that you have equation 1, 2, 3, work out equation 4, 5, 6
- Divide equation 2 by the pivot value in order
How tro do dik stra without graph
- Draw column for all nodes like A - H
