Graphs/Connectivity

Notes

Finding Connected Components

To find all connected components on a graph, we have to consider directed and undirected components separately.

Directed Graphs: Finding Strongly Connected Components

A strongly connected directed graph is one in which, for every pair of vertices u and v, u can be reached from v and v can be reached from u.

One (slow) way to do this is to call a DFS from each vertex independently. Since DFS runs in $ O(n+m) $ time, and we run it on all n nodes, this approach runs in $ O(n(n+m)) $

Another (faster) way to do this is to run a "normal" DFS, followed by running a "backwards" DFS. In practice, this can be accomplished by either creating a copy of the graph with all the edges reversed, or creating a "reverse" opposite method (where we pass a vertex and an edge, and get the opposite vertex).

Using this approach requires us to run two DFS searches (one forward, one reverse). Since DFS runs in $ O(n+m) $ time, running two DFS runs in $ O(n+m) $

Dietel Chapter 3: Connectivity

A better/more helpful definition of connectivity: "a graph is k-connected if any two of its vertices can be joined by k independent paths."

Outline:

• Structure of 2-connected graphs
• Structure of 3-connected graphs
• Menger theorem - states that the definition given above, and the definition saying we need at least k vertices to disconnect a k-connected graph, are in fact equivalent.
• Number of H-paths in a given subgraph H
• Number of edge-disjoint spanning trees
• Existence of disjoint paths linking several given pairs of vertices

2-connected graphs and subgraphs:

• Blocks, analogues of components (maximal connected subgraphs of a graph)
• Proposition: a graph is 2-connected if and only if it can be constructed from a cycle by successively adding H paths to graphs H already constructed.

3-connected graphs and subgraphs:

• Lemma: if G is 3-connected and cardinality of G is larger than 4, then G has an edge such that G without e is again 3-connected.
• Theorem: a graph G is 3-connected if and only if there exists a sequence G0 to Gn of graphs with the two properties that... G0 has cardinality 4, and Gn = G
• Theorem above is essential part of Tutte's wheel theorem (Graphs of the form $ C^n * K^1 $ are called wheels, so $ K^4 $ is the smallest wheel.)
• The cycle space of 3-connected graph is generated by non-separating induced cycles
• We call C a fundamental triangle if it is an induced cycle C on the graph and if $ C = C^3 $
• Every fundamental triangle is a basic cycle in G.

Menger's Theorem:

• Theorem: Let $ G = (V,E) $ be a graph and $ A, B \subseteq V $.. Then the maximum number of vertices separating A from B in G is equal to the maximum number of disjoint A-B paths in G.
• Global version:
  • A graph is k-connected if and only if it contains k independent paths between any two vertices.
  • A graph is k-edge-connected if and only if it contains k edge-disjoint paths between any two vertices.

Mader's Theorem:

• An analogy to Menger's theorem; we ask, given a graph G with an induced subgraph H, how many independent H-paths can we find in G?
• Theorem: Given a graph G with an induced subgraph H, there are always $ M_G(H) $ independent H-paths in G, where $ M_G(H) $ denotes the upper bound on the minimum number of H-paths in G.

(Again with the deluge of specialized, one-off notation.)

Edge disjoint spanning trees:

• Theorem: a multigraph contains k edge-disjoint spanning trees if and only if for every partition P of its vertex set it has at least $ k(|P|-1) $ cross-edges.
• To ensure the existence of k edge-disjoint spanning trees, it suffices to raise the edge-connectivity to 2k.
• Every 2k-edge-connected multigraph G has k edge-disjoint spanning trees.

Paths between given pairs of vertices:

• Graph with at least 2k vertices is k-linked if each 2k distinct vertices contain k disjoint paths.
• Not just asking for k disjoint paths between two sets of vertices: we are insisting these paths also link specified pairs of end vertices.
• Condition of being k-linked is much stronger than being k-connected

(Not even going to try to slog through the rest of this chapter.)