Недревесность графа

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

Недревесность графа (Anarboricity of a graph) — наибольшее число попарно реберно-непересекающихся подграфов графа \,G, которые содержат циклы и дают после объединения весь граф \,G. Наряду с древесностью недревесность образует пару инвариантов: инвариант покрытия (древесность) и инвариант упаковки (недревесность).

Литература

  • Харари Ф., Палмер Э. Перечисление графов. — М.: Мир,1977.