Graphs

Question 1

Graph

Answer 1

A set of vertices connected pairwise by edges.

Question 2

Path

Answer 2

A sequence of vertices connected by edges.

Question 3

Cycle

Answer 3

Path whose first and last vertices are the same.

Question 4

Connected vertices

Answer 4

Two vertices are connected if there is a path between them.

Question 5

Euler Tour

Answer 5

A cycle that uses each edge exactly once.

Question 6

Hamilton tour

Answer 6

A cycle that uses each vertex exactly once.

Question 7

Planar Graph

Answer 7

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.

Question 8

Isomorphic Graphs

Answer 8

When two adjacency lists represent the same graph.

Question 9

Sparse graphs

Answer 9

Graphs that have a huge number of vertices, but a small average vertex degree.

Question 10

Describe

the Depth-first Search algorithm

Answer 10

DFS (to visit a vertex v)

• Mark v as visited.
• Recursively visit all unmarked vertices w adjacent to v.

Question 11

2 Applications of Depth-first search

Answer 11

• Find all vertices connected to a given source vertex.
• Find a path between two vertices.

Question 12

Describe

the Breadth-first Search algorithm

Answer 12

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.

Question 13

Define

vertex connectivity

Answer 13

Vertices v and w are connected if there is a path between them.

Question 14

Digraph

Answer 14

Directed graph.

A set of vertices connected pairwise by directed edges.

Question 15

Strongly connected vertices

Answer 15

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.

Question 16

Key property of strong vertex connectivity

Answer 16

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.

Question 17

Tree

Answer 17

A graph that is both connected and acyclic.

Question 18

Minimum spanning tree

Answer 18

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).

Question 19

Define

a Cut

Answer 19

A cut in a graph is a partition of its vertices into two (nonempty) sets.

Question 20

Define

a Crossing edge

Answer 20

A crossing edge connects a vertex in one set with a vertex in the other.

Question 21

Define

Cut property

Answer 21

Given any cut, the crossing edge of minimum weight is in the minimum spanning tree.

Question 22

Describe

a proof for the cut property

Answer 22

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.

Question 23

Describe

a Greedy algorithm to find a Minimum Spanning Tree

Answer 23

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)

Question 24

Describe

Kruskal’s algorithm

to find the Minimum Spanning Tree

Answer 24

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.

Question 25

What is the running time of Kruskal’s algorithm?

Answer 25

E log E

E being the number of edges in the graph

Question 26

Describe

Prim’s algorithm

to find the Minimum Spanning Tree

Answer 26

• 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.

Question 27

Describe

Dijkstra’s algorithm

to find the shortest path to any vertex

Answer 27

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.

Question 28

Define

st-cut

Answer 28

A partition of the vertices into two disjoint sets, with s in one set A and t in the other set B.

Question 29

Define

the capacity of an st-cut

Answer 29

The sum of the capacities of the edges from A to B.

Question 30

Define

The net flow across a cut (A,B)

Answer 30

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.

Question 31

Augmenting path theorem

Answer 31

A flow f is a maxflow iff there are no augmenting paths.

Question 32

Maxflow-mincut theorem

Answer 32

The value of the maxflow is equal to the capacity of the mincut.

Question 33

3 Equivalent conditions for any flow f

Answer 33

• 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.

Question 34

Ford-Fulkerson Algorithm

Answer 34

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