Graphs p3 (DFSp2 and Weights)

Andy Novocin

Problem of the day

Draw on Board

Edge Classification

Base case Tree Edge (parent to child)

Forward Edge (jump beyond children)

Back Edge (jump past parents)

Cross Edge (jump to cousins)

Classify edge pseudo-code

def classify(x,y):
  if (y.parent == x):
    return "TREE"
  elif y.discovered() and !y.processed():
    return "BACK"
  elif y.processed() and (y.dt > x.dt):
    return "FORWARD"
  elif y.processed() and (y.dt < x.dt):
    return "CROSS"
    

Detecting Cycles

No back edge == No cycles

Detecting back edges is mildly subtle

NOTE: In undirected this is \( \mathcal{O}(|V|) \leq \mathcal{O}(|V|+|E|)\)

DAG => No Cycle

Note that you cannot topological sort with cycles.

But you can almost topological sort.

Articulation Vertices

Graphs are networks

Weak points are targets or key defense points

Back edges create security cables

Articulation Brute Force

Test if connected (using BFS or DFS)

For each vertex, remove it, test again, reinsert

Articulation In One Pass

\(v\) is an Articulation Vertex if and only if:

\(v\) is not a leaf, and there is a subtree of \(v\) which has no back edges that reach beyond \(v\).

Guide to the code

In the book there is an implementation

Cliff's Notes version:

Figure out the farthest back reachable using only neighbors.

If this answer is earlier than parent's answer then pass it along.

Three cases

Root cut-node (root has more than 1 tree child)

Bridge cut-node (my oldest reachable ancestor is me) then me and parent are cut-nodes

Parent cut-node (oldest reachable is non-root parent (in odd ways)) then parent is cut-node

Draw Example on Board

Strongly connected components

In directed graphs can detect if connected by traversal and traversal of reverse graph.

To spit out the components is a bit trickier.

Concept of algo

Any cycle must be in a strongly connected component (SCC)

Collapse the cycles into one 'vertex'

CROSS edges from unlabeled components into old components also create a cycle.

Repeat until no cycles.

ICUP3

Find the SCC for problem 5-2

Work problems

If we have time work HW and ask questions