Выдержка из книги
Гамкрелидзе Р.В.
Алгебра Топология 1962
Работа Рида [ 187J посвящена подсчету графов, степени вершин которых делятся на заданное число, и связных графов. Риордан [188] каждому отображению множества п элементов в себя относит направленный граф и выводит рекуррентную формулу для количеств графов такого типа, имеющих заданное число компонент связности. К комбинаторным приложениям теории графов относится результат Харари [139] о взаимно однозначном соответствии между множеством неэквивалентных задач на перестановки с ограниченным положением ( см. [52], глава 7) и множеством неизоморфных графов с вершинами двух цветов; так как задача подсчета элементов второго множества ранее уже была решена им же [134] ( при помощи метода Пойя), то и задача пересчета первого множества, казавшаяся очень трудной, тем самым оказывается решенной.
![Работа Рида [ 187J посвящена подсчету графов, степени вершин которых делятся на заданное число, и связных графов. Риордан [188] каждому отображению множества п элементов в себя относит направленный граф и выводит рекуррентную формулу для количеств графов такого типа, имеющих заданное число компонент связности. К комбинаторным приложениям теории графов относится результат Харари [139] о взаимно однозначном соответствии между множеством неэквивалентных задач на перестановки с ограниченным положением ( см. [52], глава 7) и множеством неизоморфных графов с вершинами двух цветов; так как задача подсчета элементов второго множества ранее уже была решена им же [134] ( при помощи метода Пойя), то и задача пересчета первого множества, казавшаяся очень трудной, тем самым оказывается решенной.](/pic/5357196NPzltcY0020276078.png)