資料結構

In graph theory an undirected graph has two kinds of incidence matrices: unoriented and oriented. The unoriented incidence matrix of an undirected graph is a $n \times m$ matrix B, where $n$ and $m$ are the number of vertices and edges respectively, such that

$B_{ij} = \begin{cases} 1 & \text{if vertex } v_i \text{ is incident with edge } e_j \\ 0 & \text{otherwise} \end{cases}$

An undirected graph (with no self-loops) consisting of 4 nodes and 4 edges is given as followed: 頂點 1 與 2、1 與 3、1 與 4、3 與 4 之間各有一條邊（圖中邊標號 1、2、3、4 分別對應 $e_1$–$e_4$）。

The incidence matrix of the undirected graph above is（$e_1$: (1,2), $e_2$: (1,3), etc.）:

The incidence matrix of a directed graph is a $n \times m$ matrix $B = (b_{ij})$ such that

$b_{ij} = \begin{cases} -1 & \text{if edge } e_j \text{ leaves vertex } v_i \\ \ \ \ 1 & \text{if edge } e_j \text{ enters vertex } v_i \\ \ \ \ 0 & \text{otherwise} \end{cases}$

The oriented incidence matrix of an undirected graph is the incidence matrix of ANY orientation of the graph. Check the following oriented incidence matrices of the given graph with ANY chosen edge direction. Which of the following matrix B with the multiplication: $BB^T$ (T: transpose) will generate a result that is different from the others?