Матрица разрезов

Матрица разрезов (Cutset matrix) — $\,(0,1)$-матрица, строки которой соответствуют простым разрезам, столбцы — ребрам графа и $\,(i,j)$-й элемент равен $\,1$, если ребро $\,j$ входит в разрез $\,i$, и равен нулю в противном случае.

Литература

• Зыков А.А. Теория конечных графов. — Новосибирск: Наука. Сиб. отд-ние, 1969.

• Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.