Графы раскрашенные

Описанный выше способ перехода от комбинаторной энтропии к числу упорядоченных деревьев распространяется на случай систем с несколькими типами мономеров. Для этого достаточно раскрасить вершины графа большим количеством цветов и учитывать эту раскраску при автоморфизмах графа. Если степень узла некоторого v-ro цвета составляет /v, то выходящие из него ветви переставляются (/v —1) (для корня — /v ) способами. Будем характеризовать молекулу вектором состава I, компоненты которого Z, (v = = 1, 2,. ..) равны числам узлов графа разных цветов. Тогда для q-TQ изомера такого 1-мера в результате всех перестановок вершин его молекулярного графа находим число различных упорядоченных корневых деревьев [1, 17] [c.166]

РАСКРАСКА. Дан граф. Спрашивается, можно ли раскрасить его вершины в три цвета так, чтобы концы каждого ребра были покрашены в разные цвета. (Аналогичная задача 2-РАСКРАСКА решается за полиномиальное время.) [c.36]

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

Минимальное число красок, которыми можно раскрасить все смежные вершины графа в разные цвета, называют хроматическим числом X. Максимальное хроматическое число равно 5 для плоского графа. В зависимости от значения к графы именуют к-хроматическими. Над графами могут быть произведены операции расширения в надграф — внедрение некоторых новых вершин в соответствующие ребра, так чтобы эти ребра превратились в цепь, а также сжатия — удаление некоторых вершин и ребер, переводящее граф в другой граф (подграф), содержащий меньшее их количество. [c.172]

Справочник химика 21

Химия и химическая технология