On digraphs with a small number of arcs in a minimal 1-vertex extension.pdf Понятие минимального вершинного k-расширения введено на основе понятия опти-мальной k-отказоустойчивой реализации, которое предложено Дж. П. Хейзом [1]. В ра-боте [2] исследована задача описания неориентированных графов с заданным числомдополнительных рёбер минимальных вершинных 1-расширений. В данной работе рас-сматривается аналогичная задача для орграфов без петель. В [3] приводится лемма,устанавливающая связь между минимальными вершинными k-расширениями неори-ентированного графа и его ориентации.Лемма 1 [3]. Пусть G* есть минимальное вершинное k-расширение орграфа G.Тогда симметризация G* является вершинным k-расширением симметризации G.Следствие 1. Число дополнительных дуг минимального вершинного k-расши-рения орграфа G не менее числа дополнительных рёбер минимального вершинногоk-расширения симметризации орграфа G.В работе [2] получены следующие результаты (теоремы 1-3).Теорема 1. Графы со степенным множеством {1, 0}, и только они, имеют ми-нимальные вершинные 1-расширения с одним дополнительным ребром; для каждогографа со степенным множеством {1, 0} такое расширение единственно с точностью доизоморфизма.С учётом следствия 1 получаем, что только ориентации графов из теоремы 1 могутиметь минимальные вершинные 1-расширения с одной дополнительной дугой.Теорема 2. Среди связных графов только цепи имеют минимальные вершинные1-расширения с двумя дополнительными рёбрами; для каждой цепи такое расширениеединственно с точностью до изоморфизма.С учётом следствия 1 получаем, что только ориентации графов из теорем 1-2 мо-гут иметь минимальные вершинные 1-расширения с двумя дополнительными дугами.Оказывается, что ориентация цепи имеет две дополнительные дуги в минимальномвершинном 1-расширении, только если цепь является гамильтоновой. Минимальнымвершинным 1-расширением такой цепи является контур.Теорема 3. Среди несвязных графов без изолированных вершин только графывида Pn U Cn + 1 U . . . U Cn + 1 при n > 1 имеют минимальные вершинные 1-расширенияс двумя дополнительными рёбрами, причём это расширение с точностью до изомор-физма совпадает с Cn + 1 U Cn + 1 U . . . U Cn+1.С учётом следствия 1 получаем, что только ориентации графов из теорем 1-3 могутиметь минимальные вершинные 1-расширения с двумя дополнительными дугами.Удалось получить следующие результаты.Теорема 4. Орграфы, полученные объединением n двухвершинных цепей с m изо-лированными вершинами, где m > 0, и только они имеют минимальные вершинные1-расширения с одной дополнительной дугой. Каждый такой орграф имеет единствен-ное с точностью до изоморфизма минимальное вершинное 1-расширение.Теорема 5. Среди связных орграфов гамильтоновы цепи Pn, и только они, имеютдве дополнительные дуги в минимальном вершинном 1-расширении. При n > 2 каж-дая цепь имеет единственное с точностью до изоморфизма минимальное вершинное1-расширение. При n = 2 цепь имеет два неизоморфных минимальных вершинных1-расширения: циклическую и транзитивную тройки.Теорема 6. Среди несвязных орграфов без изолированных вершин только ор-графы вида Pn U Cn + 1 U . . . U Cn + 1 при n > 2, где циклы являются контурами, а цепь -гамильтоновой цепью, имеют единственное с точностью до изоморфизма минималь-ное вершинное 1-расширение с двумя дополнительными дугами. При n = 2 возможенещё один случай: вместо контура C3 можно взять транзитивную тройку T3. ГрафP2 U T3 U . . . U T3 также имеет единственное с точностью до изоморфизма минимальноевершинное 1-расширение с двумя дополнительными дугами.На рис. 1 представлена схема построения семейства графов из теоремы 6 и их ми-нимальных вершинных 1-расширений.т т + 1Рис. 1. Орграф и его минимальное вершинное 1-расширениес двумя дополнительными дугами

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