On minimal extensions of special type black-white paths.pdf Определение 1. Граф G* = (V*,а*) называется минимальным вершиннымk-расширением [1,2] n-вершинного графа G = (V, а) с вершинами p типов, если вы-полняются следующие условия:1) граф G* является вершинным k-расширением графа G, то есть граф G вложимв каждый подграф графа G*, получающийся удалением любых его k вершин;2) граф G* содержит n + kp вершин, то есть |V* | = |V| + kp;3) а* имеет минимальную мощность при выполнении условий 1 и 2.Определение 2. Граф G* = (V*,а*) называется минимальным рёбернымk-расширением [3] n-вершинного графа G = (V, а) с вершинами p типов, если вы-полняются следующие условия:1) граф G* является рёберным k-расширением графа G, то есть граф G вложимв каждый граф, получающийся из G* удалением любых его k рёбер;2) граф G* содержит n вершин, то есть |V*| = |V|;3) а* имеет минимальную мощность при выполнении условий 1 и 2.Вершины разных типов можно изображать различными цветами. Будем рассмат-ривать минимальные вершинные и рёберные 1-расширения черно-белых неориентиро-ванных графов, в которых вершины имеют два типа: p = 2 (белые и чёрные вершины).В результате вычислительного эксперимента построены все минимальные вершин-ные и рёберные 1-расширения черно-белых цепей, в которых две белые вершины имеютстепень 1, а чёрные - степень 2 (то есть белые вершины на концах цепи), с количествомвершин до 9.Теорема 1. Минимальные вершинные расширения цепей Pn с вершинами двухтипов, в которых белые вершины имеют степень 1, а чёрные - степень 2, содержатm = 3k рёбер при чётном n = 2k, и одно из минимальных 1-вершинных расшире-ний имеет вид, показанный на рис. 1,а. При нечётном n = 2k + 1 количество рёберm = 3k + 2, и одно из минимальных вершинных расширений имеет вид, показанныйна рис. 1,б.Рис. 1. Минимальное вершинное расширение PnТеорема 2. Минимальные рёберные расширения цепей Pn с вершинами двух ти-пов, в которых белые вершины имеют степень 1, а чёрные - степень 2, содержатm = 3k - 1 рёбер при чётном n = 2k, и одно из минимальных рёберных расшире-ний имеет вид, показанный на рис. 2,а (для чётного k) и рис. 2,б (для нечётного k).При нечётном n = 2k + 1 количество рёбер m = 3k + 1, и одно из минимальныхрёберных расширений имеет вид, показанный на рис. 2,в.При этом минимальные рёберные расширения, показанные на рис. 2,а и б, в тоже время являются минимальными вершинными расширениями циклов с вершинамидвух типов - одной белой вершиной и остальными чёрными - с количеством вершинна 2 меньшим, чем в расширениях.Рис. 2. Минимальное рёберное расширение Pn

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