Cтраница 4
Теорема перечисления Редфилда может быть использована для подсчета числа суперпозиций и в тех случаях, когда конституэнты являются орграфами или когда среди конституэнт имеются и графы, и орграфы. Сам Редфилд проиллюстрировал свою теорему, строя суперпозиции циклов и ориентированных циклов, которые он использовал и отдельно друг от друга, и совместно. [46]
Число соединения тесно связано с другим важным инвариантом ориентированных графов, называемым числом обратной связи. Оно определяется как минимальное число ребер, удаление которых разрушает каждый ориентированный цикл в орграфе. [47]
Мы будем рассматривать некоторые вопросы, аналогичные изученным в главе 5 для неориентированных графов и связанные с листами и блоками. Ребро в G называем ориентированно-циклическим ребром, если оно принадлежит некоторому ориентированному циклу, и ациклическим в противном случае. [48]