diff options
Diffstat (limited to 'final/connectedness.tex')
| -rw-r--r-- | final/connectedness.tex | 58 |
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 |