10-31-2024 - Graph Theory

$$G=(\underset{\text{vertex set}}{\underbrace{V}},\underset{\text{edge set}}{\underbrace{E}})$$

Adjacency matrix ${\mathbf{A}}_{ij}\in \{0,1\}$

Previously, we looked at directed graphs. Now, we will focus on graphs Further, we will only consider simple & connected graphs

Def. simple graph means no multiple edges and no loops Def. connected means for every $v\in V$ exists an edge passing through $v$. This means that ${\mathbf{A}}_{ij}\in \{0,1\}$ and no column is $\vec{0}$.

Degree matrix $\mathbf{D}$:

$$\mathbf{D}=\mathrm{diag}(d_{11},d_{22},\dots ,d_{nn})$$

where $d_{ii}=\text{number of edges arriving at vertex i}$.

$$\mathbf{D}=\mathrm{diag}(2,3,2,2,3)$$ $$\mathbf{A}=\left[\begin{array}{ccccc}0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 1& 1& 0\end{array}\right]$$

Laplacian Matrix

$$\mathbf{L}=\mathbf{D}-\mathbf{A}$$ $$\mathbf{L}=\left[\begin{array}{ccccc}2& 0& 0& 0& 0\\ 0& 3& 0& 0& 0\\ 0& 0& 2& 0& 0\\ 0& 0& 0& 2& 0\\ 0& 0& 0& 0& 3\end{array}\right]-\left[\begin{array}{ccccc}0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 1& 1& 0\end{array}\right]=\left[\begin{array}{ccccc}2& -1& 0& -1& 0\\ -1& 3& -1& 0& -1\\ 0& -1& 2& 0& -1\\ -1& 0& 0& 2& -1\\ 0& -1& 0& -1& 3\end{array}\right]$$

Graph Partitioning - Problem

cut graph

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠ You can decompress Drawing data with the command palette: ‘Decompress current Excalidraw file’. For more info check in plugin settings under ‘Saving’

Excalidraw Data

Text Elements

Link to original

How to make a minimal cut to sub-divide (partition) a graph into two simple & connected graphs of comparable size?

Fact (Fiedler’s Method)

The first non-zero eigenvalue and corresponding eigenvector give a good graph partition as in Problem.

Fact 1: 0 is an eigenvalue of $\mathbf{L}$. The sum of of all the columns in $\mathbf{L}$ is 0. This tells you the eigenvector is $\left[\begin{array}{c}1\\ 1\\ 1\\ ⋮\\ 1\end{array}\right]$. Fact 2: eigenvalues of $\mathbf{L}$ are ${\lambda }_1=0<{\lambda }_2\le \cdots \le {\lambda }_n$. (”$\mathbf{L}$ is a nonnegative matrix” = “the eigenvalues of $\mathbf{L}$ are all positive”).

Def. $\bar{\mathbf{v}}$ is (the) eigenvector for ${\lambda }_2$. (Fiedler vector) (There can be more than one if multiplicity is higher/${\lambda }_2={\lambda }_3$ etc.)

E.g. for this graph ($L_2$): ${\lambda }_1=0$, ${\lambda }_1=0.358$, ${\lambda }_3=2$… $\bar{\mathbf{v}}=\left[\begin{array}{c}0.48\\ -0.15\\ 0.31\\ -0.35\\ -0.35\\ 0.48\\ -0.42\end{array}\right]$

Fiedler method: partition $V=V_{+}U{V}_{-}$.

$$V_{+}=\{i:{\bar{v}}_i>0\}=\{1,3,6\}$$ $$V_{-}=\{i:{\bar{v}}_i<0\}=\{2,4,5,7\}$$

V+ corresponds to the left (Triangle), V- corresponds to the right (square)

Continued at 11-14-2024 - Portfolio Optimization