|
So far I've come across a bunch of different terms for matrices used in graph theory - adjacency matrix, connectivity/connection matrix, vertex matrix, etc. Are there any differences between these matrices or are all of these terms just referring to the same thing? |
|||||||||
|
|
Some important matrices for a graph $G=(V,E)$ are the following Adjacency matrix: This matrix $A$ denotes the adjacency between vertices. It is a $|V|\times|V|$ matrix and its entries $a_{ij}$ are defined as $$a_{ij}:=\begin{cases} 1 & \text{if $(v_i,v_j)\in E$} \\ 0 & \text{otherwise} \end{cases}. $$ Notice that if $G$ is undirected $A$ is symmetric. Taking the power $A^k$ gives you a matrix that denotes the number of paths from $v_i$ to $v_j$ at entry $i,j$. Laplacian matrix: For this matrix $L$ consider the diagonal matrix $D=\text{diag}(d_1,d_2,\ldots)$, for $d_i$ being the vertex degree of $v_i$. Then $L:=D-A$. The matrix $L$ is the most important object studied is spectral graph theory. It has many nice properties, for example its cofactors give the number of spanning trees of $G$. There is also a normalized version of the Laplace matrix. Incidence matrix: This is a $|V|\times |E|$ matrix $B$, whose entries $b_{ij}$ ar defined as $|V|\times|V|$ matrix and its entries $a_{ij}$ as $$b_{ij}:=\begin{cases} 1 & \text{if $v_i\in $V$$ is incident to $e_j\in E$} \\ 0 & \text{otherwise} \end{cases} $$ Sometimes you consider incidence matrices $\vec{B}$ for Graphs with oriented edges. In this case you would change the $1$ entries to $-1$ if the edge points away from a vertex. Notice that Notice that $\vec{ B}\, \vec{B}^T=L$. |
|||
|
