Graphs : Some observations and notes

Walk is any sequences of vertices and edges.

Path is same as walk but no vertex is repeated in a path.

Use bfs when possible

Look out for 01 before djikstra

Independent set is a set of vertices, no two of which are adjacent.

Topsort
 kahn’s algo (when need to preserve order sometimes like UVA 11060, enqueue 0 indegree nodes in a heap process them)
 simple dfs everywhere else

DFS spanning tree
 Back edge : explored to explored
 Tree edge : explored to unexplored
Finding bridges and articulation points⌗

If some node is an articulation point then none of its descendants have a backedge to any of its ancestors . In case it doesn’t have any ancestors (when it is root node) then it shouldn’t have more than 1 children.

tin[node] : First time we visit node.

low[node] : lowest tin[] reachable in subtree of node

For articulation point : $low[child]\geq tin[node]$

For bridge : $low[child] > tin[node]$

Implementation:⌗
void dfs(int node,int p=1) { vis[node]=1; tin[node]=low[node]=timer++; int children=0; for(int u:adj[node]) { if(u==p)continue; if(vis[u])low[node]=min(low[node],low[u]); else { children++; dfs(u,node); low[node]=min(low[node],low[u]); if(low[u]>=tin[node] and p!=1) { //found articulation point } } } if(p==1 and children>1) { //found articulation point } }

In many SCC problems look for property of indegree 0 vertices first.

Condensed graph is when we substitute SCC with a representative node.
Biconnectivity⌗
 Graph is biconnected if it has no articulation points
 Biconnected component : Maximal biconnected subgraph
 Edge biconnected if no bridges
 Vertex biconnected if no articulation points
 In edge biconnected graph an edge will either be bridge or part of a biconnected component. If we denote that component with a single node we’ll get a tree.
 In vertex biconnected graph same kind of condensation gives a blockcut tree i.e. block of biconnected component cut vertex then another block followed by a cut vertex and so on.
Counting Paths⌗
 If $V$ is adjacency matrix of unweighted graph. Then $V^n$ contains number of paths of $n$ edges between nodes in a graph.