Перечисление - граф - Большая Энциклопедия Нефти и Газа, статья, страница 1
Дипломатия - это искусство говорить "хоро-о-ошая собачка", пока не найдешь камень поувесистей. Законы Мерфи (еще...)

Перечисление - граф

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 Графы, неподвижные относительно нечетной п четной циклических подстановок. [10]

Так же как при перечислении графов ( см. § 4.1), мы рассмотрим далйе пары циклов zr и zt из подстановки а и такие 2-подмно-жества, которые имеют по одной вершине в каждом из этих циклов. При нахождении циклового индекса парной группы мы видели, что циклы z, и zt индуцируют ( г, t) циклов длины [ г, t ], действующих на указанных выше 2-подмножествах ( ср. Заметим, что если t - четное иг - нечетное, то каждая вершина цикла zr находится в четном числе таких 2-подмножеств. Памятуя об этом, мы теперь рассмотрим все пары циклов zr и zt, у которых либо г, либо t - четное.  [11]

12 Графы, неподвижные относительно нечетной и четной циклических подстановок. [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