Minimal extensions for cycles with vertices of two types.pdf Неориентированным графом называется пара G = (V, а), где а - симметричноеи антирефлексивное отношение смежности на множестве вершин V. Здесь и далееосновные определения даются по работе [1].Будем рассматривать неориентированные графы, в которых вершины имеют раз-ные типы или окрашены в разные цвета.Вложением графа G1 = (V1,a1) в граф G2 = (V2,a2) называется взаимно одно-значное отображение ^ : V1 ^ V2, при котором сохраняются типы вершин и для всехu,v Е Vl выполняется условие: если (u,v) Е а1, то (^(u),^(v)) Е а2.Граф G* = (V*, а*) называется минимальным вершинным k-расширением (МВ^Р)n-вершинного графа G = (V, а) с вершинами p типов, если выполняются следующиеусловия:1) G* является вершинным k-расширением G, то есть граф G вложйм в каждыйподграф графа G*, получающийся удалением любых его k вершин;2) G* содержит n + k p вершин;3) а* имеет минимальную мощность при выполнении условий 1 и 2.Отказоустойчивость - способность системы противостоять ошибке и возмож-ность продолжать работу в присутствии этой ошибки. Дж. П. Хейз в работе [2] пред-ложил графовую модель для построения отказоустойчивых реализаций заданной си-стемы. Он рассмотрел минимальные вершинные k-расширения для цепей и цикловс однотипными вершинами, а также минимальные вершинные 1-расширения деревьевс вершинами разного типа. В данной работе рассматриваются циклы с вершинамидвух типов: одна вершина первого типа, а остальные вершины - другого типа. Уда-лось получить следующие результаты.Теорема 1. Минимальные вершинные 1 -расширения цикла Cn с вершинами двухтипов (одна вершина первого типа, а остальные вершины - другого типа) имеют(3n + 4)/2 ребер при четном n и (3n + 5)/2 - при нечетном n.Теорема 2. Одно из минимальных вершинных 1-расширений цикла Cn с верши-нами двух типов (одна вершина первого типа, а остальные вершины - другого типа)имеет вид, показанный на рис. 1,а для n = 4k; на рис. 1,б -для n = 4k + 2; на рис. 2,а -для n = 4k + 1 и на рис. 2,б -для n = 4k + 3.Выполнен компьютерный эксперимент, в результате которого сгенерированы всенеизоморфные минимальные вершинные 1-расширения рассматриваемых цикловс числом вершин до 8. Полученные данные представлены в таблице.Рис. 1. МВ-1Р цикла Cn при чётных nРис. 2. МВ-1Р цикла Cn при нечётных nКоличество минимальных вершинных 1-расширений Cnаа|V | m Количество МВ-1Р3 8 14 8 15 11 76 11 17 14 608 14 2

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