Notes - Pages 102-157

Components
strongly connected in a directed graph have bi-directional paths between any pair of nodes. In/out components are the set of reachable nodes from a specific node. Out components are the same for all nodes within the same strongly connected component.
136
Independent paths
two paths are (edge or node) independent if they do not share any edge or node. Upperbound by min degree of any two nodes, number of independent paths is called connectivity
138
Mengers Theorem
a (edge or node) cut set is a set of nodes removed to disconnect a pair of nodes. Mengers states that the minimum cut set is equal to the number of independent paths. The edge version of this theorem allows us to compute maximum flow through a network, as connectivity times the max flow rate of a single edge (assuming fixed flow). This also implies that connectivity == size of min cut set == max flow
139-140
Visualization
minimum distance squared, uses the formula $\triangle = x^TLx$ where x is a vector [xi, xj] ... the algrebraic connectivity (?) needs to be small to use this as a visualization technique
139-140

A Graph Laplacian representation is a matrix where the diagnol of i,j is the degree of node i, row sums to negate it. Has real non-negative eigenvalues.

page 150 - useful for simulation projects Graph sparsification forms the foundation for a range of modern numerical methods for solving large systems of simultaneous linear equations.