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.
