Перечисление - граф
Cтраница 1
Перечисление графов существенно упрощается, когда применяют достаточно простые инварианты. Распределение степеней вершин графа является первым из них. В теории графов и комбинаторике его принято называть разбиением числа 2r J ] п; на t; чисел натурального ряда. [1]
Перечислению 2-раскрашенных графов был посвящен § 4.3, а корневые графы, у которых в качестве корня выделялся некоторый порожденный подграф, изучались в предыдущем параграфе - Предметом данного параграфа является распространение этих исследований на случай перечисления таких корневых графов, у которых в качестве корня берется не обязательно порожденный подграф; затем предполагается применить полученные выводы к перечислению иг-раскрашенных графов. [2]
Перечислению 2-раскрашенных графов был посвящен § 4.3, а корневые графы, у которых в качестве корня выделялся некото-рый порожденный подграф, изучались в предыдущем параграфе - Предметом данного параграфа является распространение этих исследований на случай перечисления таких корневых графов, у которых в качестве корня берется не обязательно порожденный подграф; затем предполагается применить полученные выводы к перечислению m - раскрашенных графов. [3]
Теория перечисления графов занимается разработкой методов подсчета числа неизоморфных графов, обладающих тем или иным свойством. [4]
Задача перечисления биокрашенных и бихроматических графов недавно была сформулирована с помощью построения новой бинарной операции на группах подстановок, названной экспоненциацией. [5]
Эффективный метод Пойа для перечисления графов требует построения группы подстановок, орбиты которой соответствуют в точности изоморфным классам помеченных графов с р вершинами и q ребрами. После получения явной формулы для соответствующего циклового индекса, применив теорему Пойа с рядом 1 жв качестве перечисляющего ряда для фигур, находим перечисляющий многочлен, в котором коэффициент при xq равен числу ( р, д) - графов. [6]
Эффективный метод Пойа для перечисления графов требует построения группы подстановок, орбиты которой соответствуют в точности изоморфным классам помеченных графов с р вершинами и q ребрами. После получения явной формулы для соответствующего циклового индекса, применив теорему Пойа с рядом 1 а; в качестве перечисляющего ряда для фигур, находим перечисляющий многочлен, в котором коэффициент при xq равен числу ( р, д) - графов. [7]
Асимптотические методы необходимы для перечисления непомеченных графов. Когда применяется теорема Пойа или ее обобщение, получающаяся производящая функция часто неудобна. Тогда энумератор непомеченных графов асимптотически равен деленному на п энумератору помеченных графов. Это замечание полезно, поскольку обычно проще получать оценки лля помеченных графов. [8]
Сейчас многие задачи по перечислению графов решены. К примеру, можно подсчитать число графов, орграфов, связных графов, деревьев и эйлеровых графов, содержащих данное число вершин и ребер; однако соответствующие результаты для планарных и гамильтоновых графов еще не получены. К сожалению, почти ни в одном случае невозможно выразить эти результаты с помощью простых формул. [9]
 |
Графы, неподвижные относительно нечетной п четной циклических подстановок. [10] |
Так же как при перечислении графов ( см. § 4.1), мы рассмотрим далйе пары циклов zr и zt из подстановки а и такие 2-подмно-жества, которые имеют по одной вершине в каждом из этих циклов. При нахождении циклового индекса парной группы мы видели, что циклы z, и zt индуцируют ( г, t) циклов длины [ г, t ], действующих на указанных выше 2-подмножествах ( ср. Заметим, что если t - четное иг - нечетное, то каждая вершина цикла zr находится в четном числе таких 2-подмножеств. Памятуя об этом, мы теперь рассмотрим все пары циклов zr и zt, у которых либо г, либо t - четное. [11]
 |
Графы, неподвижные относительно нечетной и четной циклических подстановок. [12] |
Так же как при перечислении графов ( см. § 4.1), мы рассмотрим далее пары циклов zr и zt из подстановки а и такие 2-подмно-жества, которые имеют по одной вершине в каждом из этих циклов. При нахождении циклового индекса парной группы мы видели, что циклы zr и zt индуцируют ( г, t) циклов длины [ г, t ], действующих на указанных выше 2-подмножествах ( ср. Заметим, что если t - четное иг - нечетное, то каждая вершина цикла zr находится в четном числе таких 2-подмножеств. Памятуя об этом, мы теперь рассмотрим все пары циклов zr и zt, у которых либо г, либо t - четное. [13]
Аналогичные формулы были получены для перечисления графов с корнем и связных графов. С помощью модификаций этого метода были перечислены различные классы графов. [14]
Для такого преобразования исключается необходимость перечисления узловых графов Г - модели при установлении необходимых и достаточных условий осуществимости преобразования. Указанное следует из того, что для re - мерной Т - модели всевозможные неразветвленные узловые графы размерности меньше п - 2 получаются из соответствующего ( п - 2) - мерного узлового графа при некоторых частных значениях квазиупругих параметров его соединений. Иначе говоря, в рассматриваемом случае можно ограничиться определением необходимых и достаточных условий - преобразования А - модели в Гп-модель с ( п - 2) - мерным узловым графом. [15]
Страницы: 1 2 3 4