Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
You might have an Edge connectivity matrix which is different from the adjacency matrix (call that the vertex connectivity matrix): The edge-connectivity matrix, denoted by $^eχ$, of a graph $G$ is the vertex-conectivity matrix of the corresponding line graph $\text{L}(G)$. –  draks ... Jan 11 '13 at 12:55
2  
There is also the incidence matrix whose entry $m_{ij}$ is the number of times that vertex $i$ and edge $j$ are incident. –  PAD Jan 11 '13 at 13:23
add comment

1 Answer

up vote 3 down vote accepted

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$.

share|improve this answer
    
Is there a simple way to count the number of walks (no loops allowed) from $v_i$ to $v_j$? –  Calvin Lin Jan 11 '13 at 15:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.