Added connectedness algorithms

1 files changed, 58 insertions, 0 deletions

diff --git a/final/connectedness.tex b/final/connectedness.tex
new file mode 100644
index 0000000..18a382a
--- /dev/null
+++ b/final/connectedness.tex
@@ -0,0 +1,58 @@
+A graph is connected if there exists a path between any pair of vertices.
+Beearliest is a simple algorithm that uses a depth-first search to determine whether a given graph is connected, using Python3 and the NetworkX library.
+
+{\tt \obeylines
+    import networkx as nx
+    
+    def is\_graph\_connected(G):
+    \leavevmode\hskip .25in     VISITED = []
+    \leavevmode\hskip .25in     def dfs\_connectedness(v):
+    \leavevmode\hskip .50in     nonlocal VISITED
+    \leavevmode\hskip .50in     for node in G.adj[v].keys():
+    \leavevmode\hskip .75in     if node not in VISITED:
+    \leavevmode\hskip 1.00in    VISITED.append(node)
+    \leavevmode\hskip 1.00in    dfs\_connectedness(node)
+    \leavevmode\hskip .50in     return len(VISITED) == len(G.nodes)
+    \leavevmode\hskip .25in     return dfs\_connectedness(0)
+}
+
+This algorithm compiles a list of the visited nodes of the graph G, and then determines if that list contains every node after the search is complete.
+The search can start at an arbitrary node (here, it chooses the node labelled 0). The algorithm has a time complexity of $O(V+E)$, where a given graph G has V vertices and E edges.
+
+This same algorithm can be used to create an algorithm of complexity $O(E\cdot(V+E))$ to find all bridges of a connected graph (i.e. all edges which, when removed, would result in the graph becoming unconnected).
+The algorithm simply iterates through each edge of the original graph, removing it and then determining its connectedness using the method above.
+This quadratic algorithm is, however, not the most efficient algorithm for locating bridges. An $O(V+E)$ algorithm can be developed as shown below:
+
+{\tt \obeylines
+    def bridges\_2(G):
+    \leavevmode\hskip .25in BRIDGES = []
+    \leavevmode\hskip .25in tick = 0
+    \leavevmode\hskip .25in def bridges\_2\_recursion(v):
+    \leavevmode\hskip .50in nonlocal BRIDGES, VISITED, tick, discoveries, earliest, parents
+    \leavevmode\hskip .50in VISITED.append(v)
+    \leavevmode\hskip .50in discoveries[v] = tick
+    \leavevmode\hskip .50in earliest[v] = tick
+    \leavevmode\hskip .50in tick += 1
+    \leavevmode\hskip .50in for v2 in G.adj[v]:
+    \leavevmode\hskip .75in if v2 not in VISITED:
+    \leavevmode\hskip 1.00in parents[v2] = v
+    \leavevmode\hskip 1.00in bridges\_2\_recursion(v2)
+    \leavevmode\hskip 1.00in earliest[v] = min(earliest[v], earliest[v2])
+    \leavevmode\hskip 1.00in if earliest[v2] > discoveries[v]:
+    \leavevmode\hskip 1.25in BRIDGES.append((v, v2))
+    \leavevmode\hskip .75in elif parents[v] != v2:
+    \leavevmode\hskip 1.00in earliest[v] = min(earliest[v], discoveries[v2])
+    \leavevmode\hskip .25in n = len(G.nodes)
+    \leavevmode\hskip .25in VISITED = []
+    \leavevmode\hskip .25in discoveries = [float("Inf")] * n
+    \leavevmode\hskip .25in earliest = [float("Inf")] * n
+    \leavevmode\hskip .25in parents = [-1] * n
+    \leavevmode\hskip .25in for v in range(n):
+    \leavevmode\hskip .50in if v not in VISITED:
+    \leavevmode\hskip .75in bridges\_2\_recursion(v)
+    \leavevmode\hskip .25in return BRIDGES
+}
+
+The diagram shown below plots the time taken to calculate the number of bridges on the y-axis, with the value of V+E on the x-axis.
+
+\pdfximage{connectedness/bridges_algorithm_2.png} \pdfrefximage\pdflastximage
\ No newline at end of file