Graphs/Connectivity - Revision history

Admin: /* Undirected Graphs: Finding Connected Components */

2017-10-17T05:40:14Z

Undirected Graphs: Finding Connected Components

← Older revision		Revision as of 05:40, 17 October 2017
Line 18:		Line 18:
	if u not in forest:		if u not in forest:
	forest[u] = None		forest[u] = None
	~~DFS~~(g, u, forest)		do_dfs(g, u, forest)
	return 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)
	</pre>		</pre>

Admin: /* Undirected Graphs: Finding Connected Components */

2017-09-10T13:33:44Z

Undirected Graphs: Finding Connected Components

← Older revision		Revision as of 13:33, 10 September 2017
Line 9:		Line 9:
	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.		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 ~~procedrue~~ will run in <math>O(n+m)</math> time, because even if we perform multiple depth-first searches, we are only performing it on separate trees.		This procedure will run in <math>O(n+m)</math> time, because even if we perform multiple depth-first searches, we are only performing it on separate trees.

	<pre>		<pre>

Admin: /* Dietel Chapter 3: Connectivity */

2017-09-10T13:33:18Z

Dietel Chapter 3: Connectivity

← Older revision		Revision as of 13:33, 10 September 2017
Line 34:		Line 34:
	Using this approach requires us to run two DFS searches (one forward, one reverse). Since DFS runs in <math>O(n+m)</math> time, running two DFS runs in <math>O(n+m)</math>		Using this approach requires us to run two DFS searches (one forward, one reverse). Since DFS runs in <math>O(n+m)</math> time, running two DFS runs in <math>O(n+m)</math>

	==Dietel Chapter 3: Connectivity==		=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."		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."
Line 46:		Line 46:
	* Existence of disjoint paths linking several given pairs of vertices		* Existence of disjoint paths linking several given pairs of vertices

	2-connected graphs and subgraphs:		==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:		Blocks, analogues of components (maximal connected subgraphs of a graph)
	* 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 <math>C^n * K^1</math> are called wheels, so <math>K^4</math> 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 <math>C = C^3</math>
	* Every fundamental triangle is a basic cycle in G.

	~~Menger's Theorem~~:		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.
	* Theorem: Let <math>G = (V,E)</math> be a graph ~~and <math>A, B \subseteq V</math>.. 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:		==3-connected graphs and subgraphs==
	* 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 <math>M_G(H)</math> independent H-paths in G, where <math>M_G(H)</math> denotes the upper bound on the minimum number of H-paths in G.		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 <math>C^n * K^1</math> are called wheels, so <math>K^4</math> 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 <math>C = C^3</math>

			Every fundamental triangle is a basic cycle in G.

			==Menger's Theorem==

			Theorem: Let <math>G = (V,E)</math> be a graph and <math>A, B \subseteq V</math>.. 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 <math>M_G(H)</math> independent H-paths in G, where <math>M_G(H)</math> denotes the upper bound on the minimum number of H-paths in G.

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

	Edge disjoint spanning trees:		==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 <math>k(\|P\|-1)</math> cross-edges.
	* To ensure the existence of k edge-disjoint spanning trees, it suffices to raise the edge-connectivity to 2k.		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 <math>k(\|P\|-1)</math> cross-edges.
	* Every 2k-edge-connected multigraph G has k edge-disjoint spanning trees.
			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:		Paths between given pairs of vertices:

Admin: /* Undirected Graphs: Finding Connected Components */

2017-09-09T10:33:10Z

Undirected Graphs: Finding Connected Components

← Older revision		Revision as of 10:33, 9 September 2017
Line 19:		Line 19:
	forest[u] = None		forest[u] = None
	DFS(g, u, forest)		DFS(g, u, forest)
			return forest
	</pre>		</pre>

Admin: /* Undirected Graphs: Finding Connected Components */

2017-09-09T10:32:48Z

Undirected Graphs: Finding Connected Components

← Older revision		Revision as of 10:32, 9 September 2017
Line 10:		Line 10:

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

			<pre>
			// 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
			DFS(g, u, forest)
			</pre>

	===Directed Graphs: Finding Strongly Connected Components===		===Directed Graphs: Finding Strongly Connected Components===

Admin: /* Undirected Graphs: Finding Connected Components */

2017-09-09T10:30:33Z

Undirected Graphs: Finding Connected Components

← Older revision		Revision as of 10:30, 9 September 2017
Line 7:		Line 7:
	===Undirected Graphs: Finding Connected Components===		===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 procedrue will run in <math>O(n+m)</math> time, because even if we perform multiple depth-first searches, we are only performing it on separate trees.

	===Directed Graphs: Finding Strongly Connected Components===		===Directed Graphs: Finding Strongly Connected Components===

Admin: /* Directed Graphs: Finding Strongly Connected Components */

2017-09-09T09:54:01Z

Directed Graphs: Finding Strongly Connected Components

← Older revision		Revision as of 09:54, 9 September 2017
Line 13:		Line 13:
	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.		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 <math>O(n+m)</math> time, and we run it on all n nodes, this approach runs in <math>O(n(n+m))</math>		One (slow) way to do this is to call a DFS from each vertex independently.

			Since DFS runs in <math>O(n+m)</math> time, and we run it on all n nodes, this approach runs in <math>O(n(n+m))</math>

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

Admin: /* Directed Graphs: Finding Strongly Connected Components */

2017-09-09T09:53:40Z

Directed Graphs: Finding Strongly Connected Components

← Older revision		Revision as of 09:53, 9 September 2017
Line 13:		Line 13:
	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.		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. ~~This~~ runs in <math>O(n(n+m))</math>		One (slow) way to do this is to call a DFS from each vertex independently. Since DFS runs in <math>O(n+m)</math> time, and we run it on all n nodes, this approach runs in <math>O(n(n+m))</math>

	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).		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).		Using this approach requires us to run two DFS searches (one forward, one reverse). Since DFS runs in <math>O(n+m)</math> time, running two DFS runs in <math>O(n+m)</math>

	==Dietel Chapter 3: Connectivity==		==Dietel Chapter 3: Connectivity==

Admin: /* Directed Graphs: Finding Strongly Connected Components */

2017-09-09T09:52:46Z

Directed Graphs: Finding Strongly Connected Components

← Older revision		Revision as of 09:52, 9 September 2017
Line 15:		Line 15:
	One (slow) way to do this is to call a DFS from each vertex independently. This runs in <math>O(n(n+m))</math>		One (slow) way to do this is to call a DFS from each vertex independently. This runs in <math>O(n(n+m))</math>

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

	==Dietel Chapter 3: Connectivity==		==Dietel Chapter 3: Connectivity==

Admin at 09:36, 9 September 2017

2017-09-09T09:36:47Z

@@ Line 1: / Line 1: @@
 ==Dietel Chapter 3: Connectivity==
@@ Line 47: / Line 65: @@
 (Not even going to try to slog through the rest of this chapter.)
-==Flags==
+=Flags=
 {{GraphsFlag}}
 [[Category:Diestel]]