Матрица вложенности контуров

Материал из WEGA
Перейти к навигации Перейти к поиску

Матрица вложенности контуров (Cycle embedding matrix) — квадратная [math]\displaystyle{ \,(0,1) }[/math]-матрица размером [math]\displaystyle{ c \times c }[/math] ([math]\displaystyle{ \,c }[/math] — число контуров в графе), [math]\displaystyle{ \,(i,j) }[/math]-й элемент которой равен [math]\displaystyle{ \,1 }[/math], если контур [math]\displaystyle{ \,C_{j} }[/math] вложен в контур [math]\displaystyle{ \,C_{i} }[/math] т.е. если все вершины контура [math]\displaystyle{ \,C_{j} }[/math] принадлежат контуру [math]\displaystyle{ \,C_{i} }[/math] и равен [math]\displaystyle{ \,0 }[/math] в противном случае.

Литература

  • Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.