Graphs Flashcards
Graph
A set of vertices connected pairwise by edges.
Path
A sequence of vertices connected by edges.
Cycle
Path whose first and last vertices are the same.
Connected vertices
Two vertices are connected if there is a path between them.
Euler Tour
A cycle that uses each edge exactly once.
Hamilton tour
A cycle that uses each vertex exactly once.
Planar Graph
A graph that can be embedded in the plane.
I.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
I.e. it can be drawn in such a way that no edges cross each other.
Isomorphic Graphs
When two adjacency lists represent the same graph.
Sparse graphs
Graphs that have a huge number of vertices, but a small average vertex degree.
Describe
the Depth-first Search algorithm
DFS (to visit a vertex v)
- Mark v as visited.
- Recursively visit all unmarked vertices w adjacent to v.
2 Applications of Depth-first search
- Find all vertices connected to a given source vertex.
- Find a path between two vertices.
Describe
the Breadth-first Search algorithm
BFS (from a source vertex s)
Put s on a FIFO queue, and mark s as visited.
Repeat until the queue is empty:
- Remove the last recently added vertex v.
- add each of v’s unvisited neighbours to the queue, and mark them as visited.
Define
vertex connectivity
Vertices v and w are connected if there is a path between them.
Digraph
Directed graph.
A set of vertices connected pairwise by directed edges.
Strongly connected vertices
Vertices v and w are strongly connected if there is both a directe path from v to w and a directed path from w to v.
Key property of strong vertex connectivity
Strong connectivity is an equivalence relation
- v is strongly connected to v.
- If v is strongly connected to w, then w is strongly connected to v.
- If v is strongly connected to w and w to x, then v is strongly connected to x.
Tree
A graph that is both connected and acyclic.
Minimum spanning tree
Given an undirected graph G with positive edge weights (connected).
A spanning tree of G is a subgraph T that is both a tree (connected & acyclic) and spanning (includes all of the vertices).
Define
a Cut
A cut in a graph is a partition of its vertices into two (nonempty) sets.
Define
a Crossing edge
A crossing edge connects a vertex in one set with a vertex in the other.
Define
Cut property
Given any cut, the crossing edge of minimum weight is in the minimum spanning tree.
Describe
a proof for the cut property
Suppose the min-weight crossing edge e is not in the MST.
- Adding e to the MST creates a cycle.
- Some other edge f in the cycle must be a crossing edge.
- Removing f and adding e is also a spanning tree.
- Since the weight of e is less than the weight of f, that spanning tree is lower weight.
- Thus we have a proof by contradiction.
Describe
a Greedy algorithm to find a Minimum Spanning Tree
Def: Grey edges are not in the MST. Black ones are.
Start with all edges coloured grey.
Find a cut with no black crossing edges, and color its minimum-weight edge black.
Repeat until V-1 edges are coloured black.
(V being the number of vertices in the graph)
Describe
Kruskal’s algorithm
to find the Minimum Spanning Tree
Sort edges in ascending order of weight.
Iterate through the edges:
- Add the next edge to tree T, unless doing so would create a cycle.
What is the running time of Kruskal’s algorithm?
E log E
E being the number of edges in the graph
Describe
Prim’s algorithm
to find the Minimum Spanning Tree
- Start with vertex 0 and greedily grow tree T.
- Add to T the min weight edge with exactly one endpoint in T.
- Repeat until V - 1 edges.
Describe
Dijkstra’s algorithm
to find the shortest path to any vertex
Consider connected vertices in increasing order of distance from the source vertex s (non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
Define
st-cut
A partition of the vertices into two disjoint sets, with s in one set A and t in the other set B.
Define
the capacity of an st-cut
The sum of the capacities of the edges from A to B.
Define
The net flow across a cut (A,B)
The sum of the flows on its edges from A to B minus the sum of the flows on its edges from B to A.
Augmenting path theorem
A flow f is a maxflow iff there are no augmenting paths.
Maxflow-mincut theorem
The value of the maxflow is equal to the capacity of the mincut.
3 Equivalent conditions for any flow f
- There exists a cut whose capacity equals the value of the flow f.
- f is a maxflow.
- There is no augmenting path with respect to f.
Ford-Fulkerson Algorithm
Start with 0 flow.
While there exists an augmenting path:
- find an augmenting path
- compute bottleneck capacity
- increase flow on that path by bottleneck capacity
