Graphs 2 cs320

What is a directed graph?

A graph where edges have direction, from node u to node v.

What does it mean for a graph to be strongly connected?

Every node is reachable from every other node and vice versa.

How can you test for strong connectivity in a directed graph?

Run BFS from a node in both the graph and its reverse; all nodes must be reachable both ways.

What is a Directed Acyclic Graph (DAG)?

A directed graph with no cycles.

What is a topological ordering?

An ordering of nodes such that for each edge (u, v), u comes before v.

Does every DAG have a topological ordering?

Yes.

What is the time complexity of topological sorting?

O(m + n)

What does the cut property in MSTs state?

The minimum-cost edge crossing any cut must be part of the MST.

What is Kruskal's algorithm?

A greedy algorithm that adds edges in increasing order of weight unless it forms a cycle.

What is Prim's algorithm?

A greedy algorithm that grows the MST by repeatedly adding the cheapest edge from explored to unexplored nodes.

What is a minimum spanning tree (MST)?

A subset of edges that connects all vertices with minimum total weight and no cycles.

Why must the MST be a tree?

It connects all nodes and contains no cycles.

What does Cayley’s formula state?

There are n^(n-2) spanning trees in a complete graph with n nodes.

What data structure is used in Kruskal’s algorithm?

Union-Find (Disjoint Set Union)

What is the running time of Kruskal’s algorithm?

O(m log n)

What is the cut property used for in Prim’s algorithm?

It ensures that the algorithm adds the correct edges to form the MST.

What is the purpose of lexicographic tie-breaking in MST algorithms?

To handle equal-weight edges without ambiguity.

What is single-linkage clustering?

A greedy clustering method using edge distances, effectively Kruskal’s algorithm stopped at k clusters.

How does single-linkage clustering relate to MSTs?

It builds the MST and removes the k-1 largest edges to form k clusters.

What is spacing in clustering?

The minimum distance between any two objects in different clusters.

What is k-clustering of maximum spacing?

A clustering that maximizes the minimum distance between clusters.

How is the MST used in clustering?

To find k clusters by removing the k-1 most expensive edges.

How does the MST help in gene mapping?

It clusters genes by minimizing recombination distances, revealing chromosome structures.