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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Литература

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