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

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

Литература

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

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