Cтраница 1
Перечисление орграфов ( Харари [2]) было завершено так же, как для графов: была найдена формула для циклового индекса при соответствующей группе конфигураций и затем была применена теорема Пойа. Множество VW состоит из упорядоченных пар различных элементов множества V. По определению группа 5р2 ] действует на множестве V как индуцированная группой Sp: каждая подстановка а из Sp индуцирует такую подстановку а из 5р2, что а ( i, /) ( ai, а /) для ( г /) из 1 4 Применяя теорему Пойа к цикловому индексу группы S [ P2 получаем многочлен dp ( x), в котором коэффициент при х9 равен числу орграфов с q ориентированными ребрами. [1]
Задача перечисления указанных орграфов представляет собой новый интересный тип задачи, которая, по-видимому, требует для своего решения подходящего обобщения леммы Бернсайда. [2]
Она доказывается с использованием того же циклового индекса, который применяется для перечисления орграфов, снова с двумя множествами переменных и со специальным перечисляющим рядом для фигур. [3]
В сильном орграфе каждая вершина является одновременно источником и стоком. Задача перечисления орграфов, обладающих и источником, и стоком, также не решена. Робинсон и здесь заявляет, что он может пересчитывать эти виды орграфов. [4]
Справедлива теорема ( см. Харари, Норман и Картрайт [1], стр. Поэтому подходящая модификация метода перечисления сильных орграфов может быть полезной при подсчете односторонних орграфов. И Робинсон действительно реализовал это в своем подходе к задаче перечисления односторонних орграфов, но пока еще полученные им результаты не только не опубликованы, но даже и не написаны. [5]
Орграф называется односторонне связным, или односторонним, если для любых двух вершин по крайней мере одна достижима из другой. Хотя односторонние компоненты орграфа не дают, вообще говоря, его разбиения, но все же метод Робинсона, упомянутый выше при рассмотрении задач перечисления сильных орграфов, можно приспособить и к односторонним орграфам. [6]
Орграф называется односторонне связным, или односторонним, если для любых двух вершин по крайней мере одна достижима из другой. Хотя односторонние компоненты орграфа не дают, вообще говоря, его разбиения, но все же метод Робинсона, упомянутый выше при рассмотрении задач перечисления сильных орграфов, можно приспособить и к односторонним орграфам. [7]
В § 1.6 мы видели, что всякий ациклический орграф содержит хотя бы одну вершину с нулевой полустепенью захода и что любое расширение ациклического орграфа также ациклично. Робинсон [4] использовал эти факты, чтобы перечислить и помеченные, и непомеченные ациклические орграфы. Однако он обнаружил, что для перечисления непомеченных ациклических орграфов необходимо объединить всю информацию о симметриях всех ациклических орграфов. Это объединение было достигнуто путем использования таких сумм цикловых индексов, в которых проводится различие между циклами вершин с нулевыми полустепенями захода и циклами остальных вершин. [8]
Справедлива теорема ( см. Харари, Норман и Картрайт [1], стр. Поэтому подходящая модификация метода перечисления сильных орграфов может быть полезной при подсчете односторонних орграфов. И Робинсон действительно реализовал это в своем подходе к задаче перечисления односторонних орграфов, но пока еще полученные им результаты не только не опубликованы, но даже и не написаны. [9]