10-27 Slow Cut

A slow algorithm for finding cut vertices.

Wednesday, October 27, 2021

A cut vertex or “articulation vertex” is a vertex whose removal disconnects the graph.

There is an efficient way of finding cut vertices, but as a warm up we will just focus on a simple algorithm.

Remember: you should develop test cases and examples so you have confidence your code works.

Here is the plan, as discussed in class:

Write get_component, a function which returns only the connected component of a graph containing a given vertex.
```
 def get_component(g: Graph, v: Vertex) -> Graph:
     return Graph(0) # TODO
```
Danger: some code may assume that the vertices of a graph with N vertices are [0..N-1]. Fix this problem if you discover it.
Given a graph and a single vertex v, create a new graph identical to the original except excluding v and edges that connect to v.
```
 def graph_without(g: Graph, v: Vertex) -> Graph:
     return g # TODO
```
Determine if v is a cut vertex by counting the connected components of graph_without(g,v).
```
 def cut_vertex(g: Graph, v: Vertex) -> Bool:
     return False # TODO
```

Create a list of all cut vertices in a graph.

 def all_cut(g: Graph) -> [Vertex]:
     return [] # TODO