Раскрашенный граф

Cтраница 1

Четные графы пятого порядка и их числа симметрии. [1]

Раскрашенный граф состоит из графа G с множеством вершин V i такого отношения эквивалентности на множестве V, что любые межные вершины не эквивалентны, k классов эквивалентности тссматриваются как различные цвета и граф G называется - раскрашенным. Два / с-раскрашенных графа изоморфны, если уществует взаимно однозначное соответствие между их множествами вершин, которое сохраняет не только смежность, но и цвета. Заметим, что цвета не закреплены постоянно, а являются взаимозаменяемыми. Данный граф может быть - раскрашен многими шособами. Например, все 3-раскраски некоторого помеченного чрафа порядка 6 показаны на рис. 1.5.1, где буквы а, Ъ и с обозначают цвета, а натуральные числа обозначают пометки. [2]

Четные графы пятого порядка и их числа симметрии. [3]

Раскрашенный граф состоит из графа G с множеством вершин V и такого отношения эквивалентности на множестве F, что любые смежные вершины не эквивалентны, k классов эквивалентности рассматриваются как различные цвета и граф G называется - раскрашенным. Два - раскрашенных графа изоморфны, если существует взаимно однозначное соответствие между их множествами вершин, которое сохраняет не только смежность, но и цвета. Заметим, что цвета не закреплены постоянно, а являются взаимозаменяемыми. Данный граф может быть / с-раскрашен многими способами. Например, все 3-раскраски некоторого помеченного графа порядка 6 показаны на рис. 1.5.1, где буквы а, Ъ и с обозначают цвета, а натуральные числа обозначают пометки. [4]

В правильно раскрашенном графе множества вершин одного цвета образуют внутренне устойчивые множества. [5]

Пусть а, 8, у - три различные вершины правильно раскрашенного графа, причем в каждой us них отсутствует хотя бы один из двух различных цветов х и у. Тогда хотя, бы одна из этих вершин не соединена ни с одной из двух остальных ( х, у) - цепъю. [6]

Тем самым проблема представления имеет вид ( X, Г) и соответствует раскрашенному графу. Каждому узлу дерева поиска придан счетчик, показания которого увеличиваются на единицу каждый раз, когда к данному узлу применяется программа продолжения. Таким образом, в счетчике содержится число, указывающее номер оператора, применяемого на следующем шаге. Когда число это превышает количество имеющихся операторов, отмечается, что узел уже продолжен до конца. [7]

Заметим, что формула (1.2.8) не позволяет 1 выразить производящую функцию для связных ft - раскрашенных графов в терминах производящей функции для ft - раскрашенных графов. [8]

Заметим, что формула (1.2.8) не позволяет 1 выразить производящую функцию для связных / с-раскрашенных графов в терминах производящей функции для - раскрашенных графов. [9]

Если допустимы пять разных цветов и каждое ребро графа, изображенного на рис. 2.3.1, окрашено одним из этих цветов, то сколько возможно различных раскрашенных графов. [10]

Заметим, что формула (1.2.8) не позволяет 1 выразить производящую функцию для связных ft - раскрашенных графов в терминах производящей функции для ft - раскрашенных графов. [11]

Мы представим в этой главе избранные образцы некоторых выдающихся и интересных решений ряда задач перечисления помеченных объектов в теории графов, включая нахождение числа помеченных графов, связных графов, блоков, эйлеровых графов, - раскрашенных графов, ациклических орграфов, деревьев и эйлеровых контуров в эйлеровом орграфе. Часто будут даваться несколько различных решений одной и той же задачи, так что читатель сможет познакомиться с большим разнообразием полезных приемов, методов, подходов и схем. Например, мы увидим, что когда имеешь дело с задачами перечисления помеченных объектов, то экспоненциальные производящие функции оказываются естественным средством для запоминания информации, достаточной для решения. С другой стороны, исследуя незначительное количество данных, можно часто найти очень быстро требуемую формулу, истинность которой можно затем установить по индукции. [12]

Перечислению 2-раскрашенных графов был посвящен § 4.3, а корневые графы, у которых в качестве корня выделялся некото-рый порожденный подграф, изучались в предыдущем параграфе - Предметом данного параграфа является распространение этих исследований на случай перечисления таких корневых графов, у которых в качестве корня берется не обязательно порожденный подграф; затем предполагается применить полученные выводы к перечислению m - раскрашенных графов. [13]

В тех случаях, когда возникает необходимость различать вершины или ребра графов по каким-либо внутренним признакам, их раскрашивают в разные цвета. Для изоморфности раскрашенных графов необходимо существование такого взаимооднозначного отображения одного графа на другой, при котором сохраняется смежность вершин, инцидентность вершин и ребер, а также раскраска этих элементов. Двудольным называется граф, вершины которого можно раскрасить двумя цветами так, чтобы каждое ребро соединяло вершины разных цветов. [14]

Затем надо создать раскрашенный граф, в котором каждая вершина соответствует связи исходного графа, и вершины, смежные с вершиной L, составляют множество конфликтных с L связей в исходном графе. [15]

Страницы: 1 2