On the number of minimal vertex and edge 1-extensions of cycles.pdf Дж. П. Хейз в работе [1], а затем вместе с Ф. Харари в работах [2, 3] предложил гра-фовую модель для исследования отказоустойчивости дискретных систем. Особое вни-мание было уделено системам, представимым циклами. В работах [1-3] предложенысхемы построения одной оптимальной отказоустойчивой реализации (минимальногорасширения) цикла; другие схемы предложены в [4-7].Граф G* = (V*,а*) называется минимальным вершинным k-расширением (k на-туральное) n-вершинного графа G = (V, а), если выполняются следующие условия:1) граф G* является вершинным k-расширением G, то есть граф G вкладываетсяв каждый подграф графа G*, получающийся удалением любых его k вершин;2) граф G* содержит n + k вершин, то есть |V* | = |V| + k;3) а* имеет минимальную мощность при выполнении условий 1 и 2.Граф G* = (V*,а*) называется минимальным рёберным k-расширением (k нату-ральное) n-вершинного графа G = (V, а), если выполняются следующие условия:1) граф G* является рёберным k-расширением G, то есть граф G вкладываетсяв каждый подграф графа G*, получающийся удалением любых его k рёбер;2) граф G* содержит n вершин, то есть |V*| = |V|;3) а* имеет минимальную мощность при выполнении условий 1 и 2.Если говорить о минимальных вершинных и рёберных k-расширениях циклов, томожно встретить эквивалентные определения.Граф называется k-вершинно-гамильтоновым, если после удаления любых егоk вершин и инцидентных им рёбер получившийся граф является гамильтоновым. Графназывается k-рёберно-гамильтоновым, если после удаления любых k рёбер получив-шийся граф является гамильтоновым. Вершинно^рёберно-^-гамильтонов граф назы-вается оптимальным, если он имеет минимально возможное число рёбер среди всехвершинно^рёберно-^-гамильтоновых графов с тем же числом вершин.Известно, что задачи проверки вершинных (рёберных) k-расширений произволь-ных графов, так же как и задачи проверки k-вершинно-(рёберно-)гамильтоновыхграфов являются NP-полными [8]. Интерес представляет количество неизоморфныхрасширений для различных графов. В 2000 г. проведён вычислительный экспери-мент [6-9], в рамках которого удалось построить все минимальные вершинные и рё-берные 1-расширения циклов с числом вершин до 13. В рамках представляемой работыпроведён новый вычислительный эксперимент с использованием распределённых вы-числений. Удалось построить все минимальные вершинные и рёберные 1-расширенияциклов с числом вершин до 17. Основные результаты представлены в таблице.Минимальные вершинные (МВ-1Р)и рёберные (МР-1Р) 1-расширения цикловЧисло вершин Число МВ-1Р Число МР-1Р3 1 14 1 15 1 16 2 27 2 28 10 49 7 1310 63 1311 27 8712 602 5313 158 88514 7203 32015 1396 1093316 104212 264117 16069 160145

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