Комбинаторно двойственный граф

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

Комбинаторно двойственный граф (Combinatoricaly dual graph) — для данного графа \,G граф G^{\ast} такой, что существует взаимно однозначное соответствие между их множествами ребер, при котором для любых соответствующих подмножеств ребер \,Y и Y^{\ast} коциклический ранг графа G \setminus Y равен коциклическому рангу \,G минус циклический ранг части <Y^{\ast}> графа G^{\ast}, порожденной множеством ребер Y^{\ast}.

Литература

  • Харари Ф. Теория графов. — М.: Мир, 1973.