About non-isomorphic graph colouring generating by read - faradzhev method.pdf Введение Отказоустойчивость - одно из важных свойств, которое необходимо учитывать при разработке безопасных систем. Для исследования полной отказоустойчивости дискретных систем в 1976 г. JohnP. Hayes [1] предложил теоретическую модель, основанную на графах. Вершины графа соответствуют элементам системы, а рёбра - связям между элементами. Если элементы системы имеют разный тип, то соответствующие им вершины получают метку, обозначающую тип или цвет. Аналогично можно рассматривать систему, в которой и связи могут иметь разный тип. В соответствующем графе рёбра будут раскрашены в цвет, обозначающий тип связи. Если элементы и связи системы имеют одинаковый тип, то рассматривается обыкновенный граф, в котором вершины и рёбра не окрашены. Большинство полученных результатов по исследованию отказоустойчивости систем относятся именно к этому случаю, то есть к неокрашенным графам [2]. При переходе к цветным графам возникает задача их генерации по заданному неокрашенному графу. В данной работе рассматривается именно такая задача. Очевидно, что эта задача может представлять интерес и без привязки к исследованию отказоустойчивых систем. Определение 1. Пусть G = (V, а) - неориентированный граф, k - натуральное число. Функция вида f : V ^ {1,..., k} называется вершинной k-раскраской графа G, f (v) -цветом вершины v Е V, а граф G, каждой вершине которого сопоставляется какой-нибудь цвет, называется цветным либо графом с цветными вершинами. Цветной граф будем обозначать G = (V, а, f). Определение 2. Изоморфизмом цветных графов G1 = (V1,a1,f1) и G2 = (V2, a2,f2) называется изоморфизм графов G1 = (V1,a1) и G2 = (V2,a2), сохраняющий цвета, т.е. биекция ^ : V1 ^ V2, при которой выполняются следующие два условия: 1) V u, v Е Vl ((u, v) Е а1 ^ (

Скачать электронную версию публикации