2.3 Graph Theory

2.3.1 Basic Concets

$$G=(V,E)$$

• Graph Symbols $$G=(V,E)$$
  • $V$ : the set of vertices
  • $E$: the set of edges
  • An edge $e=u,v$ has two endpoints $u$ and $v$ which are said to be joined by $e$.
  • $u$ is the neighbor of $v$ which mean adjacent.
  • edges can be either directed or undirected.

2.3.2 Algebra representations of graph

• Adjacency matrix $$A_{ij}=\begin{cases}1 & if \{ v_i, v_j\} \in E \, and \, (i \neq j), \\ 0 & otherwise. \end{cases} $$
• Degree matrix $$D_ii = d(v_i)$$
• Laplacian matrix $$L=D-A$$ 
  • this can be represented as $$L_{ij} = \begin{cases} d(v_i) & if i=j, \\ -1 & if \{v_i, v_j\} \in E \, and \, i \neq j, \\ 0 & otherwise.\end{cases}$$
• Symmetric normalized Laplacian $$L^{sym} =D^{-\frac{1}{2}}LD^{-\frac{1}{2}} = I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}} $$
• Random walk normalized Laplacian $$L^{rw} = D^{-1}L = I-D^{-1}A$$
• Incidence matrix