Incidence matrix

Incidence matrix --- матрица инцидентности.

1.(For a graph) The (vertex-edge) incidence matrix [math]\displaystyle{ I(G) }[/math] of a graph [math]\displaystyle{ G = (V,E) }[/math], [math]\displaystyle{ V = \{v_{1}, \ldots, v_{n}\} }[/math], [math]\displaystyle{ E = \{e_{1}, \ldots, E_{m}\} }[/math], is [math]\displaystyle{ n \times m }[/math] [math]\displaystyle{ (0,1) }[/math]-matrix with entries

[math]\displaystyle{ i_{kl} = \left \{\begin{array}{l} 1,\mbox{ if }v_{k} \in e_{l} \\ 0,\mbox{ otherwise} \end{array} \right. }[/math]

2. (For a directed graph) The incidence matrix of a directed graph [math]\displaystyle{ D }[/math] is a [math]\displaystyle{ p\times q }[/math] matrix [math]\displaystyle{ \{b_{i,j}\} }[/math] where [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] are the numbers of vertices and edges respectively, such that [math]\displaystyle{ b_{i,j} }[/math] = 1 if the edge [math]\displaystyle{ x_j }[/math] leaves vertex [math]\displaystyle{ v_i }[/math], 1 if it enters vertex [math]\displaystyle{ v_i }[/math] and 0 otherwise. (Note that many authors use the opposite sign convention.)

3. (For a hypergraph) Let [math]\displaystyle{ {\mathcal H} }[/math] be a hypergraph, [math]\displaystyle{ E = \{e_{1}, \ldots, e_{m}\} }[/math] be its edge set and [math]\displaystyle{ V = \{v_{1}, \ldots, v_{n}\} }[/math] be its vertex set. The incidence matrix [math]\displaystyle{ {\mathcal IM(H)} }[/math] of the hypergraph [math]\displaystyle{ {\mathcal H} }[/math] is a matrix whose [math]\displaystyle{ (i,j) }[/math] entry is 1 if [math]\displaystyle{ v_{i} \in e_{j} }[/math] and 0 otherwise. Note that the transposed matrix [math]\displaystyle{ {\mathcal IM(H)}^{T} }[/math] is the incidence matrix of the dual hypergraph [math]\displaystyle{ {\mathcal H}^{\ast} }[/math]. A totally balanced matrix is incidence matrix of a totally balanced hypergraph.