Incidence matrices

Another common way to represent graphs is to use incidence matrices. Let be an undirected graph. Suppose that are the vertices and are the edges of G. Then the incidence matrix with respect to this ordering of V and E is the matrix , where .

Example. Represent the graph shown in Figure below with an incidence matrix.

Solution: e ₁ e ₂ e ₃ e ₄ e ₅ e ₆

Incidence matrices can also be used to represent multiple edges and loops. Multiple edges are represented in the incidence matrix using columns with identical entries, since these edges are incident with the same pair of vertices. Loops are represented using a column with exactly one entry equal to 1, corresponding to the vertex that is incident with this loop.

Example. Represent the pseudograph shown in Figure below using an incidence matrix.

Solution: e ₁ e ₂ e ₃ e ₄ e ₅ e ₆ e ₇ e ₈

Дата добавления: 2014-12-23