date: 2024-04-07
title: Graph-algorithm
status: UNFINISHED
author:
  - AllenYGY
tags:
  - Graph
  - Algorithm
  - NOTE
created: 2024-04-07T22:33
updated: 2024-04-15T13:24
publish: True

Graph-algorithm

Def: Graph

A graph is a pair of
V is the collection of vertices
E is the collection of edges

Def: Directed Graph

(u, v) and (v, u) are distinct for some edges (u, v) .

Def: Undirected Graph

(u, v) and (v, u) are identical for all edges (u, v) .

Graph Representation

Adjacency list Representation

is a linked list of all v that (u, v) .
- ,
- In directed graphs, is the out degree of v

Adjacency matrix Representation

is a matrix such that if .

DFS Algorithm

What does DFS do?

Traverse all vertices in graph, and thereby
Reveal properties of the graph.

Four array s are used to keep information gathered during traversal.

Four Arrays

: the color of each vertex visited
- white: undiscovered
- gray : discovered but not finished processing
- black: finished processing
: the predecessor pointer pointing back to the vertex from which u was discovered
: the discovery time
- a counter indicating when vertex u is discovered
: the finishing time
- a counter indicating when the processing of vertex ( and all its descendants ) is finished

Algorithm DFS(G)

Input: Graph $G$

Output: Vertex traversal of graph $G$

for all vertex $u \in V(G)$ do

$color[u] \gets \text{white}$ //Initialize

$pred[u] \gets \text{NULL}$

end for

$time \gets 0$

for all vertex $u \in V(G)$ do//Start a new tree

if $color[u] == \text{white}$ then

DFSVisit( $u$ )

end if

end for

Algorithm DFSVisit

$color[u] \gets \text{gray}$ //u is discovered

$d[u] \gets ++$ time//u's discovery time

for all $v \in \text{adj}[u]$ do//Visit undiscovered vertex

if $color[v] == \text{white}$ then

$pred[v] \gets u$

DFSVisit( $v$ )

end if

end for

$color[u] \gets \text{black}$ //u has finished

$f[u] \gets ++$ time//u finish time

The output of DFS

The time stamp arrays: d[v], f[v]
The predecessor array: pred[v]

Def: DFS Forest

Use to define a graph as follows:

It is a graph with no cycles, and a collection of trees.

HandShaking Theorem

If G=(V, E) is an undirected graph
If G=(V, E) is an directed graph

DFS Time Analysisi

DFS Properties

Time Time-Stamp Structure

DFS Properties

u is a descendant ( in DFS trees ) of v, if and only if is a subinterval of .
u is an ancestor of v, if and only if contains .
u is unrelated to v, if and only if and are disjoint intervals.

Time-Stamp-1

Proof

The idea is to consider every case.
Assume wlog.

If , then
- u is discovered when v is still not finished y et ( marked gray) u is a descendant of v ;
- u is discovered later than v u should finish before v;
- hence we have is a subinterval of .
If , then
- Obviously and $[d[v] , f[v]] are disjoint;
- Which means that when u or v is discovered, the others are not marked gray;
- And hence neither vertex is a descendant of the other

Tree Structure

Theorem

An edge in an undirected graph is either a tree edge or a back edge.

Proof

Assume . Then, v is be discovered while u is gray.
Hence v is in the DFS subtree rooted at u.

If , is a tree edge.
If , is a back edge.

Application

Articulation

Def: Articulation

Let G=(V, E) be a connected undirected graph.
An articulation point (cut vertex) of G is a vertex whose removal disconnects G

Given a connected graph G, how to find all articulation points?

Brute Force Solution

Brute Force Solution

Remove a vertex and its corresponding edges one by one one from G.
Test whether the resulting graph is still connected or not say by DFS.

The running time is O (n ∗(n + e)) .

Observations

The root of the DFS tree is an articulation point if it has two or more children.
A leaf of the DFS tree is not an articulation point.
And for other internal vertex v in the DFS tree, v is an articulation point if
if there is one subtree rooted at a child of v that does not have a back edge which climbs higher than v.

Tackle Observation 3

Def: Low and high

Using the discovery time in the DFS tree to define low and high.

If there is a subtree rooted at a children of v which does not have a back edge connecting to a vertex with discovery time smaller than d[v] , then v is an articulation point.

Let Low (w) be the smallest value that a descendant of w can climb up by a back edge.
We use d[v] to express the “hight” of v.
v is “higher” than u if v and u are on the same branch of the DFS tree and d[v] < d[u] .
If v and u are on different branches, d[v] and d[u] are not compatible by the time-stamp structure.