Graphs/Connectivity

Notes

Finding Connected Components

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

Undirected Graphs: Finding Connected Components

The result of finding connected components is a forest (a group of trees). To find the connected components, we perform a depth-first search, adding each discovered node to a dictionary. We want to iterate through every vertex on the graph. We perform a depth-first search on a random vertex. We then move on to the next vertex, and if it is not already a part of an existing forest, we perform another depth-first search on it.

This procedure will run in $ O(n+m) $ time, because even if we perform multiple depth-first searches, we are only performing it on separate trees.

// u is an empty dictionary
def dfs_connected(g):
    forest is empty dictionary
    for each vertex u in graph:
        if u not in forest:
            forest[u] = None
            do_dfs(g, u, forest)
    return forest

// complementary method: do depth first search
def do_dfs(g, u, discovered):
    for e in g.incident_edges(u):
        if v not in discovered:
            discovered[v] = e
            do_dfs(g, v, discovered)

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