Chapter 12 - Graphs and Networks 1 Flashcards
(*deep inhale*) Graphs and Networks, Traversals, Kruskal's and Prim's Algorithms, The route inspection and travelling salesman problems and Network Flows (*exhales*) this chapter is a huge tour...
Define a Graph, Vertex, Face and Edge.
- A Graph is a diagram involving a set of points and interconnecting lines.
- A Vertex is a point on a Graph.
- An Edge is a line joining two points.
- A Face is a region within the edges of a graph, including the singular region outside of it.
Define a complete graph?
A complete graph is a graph that has an edge connecting all possible pairs of vertices. The notation is Kₙ.
Define a complete bipartite graph?
A complete bipartite graph connects m vertices to n vertices. The notation is Kₙٖₘ
Define a degree in graph theory, and what is the relationship between the degrees and edges?
A degree in graph theory is defined as the number of connections each edge has. The total number of degrees is equal to 2 times the number of edges.
Define a Planar Graph.
A planar graph is a graph that can be embedded in the plane, in such a way that its edges only intersect at their endpoints. (no intersecting edges.)
What is Euler’s Formula for Planar Graphs?
Euler’s Formula, applicable for finite, connected, planar graphs:
v + f - e = 2.
Vertices + Faces - Edges (including infinite outside face) = 2
What are the two relationships connecting edges and graphs?
For a simple, connected, planar graph:
e ≤3v - 6 AND At least three edges, and every edge touches at most two faces.
2e ≥ 3f AND More than one edge.
State the triangle inequality.
The triangle inequality in Graph Theory:
AB + BC ≥ AC, where AC is the hypotenuse.
What is a walk traversal?
A walk traversal is a continuous journey across a graph with no restrictions on repeating edges or vertices.
What is a trail traversal? Therefore, what is a closed trail?
A trail traversal is a continuous journey across a graph that has no repeated edges. If it returns to the starting vertex, it is a closed trail.
What is a path traversal? Therefore, what is a cycle?
A path traversal is a continuous journey across a graph which has no repeated edges OR vertices. If you return to the start vertex, this is called a cycle.
What is a Hamiltonian Cycle?
A cycle which visits every vertex once and only once is called a Hamiltonian Cycle.
State the steps of Kruskal’s Algorithm.
Kruskal’s Algorithm:
Step 1: Choose the arc with minimum weight.
Step 2: Choose the arc with the least weight from the remaining arcs, avoiding those already chosen.
Step 3: If any nodes remain unconnected, go to Step 2.
State the steps of Prim’s Algorithm (on a graph).
Prim’s Algorithm:
Step 1: Choose any node to be the first the connected set.
Step 2: Choose the arc of minimum weight joining a connected node to an unconnected node. Add this arc to the spanning tree and the node to the connected set.
Step 3: If any unconnected nodes remain, go to Step 2.
State the steps of Prim’s Algorithm (on a graph).
Prim’s Algorithm (on a matrix):
Step 1: Select the first node.
Step 2: Cross out the row and number the column for the chosen node.
Step 3: Find the minimum undeleted weight in the numbered columns. Circle this value. The node for this row is the next chosen node.
Step 4: Repeat steps 2 and 3 until all nodes have been chosen.
State the steps for the Route Inspection Algorithm.
Route Inspection Algorithm:
Step 1: Identify all the odd nodes.
Step 2: List all the possible pairings of the odd nodes.
Step 3: For each pairing find the shortest routes between paired nodes and the total weight of those routes.
Step 4: Choose the pairing with the smallest total.
Step 5: Repeat the shortest route arcs (equivalent to adding extra arcs to the network). The network is now traversable.
Name the characteristic of the Route Inspection Algorithm to do with the frequency it passes through a node.
The inspection route passes 1/2n times through a node of degree n.
Define the travelling salesman problem.
The travelling salesman problem tries to find a route that visits every node of a network and returns to the start in the shortest possible distance.
How do you solve a travelling salesman problem?
To a solve a practical travelling salesman problem with n nodes:
- Create a complete network, Kₙ, of shortest distances between pairs of nodes.
- Find a minimum weight Hamiltonian cycle for the complete network (this is the classical problem).
- Interpret the solution in the practical situation.
Describe the relationship between nodes and possible tours. (TSP)
A network with n nodes has 1/2(n-1)! possible tours.
State the steps for the nearest neighbour algorithm. (TSP)
The nearest neighbour algorithm:
Step 1: Choose a starting node, V.
Step 2: From your current position, choose the arc with minimum weight leading to an unvisited node. Travel to that node.
Step 3: If there are unvisited nodes, go to Step 2.
Step 4: Travel back to V.
Describe how you determine whether a solution, T, is optimal? (TSP)
For a solution T, to determine an optimal value, you find two values:
Lower Bound ≤T≤Upper Bound.
What is true for any tour? (TSP)
The length of any known tour is an upper bound for a solution.
Describe the relationship between minimum spanning trees and upper bounds for a solution. (TSP)
(2 x length of the minimum spanning tree) is an upper bound.
How do you find a lower bound for a TSP?
To find a lower bound:
Step 1: Choose a node V.
Step 2: Identify the two lowest weights, p and q, of the arcs connected to V.
Step 3: Remove V and its connecting arcs from the network. Find the total weight, m, of the minimum spanning tree of the remaining subgraph.
Step 4: Calculate lower bound = p + q + m.
Step 5: If possible, choose another node V and go to Step 2.
Step 6: Choose the largest result obtained as the best lower bound.
Step 7: If you find a lower bound which forms a tour, then that tour is the optimal solution. If none of the possible lower bounds form a tour, the optimal tour must be greater than the best lower bound.
Define the feasibility condition.
The feasibility condition states that the flow in an arc cannot be greater than its capacity.
Define the conservation condition.
The conservation condition states that, at every node apart from S source and T sink, total inflow = total outflow.
And:
Total outflow from S source = total inflow to T sink.
What is the capacity of a cut, in network flows?
The capacity of a cut is the sum of the capacities of those arcs of the cut which are directed from X to Y.
You describe a cut either by listing the set of arcs in the cut (the cut set) or by listing the nodes in the source set X, and the sink set Y.
What is the value of the flow in a cut, in network flows?
The value of any flow is less than or equal to the capacity of any cut.
State the maximum flow-minimum cut theorem.
The maximum. flow-minimum cut theorem states that the value of the maximal flow is equal to the capacity of a minimum cut.
