«ГРАФОВЫЕ МОДЕЛИ ОТКАЗОУСТОЙЧИВОСТИ ...»

В работе (Harary, Hayes, 1993) авторы предложили процедуру для построения минимального реберного k-расширения цикла. Большинство схем построения минимальных вершинных 1-расширений, которые были рассмотрены в главе 2, позволяют строить и минимальные реберные 1-расширения для циклов с числом вершин на 1 больше.

ТЕОРЕМА 3.4.1 (Harary, Hayes, 1993). Минимальное реберное 1-расn + ширение n-вершинного цикла Cn содержит не менее дополнительных ребер.

Доказательство. Пусть граф G* = (V*, *) является минимальным реберным 1-расширением n-вершинного цикла Cn. Согласно лемме 3.1.2 степень каждой вершины в графе G* не ниже 3, а при нечетном значении n степень одной из вершин в силу теоремы о необходимой четности суммы степеней вершин будет строго больше 3. Таким образом, можно записать Поскольку число ребер n-вершинного цикла равно n, то, объединяя оба случая, получаем требуемую оценку снизу для числа дополнительных ребер минимального вершинного 1-расширения цикла.

ТЕОРЕМА 3.4.2 (Harary, Hayes, 1993). Гамильтоновы графы, изображенные на рис. 3.4.1, представляют собой минимальные реберные 1-расширения n-вершинного цикла при n четном (рис. 3.4.1, а) и n нечетном (рис. 3.4.1, б).

Данные схемы совпадают со схемами построения минимальных вершинных 1-расширений из теоремы 2.4.2. На рис. 3.4.2 представлены минимальные реберные 1-расширения малых целых, построенных по схеме из теоремы 3.4.2.

Рис. 3.4.2. МР-1Р циклов C5 (а), C6 (б), C7 (в), C8(г), C9(д) и C10(е) Следствие 1. Минимальное реберное 1-расширение n-вершинного цикла имеет вектор степеней (3,3,…,3) при четном n и (4,3,…,3), при нечетном n.

Следствие 2. Минимальное реберное 1-расширение n-вершинного цикла Cn содержит в точности ребер или дополнительных ребер.

Схемы Махопадхья и Синха, которые были рассмотрены в теореме 2.4.3 главы 2, позволяют строить как вершинные, так и реберные минимальные 1-расширения:

ТЕОРЕМА 3.4.3 (Mukhopadhyaya, Sinha, 1992). Графы M(k) являются минимальными вершинными и реберными 1-расширениями соответствующего цикла при k 4.

На рис. 2.4.4 и 2.4.5 можно посмотреть минимальные реберные 1-расширения циклов, построенные по схемам Махопадхья и Синха. Нужно учитывать, что граф M(k) является минимальным вершинным 1-расширением для цикла с числом вершин n – 1 и минимальным реберным 1-расширением справедлива ТЕОРЕМА 3.4.4. Графы M(k) и H(k) при k = 7 и k > 8 неизоморфны.

Далее в главе 2 было рассмотрено семейство W(k) (см. теорему 2.4.5).

ТЕОРЕМА 3.4.5 (Ванг, Хунг и Хсу, 1998). Графы W(k) являются минимальными вершинными и реберными 1-расширениями соответствующего цикла при k 1.

Напомним, что семейство W(k) дает минимальные вершинные 1-расширения цикла Cn при n = 11, 29, 55, 89, …, а минимальные реберные 1-расширения при n = 12, 30, 56, 90, … Семейство CT(s) (см. теорему 2.4.6) также позволяет строить минимальные реберные 1-расширения некоторых циклов.

ТЕОРЕМА 3.4.6 (Хунг, Хсу и Санг, 1999). Графы CT(k) являются минимальными вершинными и реберными 1-расширениями соответствующего цикла при k 1.

Семейство CT(k) дает минимальные вершинные 1-расширения цикла Cn при n = 10, 22, 46, 94, … Заметим, что схемы построения минимальных вершинных 1-расширений из теоремы 2.4.7 в общем случае не дают минимальные реберные 1-расширения. В работе (Абросимов, 2004) было предложено новое семейство минимальных реберных 1-расширений для циклов с любым числом вершин.

ТЕОРЕМА 3.4.7. Гамильтоновы графы, изображенные на рис. 3.4.3, представляют собой минимальные реберные 1-расширения n-вершинного (n > 3) цикла при n четном (рис. 3.4.3, а) и n нечетном (рис. 3.4.3, б).

Доказательство. Обозначим через A(n) n-вершинный граф, построенный по рассматриваемым схемам. Покажем, что графы A(n) являются минимальными реберными 1-расширениями соответствующих циклов. Непосредственной проверкой убеждаемся, что графы являются реберными 1-расширениями циклов.

Рассматриваемые графы имеют такое же количество ребер, что и соответствующие графы из теоремы 3.4.2, следовательно, они являются и минимальными реберными 1-расширениями.

На рис. 3.4.4 представлены минимальные реберные 1-расширения некоторых циклов, построенные по схемам из теоремы 3.4.7.

Заметим, что при n 5 построенные графы изоморфны построениям Харари и Хейза. Покажем, что при n > 5 рассмотренные графы неизоморфны соответствующим графам из теоремы 3.4.2.

Рис. 3.4.4. МР-1Р циклов C5 (а), C6 (б), C7 (в), C8 (г), C9 (д) и C10 (е) ТЕОРЕМА 3.4.8. Графы A(n) и H(n) при n > 6 неизоморфны.

Доказательство. Для четного n = 2k имеем графы A(2k) и H(2k), представленные на рис. 3.4.1, а и 3.4.3, а. Видно, что граф H(2k) содержит два цикла длины 3: vn/2+1v1v2 и vnvn-1vn/2, что возможно в графе A(2k) лишь при n = 4.

Для нечетного n = 2k + 1 имеем графы A(2k + 1) и H(2k + 1), представленные на рис. 3.4.1, б и 3.4.3, б. Видно, что единственная вершина степени в графе A(2k + 1) является вершиной двух треугольников с общей стороной:

vn/2vn-1vn и vn/2vn-1vn-2, а в графе H(2k + 1) такое возможно лишь при n = 5.

ТЕОРЕМА 3.4.9. Графы A(n) и M(n) при n > 7 неизоморфны.

Доказательство. Для нечетного n = 2k + 1 имеем графы A(2k + 1) и M(2k + 1). Видно, что единственная вершина степени 4 в графе A(2k + 1) является вершиной двух треугольников с общей стороной: vn/2vn+1vn и vn/2vn-1vn, а в графе M(2k + 1) такое возможно лишь при n = 5 и n = 7.

Для четного n = 2k имеем графы A(2k) и M(2k). Видно, что граф M(2k) содержит циклы длины 3, а граф A(2k) при n > 4 циклов длины 3 не содержит.

Таким образом, имеет место следующая ТЕОРЕМА 3.4.10. Любой цикл Cn при n > 5 имеет, по крайней мере, два неизоморфных минимальных реберных 1-расширения.

Аналогичный результат имеет место и для минимальных вершинных 1расширений циклов (см. теорему 2.4.10).

Схемы, описанные в теоремах 3.4.2-3.4.6, позволяют строить графы, являющиеся как минимальными реберными 1-расширениями цикла, так и минимальными вершинными 1-расширениями цикла с числом вершин на одну меньше. Графы, построенные по схеме, представленной на рис. 3.4.3, б, обладают этим же свойством. Схема, представленная на рис. 3.4.1, а, позволяет строить лишь минимальные реберные 1-расширения цикла. В табл. 3.4.1 показаны минимальные вершинные и реберные 1-расширения циклов с числом вершин 5, 6 и 7.

Видно, что одно из двух минимальных реберных 1-расширений 6-вершинного цикла (см. рис. 3.4.1, а) является также и минимальным вершинным 1-расширением 5-вершинного цикла, а оба минимальных реберных 1-расширения 7-вершинного цикла (см. рис. 3.4.1, б и 3.4.3, б) являются также и минимальными вершинными 1-расширениями 6-вершинного цикла. С помощью произведенных на компьютере вычислений по сопоставлению графов, являющихся минимальными реберными 1-расширениями и минимальными вершинными 1-расширениями циклов, были получены данные, представленные в табл. 3.4.2 (в 1999-2000 г. автором были обработаны циклы с числом вершин до 13, последующие результаты получены в 2012 г.

Н. А. Кузнецовым):

В первом столбце указывается цикл, во втором – вектор степеней его минимального вершинного 1-расширения, в третьем – количество неизоморфных минимальных вершинных 1-расширений, в четвертом и пятом столбцах приводится аналогичная информация относительно минимальных реберных 1-расширений. В последнем столбце указывается количество минимальных реберных 1-расширений, являющихся также и минимальными вершинными 1-расширениями цикла с числом вершин на единицу меньшим.

Из таблицы видно, что существуют минимальные 1-расширения, как вершинные, так и реберные, которые не являются минимальными 1-расширениями, соответственно реберными или вершинными, цикла, отличающегося по числу вершин на единицу.

Наименьшим по числу вершин циклом, таким, что среди его минимальных реберных 1-расширений не присутствует минимальное вершинное 1-расширение цикла с числом вершин на единицу меньшим, является 10вершинный цикл, а соответстующим минимальным вершинным 1-расширением цикла C9 является граф Петерсена, изображенный на рис. 2.4.11 (заметим, что этот граф является негамильтоновым, то есть даже не содержит цикла Для вершинных Рис. 3.4.5. МР-1Р цикла C8 1-расширений аналогичным циклом является цикл C8, сразу 2 минимальных реберных 1-расширения которого не ла C7. Эти графы представлены на рис. 3.4.5.

3.5. Предполные графы К сожалению, полного описания минимальных реберных k-расширений предполных графов, в отличие от вершинных, пока получить не удалось. В этом параграфе рассмотрим некоторые общие свойства таких расширений, а далее применим их для описания решения в некоторых частных случаях. Для реберных k-расширений предполных графов имеет место полезная ЛЕММА 3.5.1. Пусть n-вершинный предполный граф G имеет в точности p полных вершин. Если граф G имеет минимальное реберное k-расширение, то оно содержит не менее p + 2k полных вершин.

Доказательство. Пусть G* – минимальное реберное k-расширение графа G с p полными вершинами. Рассмотрим граф G, получающийся из G* удалением следующих k ребер: в качестве очередного ребра удаляем а) ребро, соединяющее две полные вершины. Если таких ребер нет, то б) ребро, инцидентное полной вершине (это возможно, только если останется единственная полная вершина). Если нет ребер из пунктов а) и б), то в) любое ребро.

Очевидно, что если среди выбранных ребер окажется хотя бы одно ребро из пунктов б) или в), то получившийся граф не будет полным и не будет допускать вложения исходного графа G. Таким образом, граф G должен содержать не менее p полных вершин и получаться из графа G* удалением k ребер, соединяющих полные вершины графа G*. После удаления каждого такого ребра количество полных вершин уменьшается на две, что и доказывает утверждение.

Следствие 1. Пусть n-вершинный предполный граф G имеет в точности p полных вершин, тогда граф G не имеет минимальных реберных k-расn p Следствие 2. Пусть n-вершинный предполный граф имеет вид Kp + Gn.

Если он имеет минимальное реберное k-расширение, то оно имеет вид Kp+2k + Gn–2k, где Gn–2k – подходящий (n – 2k)-вершинный граф.

Соединение полного графа и цепи: Km + Pn Напомним, что n-вершинное дерево, все вершины которого имеют степень не более двух, называется цепью и обозначается Pn. Одновершинная цепь P1 называется тривиальной. Будем говорить, что n-вершинный граф G может быть покрыт (не более чем) p цепями, если существует n-вершинный граф, являющийся объединением (не более чем) p цепей и вкладывающийся в граф G. Например, полный граф Kn может быть покрыт одной цепью, а вполне несвязный граф On может быть покрыт n цепями (тривиальными).

При n 2 граф Km + Pn изоморфен графу Km+n и не имеет минимальных реберных расширений. Пусть далее n > 2, и рассмотрим граф Km+2 + G, где G – (n – 2)-вершинный граф, такой, что любой граф, получающийся из G удалением одного ребра, можно покрыть не более чем тремя цепями. Обозначим для определенности вершины подграфа Km+2 графа Km+2 + G через v1, …, vm+2.

Покажем, что Km+2 + G является реберным 1-расширением для Km +Pn. Заметим, что ребра графа Km+2+G можно разделить на три типа:

ребра, соединяющие полные вершины v1, …, vm+2;

ребра, соединяющие полную вершину v1, …, vm+2 и вершину подграфа ребра, соединяющие вершины подграфа G.

Рассмотрим удаление из Km+2 + G ребра типа 1. Пусть для определенности удалено ребро {v1,v2}. Поскольку часть графа G допускает покрытие не более чем тремя цепями, то, очевидно, и сам граф G может быть покрыт тремя цепями. Рассмотрим худший случай, когда для покрытия необходимы три цепи. Пусть цепи Pn 1, Pn 2 и Pn 3 образуют покрытие графа G. Вложение графа Km + Pn в Km+2 + G – {v1,v2} возможно следующим образом. Полные вершины – v3, …, vm+2, а оставшиеся вершины образуют цепь: Pn1 v1Pn2 v2 Pn3.

Рассмотрим удаление из Km+2 + G ребра типа 2. Пусть снова цепи Pn 1, Pn 2 и Pn 3 образуют покрытие графа G. Пусть для определенности удалено ребро, соединяющее вершину v1 с некоторой вершиной w цепи Pn 1. Вложение графа Km + Pn в Km+2 + G – {v1,w} возможно следующим образом. Полные вершины – v3, …, vm+2, а оставшиеся вершины образуют цепь: Pn1 v2 Pn2 v1 Pn3.

Рассмотрим удаление из Km+2 + G ребра типа 3. Пусть для определенности удалено ребро, соединяющее вершины v и w. По условию граф G – {v,w} допускает покрытие не более чем тремя цепями, и пусть это снова будут Pn 1, Pn 2 и Pn 3. Вложение графа Km + Pn в Km+2 + G – {v,w} возможно следующим образом. Полные вершины – v3, …, vm+2, а оставшиеся вершины образуют цепь: Pn1 v1Pn2 v2 Pn3.

Заметим, что условие покрытия графа G с удаленным ребром тремя цепями является существенным, так как более трех цепей нельзя объединить в одну с помощью двух дополнительных вершин. Таким образом, граф Km+2 + G является реберным 1-расширением графа Km + Pn.

Исследуем свойства графа G:

любой граф, получающийся из G удалением одного ребра, можно покрыть не более чем тремя цепями;

граф, получающийся из G удалением одного ребра, имеет не более трех компонент связности, а следовательно, сам граф G имеет не более двух компонент связности.

Рассмотрим граф, являющийся объединением двух цепей: Pn1 Pn2. При удалении любого ребра такой граф распадется на три цепи. Таким образом, объединение двух цепей может быть использовано в качестве графа G, причем число ребер в таком графе есть n – 4. Заметим, что Pn1 Pn2 отличается в точности на одно ребро от объединения трех цепей. С учетом леммы получаем, что минимальное реберное 1-расширение графа Km + Pn имеет вид Km+2 + G, где G – (n – 2)-вершинный граф, каждая часть которого, получающаяся удалением одного ребра, может быть покрыта не более чем тремя цепями. Рассмотрим, какие графы удовлетворяют условиям 1–3 для nвершинного графа G:

объединение двух цепей: Pn1 Pn2, n1 + n2 = n, 1 n1 n2 n–1. Таких графов будет n/2;

при n 5: цикл и две изолированные вершины: O2 C n 2 ;

Из всего сказанного получается следующая теорема.

ТЕОРЕМА 3.5.1. Относительно минимальных реберных 1-расширений предполных графов вида Km + Pn справедливо следующее:

– при n = 1, 2 минимальных реберных 1-расширений нет;

– при n = 3 минимальное реберное 1-расширение единственно: Km+3;

– при n 4 существует (n/2 – 1) минимальных реберных 1-расширений – при n = 7 имеется минимальное реберное 1-расширение вида – при n 7 имеется минимальное реберное 1-расширение вида Следствие. Число дополнительных ребер в минимальном реберном 1расширении графа Km + Pn при n > 3 составляет 2n – 6.

Доказательство. При n > 3 одно из минимальных реберных 1-расшиKm+2 + ( Pn1 Pn2 ), 1 n1 n2 n – 3. Определим число его ребер.

Km+2 содержит (m + 2)(m + 1)/2 ребер.

Каждая вершина из Km+2 соединена с каждой из n – 2 вершин объединения Pn1 Pn2, что дает (m + 2)(n – 2) ребер.

Складывая, получаем (m + 2)(m + 1)/2 + n – 4 + (m + 2)(n – 2).

Граф Km + Pn содержит m(m – 1)/2 + n – 1 + mn ребер. Таким образом, число дополнительных ребер составляет 2n – 6.

На рис. 3.5.1 представлены граф K1 + P7 и его минимальные реберные 1-расширения. Полные вершины обозначены черными точками. Для наглядности некоторые ребра, соединяющие полные вершины с остальными, опущены.

Рис. 3.5.1. Граф K1 + P7 и все его минимальные реберные 1-расширения Теорему 3.5.1 можно обобщить:

ТЕОРЕМА 3.5.2. Относительно минимальных реберных k-расширений предполных графов вида Km + Pn справедливы утверждения:

– при n 2k минимальных реберных 1-расширений нет;

– при 2k < n 4k + 1 минимальное реберное 1-расширение единственно:

– при n > 4k + 1 минимальные реберные расширения имеют вид где Gn-2k – (n – 2k)-вершинный граф с n – 3k – 1 ребрами, такой, что после удаления любых его k-ребер оставшаяся часть может быть покрыта не более чем 2k + 1 цепями.

Доказательство. Первое утверждение теоремы вытекает из следствия 1 леммы 3.5.1.

Из леммы 3.5.1 следует, что если граф K1 + Pn имеет минимальное реберное k-расширение, то оно имеет вид K2k+m + G, где G есть (n – 2k)-вершинный граф. Обозначим для определенности через v1,…, v2k+m полные вершины K2k+m + G из части K2k+m. Рассмотрим граф, получающийся после удаления k ребер из графа K2k+m + G. В нем останется, по крайней мере, m полных вершин, пусть для определенности это будут вершины v2k+1,…,v2k+m. Оставшиеся вершины должны образовывать цепь. Обозначим через K* подграф, образованный из вершин v1,…, v2k, а через G* – подграф, образованный из вершин графа G. Для построения цепи имеется 2k вершин v1,…, v2k и вершины подграфа G*. Граф K2k является (2k – 1)-связным, поэтому удаление из него любых k ребер его связности не нарушит. Предположим, что подграф G* можно покрыть не более чем 2k + 1 цепями: Pn 1, …, Pnl. Тогда легко построить n-вершинную цепь, соединяя концы цепей Pn 1, …, Pnl вершинами v1,…, v2k. Если же подграф G* нельзя покрыть не более чем 2k + 1 цепями, то nвершинную цепь построить невозможно.

Заметим, что минимальным по числу ребер p-вершинным графом, который удовлетворяет приведенному условию, при p 2k + 1 является вполне несвязный граф Op, а при p > 2k + 1 – объединение k + 1 цепей: Pn 1, …, Pnk +1. В самом деле, удаление одного ребра разбивает цепь на две цепи, следовательно, удаление k ребер приведет к образованию 2k + 1 цепей. Легко подсчитать и число ребер в p-вершинном графе, являющемся объединением k + 1 цепей:

На рис. 3.5.2 представлены минимальные реберные 2-расширения для графов K1 + P11. По-прежнему полные вершины обозначаются черными точками и для наглядности некоторые ребра, соединяющие полные вершины с остальными, опущены.

Соединение полного графа и цикла: Km + Cn Связный n-вершинный граф, все вершины которого имеют степень 2, называется циклом и обозначается Cn. Очевидно, что цикл не может иметь менее 3 вершин.

ТЕОРЕМА 3.5.3. Относительно минимальных реберных 1-расширений графа Km + Cn справедливы следующие утверждения:

– при n = 3 минимальных реберных 1-расширений нет;

– при n = 4 имеется единственное минимальное реберное 1-расширение: Km+2 + O2;

– при n 5 одно из минимальных реберных 1-расширений имеет вид – при n = 6 одно из минимальных реберных 1-расширений имеет вид – при n 6 одно из минимальных реберных 1-расширений имеет вид – других минимальных реберных 1-расширений с точностью до изоморфизма у графа Km + Cn нет.

Доказательство. При n = 3 граф Km + Cn является полным графом Km+n и поэтому минимальных реберных 1-расширений не имеет. Далее рассмотрим случай n > 3.

По лемме, если граф Km + Cn имеет минимальное реберное 1-расширение, то его можно представить в виде Km+2 + Gn-2. Обозначим для определенности через v1,…, vm+2 полные вершины в части Km+2, а через u1, …, un- вершины части Gn-2.

Убедимся, что при n > 3 граф Km+2 + Pn-2 является реберным 1-расширением графа Km + Cn. Аналогично доказательству теоремы 3.5.1 все ребра разделим на три типа: ребра внутри Km+2, ребра внутри Pn-2 и ребра, соединяющие вершины из Km+2 и из Pn-2. Заметим, что при удалении ребра любого типа остается, по крайней мере, m полных вершин, поэтому достаточно убедиться, что остальные вершины образую n-вершинный цикл. Рассмотрим удаление ребра каждого типа.

При удалении ребра, например {v1,v2}, в части Km+2 остаются полные вершины v3,…,vm+2, а остальные вершины образуют цикл: v1, u1, v2, u2, …, un-2, v1.

При удалении ребра в части Pn-2 эта цепь распадается на две цепи: Pn 1 и Pn 2. Полные вершины – v3,…,vm+2, а остальные вершины образуют цикл: v1, P1, v2, P2, v1.

При удалении ребра, соединяющего вершину из Km+2 и из Pn-2, например {v1,up}, где 1 p n – 2, остаются полные вершины v3,…,vm+2, а остальные вершины образуют цикл: или v1, u1, u2, …, un-2, v2, v1 (если p 1), или v2, u1, …, un-2, v1, v2 (если p = 1).

Таким образом, при n > 3 граф Km+2 + Pn-2 действительно является реберным 1-расширением графа Km + Cn.

Пусть Km+2 + Gn-2 является минимальным реберным 1-расширением графа Km + Cn. Тогда граф Gn-2 содержит не более n – 3 ребер. Рассмотрим удаление произвольного ребра e в Gn-2. По предположению вершины графа Gn-2 вместе с двумя полными вершинами образуют цикл, следовательно, граф Gn-2 – e содержит не более двух компонент связности и может быть покрыт двумя цепями. Первое условие означает, что число ребер в Gn-2 не менее n – 3. Поскольку цепь Pn-2 содержит в точности n – 3 ребра, то граф Km+2 + Pn- является минимальным реберным 1-расширением графа Km + Cn, а любое другое минимальное реберное 1-расширение, если оно есть, имеет вид Km+2 + Gn-2, где граф Gn-2 имеет n – 2 вершин и n – 3 ребер. Так как граф Gn-2 – e содержит не более двух компонент связности, то граф Gn-2 либо состоит из одной компоненты связности и тогда является деревом, либо из одной (n – 3)вершинной двусвязной компоненты с n – 3 ребрами, то есть цикла, и одной изолированной вершины.

Исследуем, каким может быть дерево в нашем случае. Покажем, что оно не может иметь более трех листьев. Предположим, что это не так, и граф Gn-2 является деревом с более чем тремя листьями. Рассмотрим граф, получающийся удалением из Gn-2 ребра при некотором листе v. Получим дерево с числом вершин на одну меньше и не менее чем с тремя листьями и изолированную вершину: Tn-3 O1. По условию граф K2 + (Tn-3 O1) должен содержать n-вершинный цикл. Вершина v в этом цикле должна соседствовать с обеими полными вершинами v1 и v2. Другим соседом полной вершины v1 будет один из листьев дерева. Далее последует цепь (единственная) до другого листа, затем вершина v2. Оставшиеся листья не могут быть присоединены к циклу. Таким образом, дерево не может иметь более трех листьев. Один лист может иметь только тривиальное дерево (состоящее из одной вершины). Если листа два, то получаем рассмотренный ранее случай цепи.

Исследуем случай трех листьев. В этом случае дерево, очевидно, имеет одну вершину степени 3, три вершины степени 1 и может иметь несколько вершин степени 2. Однако если хотя бы один лист не смежен с вершиной степени 3, то, удалив ребро при таком листе, мы опять получим граф вида TnO1. Повторяя предыдущие рассуждения, получим противоречие. Следовательно, деревом с тремя листьями может быть лишь 4-вершинная звезда K1 + O3.

Итак, граф Gn-2 может иметь вид O1 Cn-3, или Pn-2, или K1 + O3.

Таким образом, графы K1 + C4 и K1 + C5 имеют единственное минимальное реберное 1-расширение, граф K1 + C6 имеет три минимальных реберных 1-расширения, а при n > 6 граф K1 + Cn имеет два минимальных реберных 1-расширения. На рис. 3.5.3 представлены все минимальные реберные 1-расширения для графа K1 + C6. Как и ранее, полные вершины обозначаются черными точками, и для наглядности некоторые ребра, соединяющие полные вершины с остальными, опущены.

Очевидным образом теорема обобщается:

ТЕОРЕМА 3.5.4. Относительно минимальных реберных k-расширений предполных графов вида Km + Сn справедливо следующее:

– при n 2k минимальных реберных 1-расширений нет;

– при 2k < n 4k минимальное реберное 1-расширение единственно:

– при n > 4k минимальные реберные расширения имеют вид где Gn-2k – (n – 2k)-вершинный граф с n – 3k – 1 ребрами, такой, что после удаления любых его k ребер оставшаяся часть может быть покрыта не более чем 2k цепями.

В табл. 3.6.1 представлены минимальные реберные 1-расширения для малых деревьев с числом вершин до 5. Последующие далее в этом параграфе результаты позволяют построить минимальное реберное 1-расширение для двух частных случаев деревьев – звезд и сверхстройных деревьев особого вида.

3.6.1. Звёзды Звезда является частным случаем предполного графа и может быть записана в виде Km + On, где On – вполне несвязный граф. По лемме 3.5.1 число полных вершин минимального реберного k-расширения графа Km + On должно быть не менее m + 2k, следовательно, при n < 2k граф Km + On не имеет минимального реберного k-расширения. Заметим, что при n 2k граф вида Km+2k + On-2k является расширением графа Km + On, а с учетом леммы 3.5.1 и следствий из неё получаем следующее утверждение.

ТЕОРЕМА 3.6.1. При k n/2 граф Km+2k + On-2k является единственным минимальным реберным k-расширением графа Km + On. При k > n/2 граф Km + On не имеет минимальных реберных k-расширений.

На рис. 3.6.1 показаны минимальные реберные 1-расширения звезд K1 + O2 и K1 + O3. Для наглядности полные вершины помечены черным.

3.6.2. Сверхстройные деревья Далее мы получим нижнюю оценку на количество дополнительных стройного дерева и покажем, что эта оценка является достижимой, указав специальное семейство сверхстройных деревьев, минимальные реберные 1расширения которых имеют соответствующее число дополнительных ребер.

Пусть T – сверхстройное дерево с вектором цепей (m1,…,mk), k > 2, и с вектором степеней вида (k,2m,1k). Определим ограничения, которым должно удовлетворять любое минимальное реберное 1-расширение T* сверхстройного дерева T. Заметим, что 1) граф T* не может иметь вершин со степенью меньше двух, так как удаление любого инцидентного такой вершине ребра привело бы к появлению изолированной вершины;

2) граф T* не может иметь единственную вершину степени k, так как удаление любого инцидентного такой вершине ребра привело бы к графу, у которого все вершины имеет степень меньше k.

Из пункта 2 следует две альтернативы: либо в T* есть вершина степени более k, либо как минимум две вершины степени не менее k. Оценим количество дополнительных ребер в каждом из случаев.

1. Если в графе T* есть вершина степени более k, то вектор степеней графа T* будет мажорировать вектор (k + 1,2m+k). Чтобы определить минимально возможное в этом случае число дополнительных ребер, вычтем из суммы компонент этого вектора сумму степеней вершин дерева T и разделим пополам: (k + 1)/2.

2. Если в графе T* есть как минимум две вершины степени не менее k, то вектор степеней графа T* будет мажорировать вектор (k,k,2m+k–1). Чтобы определить минимально возможное в этом случае число дополнительных ребер, вычтем из суммы компонент этого вектора сумму степеней вершин дерева T и разделим пополам: k – 1.

Так как k > 2, то лишь при k = 3 схема 2 может иметь такое же количество дополнительных ребер, как и схема 1, а во всех остальных случаях больше. Таким образом, получаем ТЕОРЕМА 3.6.2. Минимальное реберное 1-расширение сверхстройного дерева T с вектором степеней (k,2,…,2) содержит не менее чем (k + 1)/2 при нечетном k и (k + 2)/2 при четном k дополнительных ребер.

Далее мы покажем, что оценки из этой теоремы не могут быть улучшены. Исследуем схему 1.

ТЕОРЕМА 3.6.3. Сверхстройное дерево T с вектором цепей (m1,…,mk) тогда и только тогда имеет минимальное реберное 1-расширение с вектором степеней (k + 1,2,…,2), отличающееся от T на (k + 1)/ дополнительных ребер, когда 1) среди его цепей есть цепи всех длин от 1 до m1 (максимальной длины цепи);

2) цепь максимальной длины m1 единственна;

3) все остальные цепи можно разбить на пары так, чтобы их длины в сумме давали m1.

Доказательство. Пусть k – нечетно и T – сверхстройное дерево с вектором цепей (m1,…mk), а G* – его минимальное реберное 1-расширение с дополнительных ребер. Заметим, что последнее условие теоремы эквивалентно тому, что концы всех цепей, кроме максимальной, могут быть длину m1 + 1.

Нетрудно видеть, что граф G*, построенный по первой схеме, представляет собой объединение циклов с общей вершиной, которую для определенности обозначим v. Построение графа G* из дерева T можно представить себе следующим образом: одна висячая вершина соединяется с корневой вершиной, а остальные висячие вершины попарно соединяются между собой.

Количество циклов в G* обозначим через t = d(v)/2 = (k + 1)/2. Длины циклов в G* обозначим через p1,…,pt. Для определенности будем считать, что m1 … mk и p1 … pt. Очевидно, что p1 m1 + 1.

графе G*. Это ребро принадлежит некоторому циклу длины pi. Если ребро инцидентно вершине v, то после удаления ребра вместо цикла появится цепь длины pi – 1. Если ребро не инцидентно вершине v, то цикл распадается на две цепи. Так как по предположению дерево T вкладывается в получившийся граф, то для каждой из этих цепей должна найтись цепь такой же длины и в дереве T. В силу произвольности выбора ребра можно сделать вывод, что в С учетом полученной ранее оценки p1 m1 + 1 получаем, что p1 = m1 + 1.

Таким образом, утверждение 1 доказано.

Предположим, что в дереве T есть несколько цепей максимальной длины m1. Так как конец только одной из этих цепей может быть соединен с корневой вершиной и образовать цикл максимальной длины p1 = m1 + 1, то концы остальных цепей длины m1 должны быть соединены с концами некоторых других цепей. Но это приведет к тому, что длины получившихся циклов будут больше, чем p1 = m1 + 1, а это противоречит предположению о том, что является максимальной длиной цикла. Таким образом, утверждение 2 доказано.

Предположим, что p1 > pt, то есть не все циклы имеют одинаковую длину p1. Рассмотрим граф, получающийся из G* удалением ребра e инцидентного вершине v из цикла минимальной длины pt, и попробуем построить вложение дерева T в получившийся граф. Вершина v в графе G* – e имеет степень k и единственным образом соответствует корневой вершине дерева. Из вершины выходит одна цепь длины pt – 1, и (k – 1)/2 циклов, из которых нужно выделить k – 1 цепей. По предположению pt – 1 < m1, то есть единственная цепь, получившаяся после удаления ребра e, не может быть цепью максимальной длины. Таким образом, один из циклов максимальной длины p1 будет содержать в себе цепь максимальной длины m1. Однако тогда остается еще (k – 3)/2 циклов, и этого недостаточно, чтобы построить вложение для оставшихся k – 2 цепей. Полученное противоречие доказывает утверждение 3, а вместе с ним и необходимость.

Достаточность. Предположим, что дерево T удовлетворяет условиям 1-3 теоремы. Построим граф G* из дерева T следующим образом: концевую вершину цепи максимальной длины m1 соединяем с корневой вершиной, а остальные концевые вершины цепей попарно соединяются между собой таким образом, чтобы длина цикла была m1 + 1: конец цепи длины соединяется с концом цепи длины m1 – 1, конец цепи длины 2 соединяется с концом цепи длины m1 – 2 и так далее. Докажем, что граф G* будет минимальным реберным 1-расширением дерева T.

Исследуем удаление произвольного ребра e из графа G*. Рассмотрим два случая.

1. Ребро e инцидентно корневой вершине v. Удаление ребра e приведет к тому, что из корневой вершины v будет выходить одна цепь длины m1 и (k – 1)/2 циклов, каждый из которых имеет длину m1 + 1. Получившаяся цепь будет соответствовать единственной цепи дерева T максимальной длины m1, а в каждом из (k – 1)/2 циклов выделим по две цепи подходящей длины, так чтобы получить оставшиеся k – 1 цепей дерева T. Вложение построено.

2. Ребро e не инцидентно корневой вершине v. Удаление ребра e приведет к тому, что из корневой вершины v будет выходить две цепи, сумма длин которых будет равна m1, и (k – 1)/2 циклов, каждый из которых имеет длину m1 + 1. Получившиеся цепи будут соответствовать подходящим цепям дерева T. Один из оставшихся циклов используем для вложения цепи максимальной длины m1, а в каждом из (k – 1)/2 оставшихся циклов выделим по две цепи подходящей длины, так чтобы получить оставшиеся k – 1 цепей дерева T. Вложение построено.

На рис. 3.6.2 представлены 7-вершинное сверхстройное дерево с вектором цепей (3,2,1) и все его минимальные реберные 1-расширения, первое из которых построено по теореме 3.6.3. Это дерево является минимальным по числу вершин среди представителей рассматриваемого в теореме 3.6.3 семейства.

Рис. 3.6.2. Сверхстройное дерево (3,2,1) и все его МР-1Р Следствие. Сверхстройные деревья, удовлетворяющие условию теоремы 3.6.3, при k > 3 имеют единственное с точностью до изоморфизма минимальное реберное 1-расширение.

Дополнительные семейства Идея доказательства теоремы 3.6.3 легко переносится и на более общий случай сверхстройных деревьев.

ТЕОРЕМА 3.6.4. Сверхстройное дерево T с вектором цепей (m1,…mk) имеет реберное 1-расширение с вектором степеней (k + d,2,…,2), d > 0, отличающееся от T на (k + d)/2 дополнительных ре-бер когда 1) среди его цепей есть цепи всех длин от 1 до его высоты m (максимальной длины цепи);

2) цепей максимальной длины m1 в точности d;

3) все остальные цепи можно разбить на пары так, чтобы их длины в сумме давали m1.

Доказательство. Пусть k – четно и T – сверхстройное дерево с вектором цепей (m1,…mk), а G* – его реберное 1-расширение с вектором степеней (k + d,2,…,2), отличающееся от T на (k + 2)/2 дополнительных ребер. Доказательство следует схеме предыдущей теоремы.

Нетрудно видеть, что граф G* представляет собой объединение циклов с общей вершиной, которую для определенности обозначим v. Построение G* из дерева T можно представить себе следующим образом: d висячих вершин соединяются с корневой вершиной, а остальные висячие вершины попарно соединяются между собой.

Количество циклов в G* обозначим через t = d(v)/2 = (k + d)/2. Длины циклов в G* обозначим через p1,…,pt. Для определенности будем считать, что m1 … mk и p1 … pt. Очевидно, что p1 m1 + 1.

Необходимость. Рассмотрим удаление произвольного ребра в графе G*. Это ребро принадлежит некоторому циклу длины pi. Если ребро инцидентно вершине v, то после удаления ребра вместо цикла появится цепь длины pi – 1. Если ребро не инцидентно вершине v, то цикл распадается на две цепи. Так как по предположению дерево T вкладывается в получившийся граф, то для каждой из этих цепей должна найтись цепь такой же длины и в дереве T. В силу произвольности выбора ребра можно сделать вывод, что в дереве T должны быть цепи длины 1, 2,…, p1 – 1. С учетом полученной ранее оценки p1 m1 + 1 имеем p1 = m1 + 1. Таким образом, утверждение доказано.

Предположим, что в дереве T есть более d цепей максимальной длины m1. Так как концы только d из этих цепей могут быть соединены с корневой вершиной и образовать цикл максимальной длины p1 = m1 + 1, то концы остальных цепей длины m1 должны быть соединены с концами некоторых других цепей. Но это приведет к тому, что длины получившихся циклов будут больше, чем p1 = m1 + 1, а это противоречит предположению о том, что p1 является максимальной длиной цикла. Таким образом, утверждение доказано.

Предположим, что p1 > pt, то есть не все циклы имеют одинаковую длину p1. Рассмотрим граф, получающийся из G* удалением ребра e инцидентного вершине v из цикла минимальной длины pt, и попробуем построить вложение дерева T в получившийся граф. Вершина v в графе G* – e имеет степень k + 1 и единственным образом соответствует корневой вершине дерева. Из вершины v выходит одна цепь длины pt – 1 и k/2 циклов, из которых нужно выделить k – 1 цепь. По предположению pt – 1 < m1, то есть единственная цепь, получившаяся после удаления ребра e, не может быть цепью максимальной длины. Таким образом, два цикла максимальной длины p1 будут содержать в себе две цепи максимальной длины m1. Однако тогда остается еще (k – 4)/2 циклов, и этого недостаточно, чтобы построить вложение для оставшихся k – 2 цепей. Полученное противоречие доказывает утверждение 3, а вмести с ним и необходимость.

Достаточность. Предположим, что дерево T удовлетворяет условиям 1-3 теоремы. Построим граф G* из дерева T следующим образом: концевые вершины цепей максимальной длины m1 соединяем с корневой вершиной, а остальные концевые вершины цепей попарно соединяются между собой таким образом, чтобы длина цикла была m1 + 1: конец цепи длины соединяется с концом цепи длины m1 – 1, конец цепи длины 2 соединяется с концом цепи длины m1 – 2 и так далее. Докажем, что граф G* будет реберным 1-расширением дерева T.

Исследуем удалением произвольного ребра e из графа G*. Рассмотрим два случая.

1. Ребро e инцидентно корневой вершине v. Удаление ребра e приведет к тому, что из корневой вершины v будет выходить одна цепь длины m1 и (k + d – 2)/2 циклов, каждый из которых имеет длину m1 + 1. Получившаяся цепь будет соответствовать цепи дерева T максимальной длины m1, d – циклов будут содержать остальные цепи максимальной длины, а в каждом из (k – d)/2 циклов выделим по две цепи подходящей длины, так чтобы получить оставшиеся k – d цепей дерева T. Вложение построено.

2. Ребро e не инцидентно корневой вершине v. Удаление ребра e приведет к тому, что из корневой вершины v будет выходить две цепи, сумма длин которых будет равна m1 и (k + d – 2)/2 циклов, каждый из которых имеет длину m1 + 1. Получившиеся цепи будут соответствовать подходящим цепям дерева T. Из оставшихся циклов d штук используем для вложения d цепей максимальной длины m1, а в каждом из (k – d)/2 оставшихся циклов выделим по две цепи подходящей длины, так чтобы получить оставшиеся k – d цепей дерева T. Вложение построено. Теорема доказана.

На рис. 3.6.3 представлены 10-вершинное сверхстройное дерево с вектором цепей (3,3,2,1) и все его минимальные реберные 1-расширения, первое из которых построено по теореме 3.6.4.

Рис. 3.6.3. Сверхстройное дерево (3,3,2,1) и все его МР-1Р В работе (Абросимов, Комаров, 2010, а) можно посмотреть каталог минимальных реберных 1-расширений всех сверхстройных деревьев с числом вершин до 10.

Следствие. Для сверхстройных деревьев, удовлетворяющих условию теоремы 3.6.4, при d = 2 соответствующее реберное 1-расширение будет и минимальным.

3.7. Орграфы Основные определения, связанные с расширениями графов, которые были сформулированы в первом параграфе этой главы для неориентированных графов, без изменений могут быть перенесены и на ориентированные графы. Леммы 3.1.1-3.1.2 можно применять и к орграфам.

3.7.1. Турниры В отличие от вершинных для минимальных реберных k-расширений турниров полное решение задачи получается достаточно легко.

ТЕОРЕМА 3.7.1. Единственным с точностью до изоморфизма минимальным реберным 1-расширением n-вершинного турнира является полный n-вершинный граф без петель. При k > 1 n-вершинный турнир не имеет минимальных реберных k-расширений.

Доказательство. Пусть T есть n-вершинный турнир, а T* – его минимальное реберное 1-расширение. Каждая пара вершин графа T является концами некоторой дуги. Пусть граф T* отличен от полного графа без петель.

Тогда в нем есть пара вершин u, v таких, что между ними нет дуги (u, v). Рассмотрим подграф, получающийся удалением дуги (v, u) (эта дуга обязательно есть, поскольку T* является минимальным реберным 1-расширением турнира T, то есть граф T* допускает вложение турнира T). В этот подграф нельзя будет вложить турнир T, так как между вершинами u, v нет ни одной дуги. Следовательно, полный n-вершинный граф без петель является единственным минимальным реберным 1-расширением турнира T.

При k > 1 любая пара вершин u, v орграфа T* может быть соединена не более чем двумя дугами (u, v) и (v, u), поэтому удалим из T* обе эти дуги и k – 2 любых других дуг. Получим орграф, в который нельзя вложить турнир T.

Таким образом, при k > 1 турниры не имеют минимальных реберных k-расширений.

3.7.2. Ориентации звезд звезды Zm,n добавлением p – 1 «центральной» вершины, соединением их между собой и центральной вершиной звезды Zm,n парами встречных дуг. Каждая из добавленных центральных вершин соединяется m входящими и n исходящими дугами с произвольными источниками и стоками звезды Zm,n. По описанной схеме для заданной звезды в общем случае может быть построено много графов (рис. 3.7.1).

ТЕОРЕМА 3.7.2. Относительно минимальных реберных 1-расширений направленных звезд Zm,n справедливо следующее:

1) при m = n = 1 звезда Z1,1 имеет единственное с точностью до изоморфизма минимальное реберное 1-расширение, которым является циклическая тройка;

2) при mn > 1 звезда Zm,n имеет минимальные реберные 1-расширения вида K1,m+n и графы, построенные по схемам ZKm–1,n,2 и ZKm,n–1,2;

3) при m > 0, n = 0 звезда Zm,0 имеет минимальные реберные 1-расширения вида ZKm–1,0,2;

4) при m = 0, n > 0 звезда Z0,n имеет минимальные реберные 1-расширения вида ZK0,n–1,2;

5) при m = 2, n = 1 звезда Z2,1 имеет еще одно минимальное реберное 1-расширение – турнир, получающийся из циклической тройки добавлением одной вершины и дуг от неё во все остальные вершины;

6) при m = 2, n = 1 звезда Z2,1 имеет еще одно минимальное реберное 1-расширение – турнир, получающийся из циклической тройки добавлением одной вершины и дуг в неё из всех остальных вершин.

Доказательство. Убедимся, что орграфы K1,m+n, ZKm–1,n,2 и ZKm,n–1,2 действительно являются реберными 1-расширениями звезды Zm,n.

Для неориентированной звезды K1,m+n проверка вполне тривиальна.

Пусть в звезде Zm,n есть и источники, и стоки, то есть m > 0 и n > 0. Рассмотрим удаление в графе K1,m+n любой дуги вида (v, u), где v – центральная вершина, а u – любая другая. Вложение звезды Zm,n строится следующим образом: центральная вершина звезды Zm,n соответствует вершине v. Вершина u и m – 1 из оставшихся вершин графа K1,m+n будут соответствовать источникам, а остальные n вершин – стокам. Аналогично – для случая удаления дуги вида (u, v). Заметим, что количество дуг в графе K1,m+n в два раза больше, чем в звезде Zm,n, то есть 2(m + n).

Пусть m > 0; рассмотрим орграф ZKm–1,n,2. В этом графе две вершины имеют полустепени исхода и захода n + 1 и m соответственно, а у остальных вершин суммы полустепеней исхода и захода равны 2. Общее количество дуг равно 2(m + n). Обозначим две полные вершины через v1 и v2.

Все дуги рассматриваемого орграфа можно разделить на три группы подобных дуг:

1) дуги от вершин v1 и v2 в остальные вершины (если n = 0, то дуг этого типа может не быть);

2) дуги в вершины v1 и v2 из остальных вершин (если m = 1, то дуг этого типа может не быть);

3) дуги между вершинами v1 и v2.

Рассмотрим удаление из орграфа ZKm–1,n,2 дуги каждого вида и укажем, каким образом в получившийся орграф может быть вложена звезда Zm,n. Обозначим:

1) G1 – граф, получающийся из орграфа ZKm–1,n,2 удалением дуги первого типа; пусть для определенности это будет дуга (v1, u), где u – произвольная вершина, которая в звезде Zm,n была стоком;

2) G2 – граф, получающийся из орграфа ZKm–1,n,2 удалением дуги второго типа; пусть для определенности это будет дуга (w, v1), где w – произвольная вершина, которая в звезде Zm,n была истоком;

3) G3 – граф, получающийся из орграфа ZKm–1,n,2 удалением дуги третьего типа; пусть для определенности это будет дуга (v2, v1).

Во всех трех случаях m – 1 вершин орграфов G1, G2, G3, из которых идет дуга в вершину v2, и вершина v1 будут соответствовать источникам звезды Zm,n, вершина v2 – центральной вершине, а оставшиеся n вершин орграфов G1, G2, G3 – стокам звезды Zm,n.

Аналогично рассмотрим орграф ZKm,n–1,2 при n > 0. В этом графе две вершины имеют полустепени исхода и захода n и m + 1 соответственно, а у остальных вершин суммы полустепеней исхода и захода равны 2. Общее количество дуг снова равно 2(m + n). Как и раньше, обозначим две полные вершины через v1 и v2. Все дуги рассматриваемого орграфа делятся на три группы подобных дуг:

1) дуги от вершин v1 и v2 в остальные вершины (если n = 1, то дуг этого 2) дуги в вершины v1 и v2 из остальных вершин (если m = 0, то дуг этого 3) дуги между вершинами v1 и v2.

Рассмотрим удаление из орграфа ZKm,n–1,2 дуги каждого вида и укажем, каким образом в получившийся орграф может быть вложена звезда Zm,n.

Пусть 1) граф G1 получается из орграфа ZKm,n–1,2 удалением дуги первого типа;

пусть для определенности это будет дуга (v1, u), где u – произвольная вершина, которая в звезде Zm,n была стоком;

2) граф G2 получается из орграфа ZKm,n–1,2 удалением дуги второго типа;

пусть для определенности это будет дуга (w, v1), где w – произвольная вершина, которая в звезде Zm,n была истоком;

3) граф G3 получается из орграфа ZKm,n–1,2 удалением дуги третьего типа;

пусть для определенности это будет дуга (v1, v2).

Во всех трех случаях m – 1 вершин орграфов G1, G2, G3, из которых идет дуга в вершину v2, и вершина v1 будут соответствовать источникам звезды Zm,n, вершина v2 – центральной вершине, а оставшиеся n вершин орграфов G1, G2, G3 – стокам звезды Zm,n.

Исследуем, какие у звезды Zm,n могут быть минимальные реберные 1-расширения. Пусть G* – некоторое минимальное реберное 1-расширение звезды Zm,n. Так как звезда Zm,n вкладывается в орграф G*, то в G* есть как минимум одна полная вершина. Рассмотрим случаи, когда таких вершин одна, две, три и более.

Случай I. Предположим, что полная вершина одна, и обозначим ее через v. В этом случае вершина v должна быть соединена со всеми остальными вершинами парой встречных дуг. Если бы это было не так и вершина v была бы соединена с некоторой вершиной u только одной дугой, например (v, u), то вложение звезды Zm,n в граф G* – (v, u) было бы невозможно, так как ни одна вершина не будет соответствовать центральной вершине звезды Zm,n.

Граф K1,m+n имеет минимальное число дуг среди всех рассматриваемых графов, то есть графов с одной вершиной, соединенной парой встречной дуг со всеми остальными вершинами.

Случай II. Пусть есть две полные вершины. Обозначим их через v1 и v2. Какие дуги должны быть между этими вершинами? Если между ними будет только одна дуга, например (v1, v2), то граф, получающийся из G* после удаления дуги (v1, v2), не будет содержать ни одной вершины, которая могла бы соответствовать центральной вершине звезды Zm,n. Следовательно, вершины v1 и v2 соединены парой встречных дуг.

Каковы могут быть полустепени исхода и захода вершин v1 и v2? Очевидно, что они не могут быть меньше, чем у центральной вершины звезды Zm,n, то есть n и m соответственно. Общее количество дуг, входящих и исходящих из этих вершин, равно m + n + 1 (две дуги между вершинами v1 и v2 и по одной дуге в или из оставшихся m + n – 1 вершин). Таким образом, вершины v1 и v2 могут иметь либо полустепень исхода m, а полустепень захода n + 1, либо наоборот. Можно заметить, что вершины v1 и v2 должны иметь одинаковые полустепени исхода и захода. В самом деле, если бы это было не так и вершины v1 и v2 имели бы разные полустепени, например, вершина v1 – (m, n + 1), а вершина v2 – (m + 1, n), то удаление дуги (v1, v2) привело бы к орграфу, в котором вершины v1 и v2 имеют полустепени исхода и захода (m – 1, n + 1) и (m + 1, n – 1) соответственно. Ясно, что вложение в получившийся граф звезды Zm,n невозможно. Итак, среди всех графов, имеющих две вершины с одинаковыми полустепенями исхода и захода, соединенные между собой парой встречных дуг, а с остальными вершинами хотя бы одной дугой, подходящими являются только графы семейств ZKm–1,n,2 и ZKm,n–1,2.

Случай III. Рассмотрим случай, когда есть три вершины, соединенные со всеми остальными m + n – 2 вершинами хотя бы одной дугой. Обозначим эти полные вершины через v1, v2 и v3. Подобное соединение возможно при m + n 2. Между этими вершинами, очевидно, должна быть, по крайней мере, одна дуга. Общее количество дуг в таком графе будет не менее чем Если m + n = 2, то число дуг будет меньше, чем в рассмотренных ранее случаях I и II, где количество дуг есть 2(m + n). Непосредственной проверкой убедимся, что звезда Z1,1, которая является ориентированной цепью (рис.

3.7.2, а), имеет подходящее реберное 1-расширение, которое в данном слуРис. 3.7.2. Звезда Z1,1 (а) и ее единственчае будет циклической тройкой (рис.

3.7.2, б).

Звезды Z2,0 и Z0,2 не имеют реберных 1-расширений, построенных по рассматриваемой схеме. Если же добавить еще одну дугу, то мы получим графы, изоморфные графам семейств ZK1,0,2 и ZK0,1,2. При m + n = 3 имеем 3(m + n – 1) = 2(m + n). То есть число дуг будет таким же, как и в рассмотренных ранее случаях. Подходящими звездами будут Z3,0, Z2,1, Z1,2 и Z0,3. Непосредственной проверкой убеждаемся, что звезды Z3,0 и Z0,3 не имеют реберных 1-расширений, построенных по рассматриваемой схеме, а звезды Z2, 1-расширения изображены на рис. 3.7.3, б, г.

На рис. 3.7.3, б, г первыми указаны расширения, укладывающиеся в рассматриваемую схему. Вершины v1, v2 и v3 образуют в них контур. Последующие три расширения принадлежат семействам ZK2,0,2 и ZK1,1,2 для звезды Z2,1; ZK0,2,2 и ZK1,1,2 для звезды Z1,2. Последние расширения – это звезды K1,3.

Видно, что звезды Z2,1 и Z1,2 имеют три изоморфных минимальных реберных 1-расширения и по два различных.

Случай IV. Рассмотрим случай, когда есть p > 3 вершин, соединенных со всеми остальными m + n – p + 1 вершинами хотя бы одной дугой. Подобное соединение возможно при m + n p – 1. Между этими вершинами, очевидно, должна быть, по крайней мере, одна дуга, то есть индуцированный ими подграф является турниром. Общее количество дуг в таком графе будет не менее чем Исследуем, в каких случаях эта величина может быть меньше, чем 2(m + n) – количество дополнительных ребер в случаях I и II. Получаем (p– 1)(p – 2 – p/2) 0, а так как p > 3, то остается p/2 – 2 0, то есть p 4.

Случаи, когда p = 1, 2 и 3, были рассмотрены ранее, и, так образом, еще только при p = 4 возможно реберное 1-расширение, которое будет иметь не больше дуг, чем расширения из случаев I и II. Итак, при p = 4 количество дуг есть 4(m + n) – 6, а у расширений в случаях I и II – 2(m + n), причем m + n 3.

Сравнивая, получаем, что лишь при m + n = 3 достигается равенство, а при остальных значениях количество дуг в расширении с p = 4 будет больше, чем в случаях I и II. При m + n = 3 имеем четыре звезды, которые мы уже рассматривали ранее: Z3,0, Z2,1, Z1,2 и Z0,3. Можно заметить, что эта ситуация идентична рассмотренной ранее и не дает новых реберных 1-расширений.

Следствие 1. Исходящая звезда, то есть направленная звезда вида Zm,0, m > 1, имеет два неизоморфных минимальных реберных 1-расширения – граф K1,m, и орграф ZKm–1,0,2.

Следствие 2. Входящая звезда, то есть направленная звезда вида Z0,n, n > 1, имеет два неизоморфных минимальных реберных 1-расширения – граф K1,m, и орграф ZK0,n–1,2.

Теорему 3.7.2 легко обобщить для ориентированных звезд. Обозначим через ZKm,n,p,t граф, получающийся из звезды Zm,n добавлением t – 1 «центральной» вершины, соединением их между собой и центральной вершиной звезды Zm,n парами встречных дуг. Каждая из добавленных центральных вершин соединяется m входящими, n исходящими дугами и p ребрами с произвольными источниками и стоками звезды Zm,n.

ТЕОРЕМА 3.7.3. Ориентированные звезды Zm,n,p при m > 0, n > 0 и p > 0 имеют единственное с точностью до изоморфизма минимальное реберное 1-расширение – звезду K1,m+n+p.

Доказательство. Пусть G* – некоторое минимальное реберное 1-расширение звезды Zm,n,p. Так как звезда Zm,n,p вкладывается в орграф G*, то в G* есть как минимум одна полная вершина. Рассмотрим случаи, когда полная вершина одна и более.

Случай I. Предположим, что полная вершина одна, и обозначим ее через v. Повторяя рассуждения из доказательства теоремы 3.7.2, получим, что вершина v должна быть соединена со всеми остальными вершинами парой встречных дуг. Если бы это было не так и вершина v была бы соединена с некоторой вершиной u только одной дугой, например (v, u), то вложение звезды Zm,n,p в граф G* – (v, u) было бы невозможно, так как ни одна вершина не будет соответствовать центральной вершине звезды Zm,n,p. Граф K1,m+n+p имеет минимальное число дуг среди всех подходящих под этот случай графов, то есть графов с одной вершиной, соединенной парой встречной дуг со всеми остальными вершинами. Легко видеть, что звезда K1,m+n+p является реберным 1-расширением орзвезды Zm,n,p. Рассмотрим удаление в графе K1,m+n+p любой дуги вида (v, u), где v – центральная вершина, а u – любая другая. Вложение звезды Zm,n,p строится следующим образом: центральная вершина звезды Zm,n,p соответствует вершине v. Вершина u и m – 1 из оставшихся вершин графа K1,m+n будут соответствовать источникам, а остальные n + p вершин – стокам и вершинам, которые соединены с центральной вершиной парой встречных дуг. Заметим, что количество дуг в графе K1,m+n+p есть 2(m + n + p).

Случай II. Предположим, что вершин, соединенных дугой с остальными вершинами, всего t штук и t > 1. Повторяя рассуждения из теоремы 3.7.2, мы получим, что центральные вершины должны быть соединены между собой, что дает не менее t(t – 1)/2 дуг, каждая из них – с p вершинами парой встречных дуг и с остальными m + n – t + 1 вершинами, по крайней мере, одной дугой. Всего получаем дуг Эта величина принимает минимальное значение (по t > 1) при t = 2, и это будет 2(m + n + p) + p – 1. Однако при t = 2, как мы установили при исследовании случая II в доказательстве теоремы 3.7.2, центральные вершины должны быть соединены парой встречных дуг. Поэтому минимально возможное количество дуг по данной схеме может быть 2(m + n + p) + p, и при p > 0 это больше числа дуг в графе K1,m+n+p.

Обобщим результаты двух предыдущих теорем.

ТЕОРЕМА 3.7.4. Относительно минимальных реберных k-расширений направленных звезд Zm,n справедливы следующие утверждения:

1) при m = n = k звезда Zm,n имеет минимальным реберным k-расширением любой регулярный (2k + 1)-вершинный турнир и только их;

2) при m = n + 1 = k звезда Zm+1,m имеет минимальным реберным k-расширением любой (2k + 2)-вершинный турнир, который получается из регулярного (2k + 1)-вершинного турнира добавлением дополнительной вершины-источника;

3) при m + 1 = n = k звезда Zm,m+1 имеет минимальным реберным k-расширением любой (2k + 2)-вершинный турнир, который получается из регулярного (2k + 1)-вершинного турнира добавлением дополнительной вершины-стока;

4) кроме случая m = n = k звезда Zm,n при k m + n имеет минимальным реберным k-расширением графы вида ZKm1,n1,k+1, где m1+ n1= m+n – k, не имеет минимальных реберных k-расширений.

Доказательство. Пусть k > 1 и G* – некоторое минимальное реберное k-расширение звезды Zm,n. Так как звезда Zm,n вкладывается в орграф G*, то в G* есть как минимум одна вершина, соединенная дугой со всеми остальными.

Обозначим через p количество полных вершин; положим N = m + n. Очевидно, что p m + n + 1. Удаление k любых дуг из графа G* должно оставить, по крайней мере, одну полную вершину.

Случай I. Если все полные вершины в графе G* соединены между собой одной дугой, то удаление такой дуги исключает две полные вершины.

Поэтому количество полных вершин должно быть не менее 2k + 1. Тогда количество дуг в таком орграфе будет не менее чем (2k + 1)k + + (2k + 1)(N – 2k) = (2k + 1)N – 2k2 – k, причем 2k N.

Случай II. Если все полные вершины в графе G* соединены между собой парой встречных дуг, то удаление такой пары дуг исключает две полные вершины. Поэтому если k четно, то количество полных вершин должно быть не менее k + 1. При нечетном k = 2k1 + 1 с удалением k1 пары встречных дуг будут исключены k – 1 полных вершин. Предположим, что останется еще лишь одна полная вершина. Если она будет соединена с некоторой вершиной только одной дугой, то, удалив ее, мы исключим последнюю полную вершину. Следовательно, эта вершина должна быть соединена с остальными вершинами также парой встречных дуг. Более того, удалив одну такую дугу, мы получим, что из единственной полной вершины либо исходит, либо входит в некоторую вершину единственная дуга. Следовательно, в звезде Zm,n должен быть хотя бы один источник и сток. В силу произвольности выбора исключаемых вершин можно сделать вывод, что при нечетном k, при n > 0, m > 0 и k – 1 N орграф G* может иметь k полных вершин, соединенных между собой и со всеми остальными вершинами парой встречных дуг. Определим количество дуг в этом случае: k(k – 1) + 2(N – k + 1)k = 2Nk – k2 + k, причем k – Случай III. Если количество полных вершин в орграфе G* есть k + 1, то между собой они должны быть соединены парой встречных дуг, но с остальными вершинами они могут быть соединены одной дугой. Мы уже встречались с такими орграфами, например это семейства ZK m,n,k +1. Минимальное – k) = N(k + 1), причем k N.

Видно, что при больших значениях N количество дуг в последнем случае будет меньше, чем в случаях I и II. Определим более точные соотношения по количеству дуг между этими случаями. Случаи II и III:

При k = 1 мы имеем равенство количества дуг. Случай II при k = 1 – это звезда K1,N из теоремы 3.7.2. При k > 1 интерес представляет случай N k. Но так как в случае II k N, то остается единственная возможность – k = N. Легко видеть, что при k = N графы в случаях II и III изоморфны и представляют собой полный граф Kn. Таким образом, при k > 1 случай II не представляет интереса.

Так как в случае I имеем ограничение 2k N, то интерес представляет всего два значения N. При N = 2k получаем, что граф, построенный по схеме I, будет иметь меньше дуг, чем граф из случая III, а при N = 2k + 1 – количество дуг в случаях I и III будет одинаково. Видно, что при этих значениях графы из случая I будут турнирами. Исследуем эти возможности подробнее.

N = 2k. В этом случае мы имеем (2k + 1)-вершинный турнир. Удаляя k произвольных дуг, соединяющих различные вершины турнира, мы получим граф с единственной полной вершиной, которая соединена с каждой их остальных вершин одной дугой. Значит, чтобы звезда Zm,n вкладывалась в получившийся граф, в эту вершину должны входить m дуг и выходить n. В силу произвольности выбора это должно быть справедливо для всех вершин турнира, то есть все вершины должны иметь одинаковые степени исхода и захода. Это возможно лишь при m = n = k. Таким образом, только звезда вида Zm,m может иметь регулярный турнир минимальным реберным k-расширением при k = m. При k = 1 имеем звезду Z1,1 и ее минимальным реберным 1-расширением является циклическая тройка. На рис. 3.7.4 показаны звезда Z2,2 и ее единственное минимальное реберное 2-расширение, построенное по описанной схеме.

Рис. 3.7.4. Звезда Z2,2 и ее единственвершины турнира, получим граф с двумя с каждой из остальных вершин одной дугой. Значит, чтобы звезда Zm,n вкладывалась в получившийся граф, в одну из этих вершин должны входить m дуг и выходить n. Так как число вершин в турнире четно, то он не может быть регулярным, и все вершины не могут иметь одинаковые полустепени исхода и захода. Следовательно, хотя бы одна вершина будет иметь полустепени исхода и захода, отличные от m и n. Однако такая вершина может быть только одна, потому что в противном случае, подбирая соответствующим образом k удаляемых дуг, мы могли бы получить орграф с двумя полными вершинами, ни одна из которых не имела бы m входящих и n исходящих дуг.

Итак, в (2k + 2)-вершинном турнире 2k + 1 вершин должны иметь одинаковые полустепени исхода и захода – m и n соответственно. Таким образом, имеем (2k + 1)m исходящих дуг, (2k + 1)n входящих и одну неучтенную вершину, обозначим ее w. Так как число входящих и исходящих дуг должно быть равно, а m n, то можно сделать вывод, что либо m = n + 1 и w является стоком, либо n = m + 1 и w является источником. Таким образом, только звезды вида Zm+1,m и Zm,m+1 могут иметь минимальным реберным k-расширением при k = m турнир, получающийся из регулярного (2m + 1)вершинного турнира добавлением вершины и дуг из неё во все вершины турнира для звезды Zm+1,m и из всех вершин турнира в добавленную для звезды Zm,m+1. При k = 1 мы имеем звезды Z2,1 и Z1,2 и их минимальные реберные 1расширения, упомянутые в пунктах 5 и 6 теоремы 3.7.2. Этим завершается исследование случая I. Рассмотрим далее наиболее общий случай III.

Кроме случая N = 2k графы, построенные по схеме случая III, являются кандидатами на роль минимальных реберных k-расширений. Убедимся, что эти графы действительно будут являться реберными k-расширениями. Пусть G* – произвольный граф вида ZK m,n,k +1, где m1 + n1 + k = m + n. Рассмотрим удаление дуг между различными полными вершинами и остальными вершинами орграфа G*. Удаление одной такой дуги исключает одну полную вершину. Удаление k дуг оставит единственную полную вершину. Эта полная вершина будет соединена с k вершинами парой встречных дуг, с m1 вершинами исходящей дугой, а с n1 вершинами входящей дугой. По предположению звезда Zm,n должна вкладываться в получившийся орграф. Если m1 > m или n1 > n, то такое вложение будет невозможно. Аналогично, если m1 < m – k или n1 < n – k. Если же все указанные неравенства выполняются, то недостающими вершинами для соответствия источникам и стокам звезды будут являться бывшие полные вершины орграфа G*. Похожим образом можно рассмотреть удаления дуг между полными вершинами и убедиться, что графы вида ZK m,n, k +1 действительно являются реберными 1-расширениями звезды Zm,n при выполнении указанных ранее ограничений.

На рис. 3.7.5 показаны все минимальные реберные 2-расширения звезд Z2,3 и Z3,2.

Рис. 3.7.6. Звезды Z2,3 (а) и Z3,2 (г) и их МР-2Р: единственное в форме турнира (б, д) и по одному представителю семейств ZK1,2,3 (в) и ZK2,1,3 (е) ТЕОРЕМА 3.7.5. Относительно минимальных реберных k-расширений ориентированных звезд Zm,n,p справедливо следующее:

1) при четном k звезда Zm,n,p имеет минимальные реберные k-расширения 2) при нечетном k, m > 0, n > 0 и (m + n – k)(k – 1) – 2p 0 звезда Zm,n,p имеет минимальное реберное k-расширение вида Kk + Om+n+p–k+1;

3) при k m + n и (m + n – k)(k – 1) – 2p 0 звезда Zm,n,p имеет минимальные реберные k-расширения вида ZK m,n, p, k +1 ;

4) при k > m + n звезда Zm,n,p не имеет минимальных реберных k-расширений.

Доказательство. Пусть k > 1 и G* – некоторое минимальное реберное k-расширение звезды Zm,n,p. Так как звезда Zm,n,p вкладывается в орграф G*, то в G* есть как минимум одна полная вершина. Обозначим через t количество полных вершин; положим N = m + n. Очевидно, что t m + n + 1. Удаление k любых дуг из графа G* должно оставить, по крайней мере, одну полную вершину.

Случай I. Если все полные вершины в графе G* соединены между собой одной дугой, то удаление одной такой дуги исключает две полные вершины. Поэтому количество полных вершин должно быть не менее 2k + 1.

Каждая полная вершина должна быть соединена с p вершинами парой встречных дуг, а с остальными, по крайней мере, одной дугой. Тогда количество дуг в таком орграфе будет не менее чем (2k + 1)k + (2k + 1)(N – 2k) + 2(2k + 1)p = (2k + 1)N – 2k2 – k + 2(2k + 1)p, причем 2k N.

Случай II. Если все полные вершины в графе G* соединены между собой парой встречных дуг, то удаление такой пары дуг исключает две полные вершины. Поэтому, если k четно, то количество полных вершин должно быть не менее k + 1. При нечетном k = 2k1 + 1 удаление k1 пары встречных дуг исключает k – 1 полную вершину. Предположим, что останется еще лишь одна полная вершина. Если она будет соединена с некоторой вершиной только одной дугой, то, удалив ее, мы исключим последнюю полную вершину. Следовательно, эта вершина должна быть соединена с остальными вершинами также парой встречных дуг. Более того, удалив одну такую дугу, мы получим, что из единственной полной вершины либо исходит, либо входит в некоторую вершину единственная дуга. Следовательно, в звезде Zm,n должен быть хотя бы один источник и сток. В силу произвольности выбора исключаемых вершин можно сделать вывод, что при нечетном k, при n > 0, m > 0 и k – 1 N орграф G* может иметь k полных вершин, соединенных между собой и со всеми остальными вершинами парой встречных дуг. Такой граф Kk + Om+n+p–k+1. Определим количество дуг в этом случае:

причем k – 1 N.

Случай III. Если количество полных вершин в ографе G* есть k + 1, то между собой они должны быть соединены парой встречных дуг, c p вершинами также парой встречных дуг, а с остальными вершинами они могут быть соединены одной дугой. Мы уже встречались с такими орграфами, например это семейства ZK m,n, p,k +1 Определим минимальное количество дуг в этом случае:

причем k N.

Видно, что при больших значениях N количество дуг в последнем случае будет минимальным. Определим более точные соотношения по количеству дуг между этими случаями. Случаи II и III:

При k = 1 в теореме 3.7.3 мы получили, что графы из случая II всегда имеют меньшее число дуг, чем графы из случая III. При k > 1 ситуация представляется более сложной: при значениях N много больших, чем k и p, меньше дуг будет в схеме III, а при нечетных значениях k, близких к значению N или больших, чем p, меньше дуг будет в схеме II.

Так как в случае I имеем ограничение 2k N, то при p > 0 у графов из случая I будет всегда больше дуг, чем у графов из случая III.

Рассмотрим для примера поиск минимальных реберных 3-расширений звезды Z2,2,1. Посчитаем величину (m + n – k)(k – 1) – 2p и получим:

Таким образом, по теореме 3.7.5 получаем, что звезда Z2,2,1 будет иметь минимальные реберные 3-расширения двух видов: граф K3 + O3 и графы вида ZK1,0,1,4 и ZK0,1,1,4. Все эти графы содержат по 24 дуги. На рис. 3.7.6 показаны все минимальные реберные 3-расширения звезды Z2,2,1. Для облегчения визуализации расширений пара встречных дуг заменена неориентированным ребром.

ЗАКЛЮЧЕНИЕ

В заключении хочется рассмотреть два вопроса относительно минимальных вершинных и реберных k-расширений, которые часто кажутся очевидными.

Рассмотрим задачу нахождения минимального вершинного (реберного) k-расширения графа. Можем ли мы использовать для решения этой задачи знание минимальных вершинных (реберных) расширений графа при значениях меньших k? Представляется интуитивно очевидным, что минимальное вершинное (реберное) 1-расширение минимального вершинного (реберного) (k – 1)-расширения будет являться минимальным вершинным (реберным) kрасширением.

Очевидно, что минимальное вершинное 1-расширение любого минимального вершинного (k - 1)-расширения графа будет и его вершинным kрасширением. Более того, для некоторых классов графов было доказано, что оно является и минимальным вершинным k-расширением. Например для цепей, циклов, предполных графов и некоторых других связных и несвязных графов утверждение имеет место при всех значениях k.

Оказывается, что в общем случае это не так.

Рассмотрим граф G вида Pn Pn Om, где m 2n – 2. Покажем, что минимальным вершинным 1-расширением графа G при n > 3 будет граф G* вида С 2 n +1 Om, причем при n > 4 единственным с точностью до изоморфизма (при n = 2, 3 минимальным вершинным 1-расширением графа G будет граф вида Pn Pn Pn O m n +1 ). В самом деле, граф С 2 n +1 Om отличается от 1-расширение не может иметь менее двух дополнительных ребер (заметим, что при n = 2 минимальным вершинным 1-расширением графа G будет граф P2 P2 P2 O m 1, отличающийся на одно дополнительное ребро), поскольку степень хотя бы одной вершины будет не ниже двух. Таким образом, нужно показать, что не существует минимального вершинного 1-расширения, отличающегося на два ребра. Предположим, что такой граф существует. Тогда степень любой его вершины не более двух. Рассмотрим, какие графы получаются из графа G добавлением одной вершины и двух ребер (и степень вершин ни в каком из этих графов не больше двух):

Непосредственной проверкой убеждаемся, что ни один из перечисленных графов при n > 3 не является вершинным 1-расширением графа G (заметим, что при n = 3 граф P3 P3 P3 O m 2 является минимальным вершинным 1-расширением графа G).

Минимальное вершинное 1-расширение графа G* имеет вид C2n+1 Om, где C 2 n+1 некоторое минимальное вершинное 1-расширение цикла C2n+1 – однородный граф порядка 3. Покажем, что при некоторых значениях n никакой 1-расширением графа G.

граф является вершинным 2-расширением графа G и имеет 4n – 4 ребра.

Найдем значения n, при которых он будет являться и минимальным вершинным 2-расширение графа G: 4n – 4 < 3n + 3, откуда n < 7. Таким образом, при n = 5 или n = 6 граф Pn Pn O m имеет единственное с точностью до изоморфизма минимальное вершинное 1-расширение – граф вида С 2 n +1 Om, – и Pn Pn Pn Pn O m 2 n + 2, который не является минимальным вершинным 1расширением графа С 2 n +1 Om. На рис. З.1 приводится иллюстрация данного примера при n = 5 и m = 8. При n = 7 граф Pn Pn O m имеет единственное минимальное вершинное 1-расширение и два неизоморфных минимальных вершинных 2-расширения, одно из которых является минимальным вершинным 1-расширением его минимального вершинного 1-расширения, а другое нет.

Рассматривая большие значения n, можно указать графы, которые имеют минимальное вершинное k-расширение, не являющееся минимальным вершинным 1-расширением их минимального вершинного (k – 1)-расширения при больших значениях k (например, при 7 < n < 11 это будет справедливо для k = 3 и т. д.).

Рассмотрим граф P2 O 2 (рис. З.2, а). Этот граф имеет одно ребро; очевидно, что любым минимальным реберным k-расширением этого графа будет 4-вершинный граф с k + 1 ребром. На рис. З.2, б изображены два его минимальных реберных 1-расширения, а на рис. З.2, г – минимальные реберные 2расширение. На рис. З.2, в изображены минимальные реберные 1-расширения для графов на рис. З.2, б. Видно, что один из этих графов является миP2 O 2, гой нет.

Предложенные примеры показывают, что ответ на поставленный вопрос является в общем случае отрицательным как для вершинных, так и для реберных расширений. Интерес представляет описание классов графов, для которых исследуемое утверждение является истинным. В частности, на данный момент не известно связных графов и несвязных графов без изолированных вершин, для которых утверждение было бы ложным. Однако круг нерешенных вопросов, связанных с минимальными вершинными и реберным kрасширениями графов, этим не исчерпывается.

СПИСОК ЛИТЕРАТУРЫ

Aldred R. A., McKay B. D., Wormald N. C. Small hypohamiltonian graphs // J. Comb. Math. Comb. Comput. – 1997. – Vol. 23. – P. 143–152.

Aviienis A. Design of fault-tolerant computers // AFIPS’67 Conf. Proc. – New York : ACM, 1967. – P. 733–743.

Aviienis A. Fault-Tolerant Computing : An Overview // IEEE Computer. – 1971.

Aviienis A. Fault-tolerance and fault-intolerance : Complementary approaches to reliable computing // Proc. Intern. Conf. on Reliable Software. – New York :

ACM, 1975. – P. 458–464.

Aviienis A., Chen L. On the implementation of N-version programming for software fault tolerance during execution // Proc. IEEE COMPSAC77. – New York : IEEE, 1977. – P. 149–155.

Aviienis A. The methodology of N-version programming // Software Fault Tolerance / ed. M. Lyu. – New York : John Wiley & Sons Ltd, 1995. – P. 23–46.

Aviienis A., Laprie J.-C., Randell B., Landwehr C. Basic Concepts and Taxonomy of Dependable and Secure Computing // IEEE Transactions on Dependable and Secure Computing. – 2004. – № 1. – P. 11–33.

Bender E. A., Canfield E. R. The asymptotic number of labeled graphs with given degree sequences // J. Comb. Th. A. – 1978. – Vol. 24. – P. 296–307.

Bondy J. A. Variations on the hamiltonian theme // Can. Math. Bull. – 1972. – Brinkmann G. Fast generation of cubic graphs // J. Graph Theory. – 1996. – Vol. 23, № 2. – P. 139–149.

Brinkmann G., Goedgebeur J., McKay B. D. Generation of cubic graphs // Discrete Math. Theor. Comput. Sci. – 2011. – Vol. 13, № 2. – P. 69–80.

Bruck J., Cypher R., Ho C. Fault-tolerant meshes with small degree // SIAM J.

Comput. – 1997. – Vol. 26, № 6. – P. 1764–1784.

Carter W.C., Bouricius W.G. A Survey of Fault Tolerant Computer Architecture and its Evaluation // IEEE Computer. – 1971. – Vol. 4, № 1. – P. 9–16.

Cin M. D., Hohl W., Sieh V. Hardware-Supported Fault Tolerance for Multiprocessors // Architecture of Computing Systems (ARCS’97). – New York :

ACM Press, 1997. – P. 13–22.

Cho H. J., Hsu L. H. Ring embedding in faulty honeycomb rectangular torus // Inform. Process. Lett. – 2002. – Vol. 84. – P. 277–284.

Chou R. S., Hsu L. H. 1-edge fault-tolerant designs for meshes // Parallel Process.

Lett. – 1994. – Vol. 4, № 4. – P. 385–389.

Choudum S. A., Sivagurunathan S. Optimal fault-tolerant networks with a server // Networks. – 2000. – Vol. 35, № 2. – P. 157–160.

Chvatal V. Flip-flops in hypohamiltonian graphs // Can. Math. Bull. – 1973. – Chuang Y. C., Chang C. H., Hsu L. H. Optimal 1-edge fault-tolerant designs for ladders // Inform. Process. Lett. – 2000. – Vol. 84, № 2. – P. 87–92.

Collier J. B., Schmeichel E. F. Systematic searches for hypohamiltonian graphs // Networks. – 1978. – Vol. 8. – P. 193–200.

Dependability : Basic Concepts and Terminology / ed. Laprie J.-C. – New York :

Springer-Verlag, 1992.

Despain A., Patterson D. X-tree : a tree structured multiprocessor computer architecture // Proc. of the Fifth Annual Symposium on Computer Architecture. – New York : ACM, 1978. – P. 144–151.

Doyen J., van Diest V. New families of hypohamiltonian graphs // Discrete Math. – 1975. – Vol. 13. – P. 225–236.

Dutt S., Hayes J. P. On designing and reconfiguring k-fault-tolerant tree architectures // IEEE Trans. Comput. – 1990. – Vol. 39. – P. 490–503.

Dutt S., Hayes J. P. Subcube allocation in hypercube computers // IEEE Trans.

Comput. – 1991. – Vol. 40. – P. 341–352.

Dutt S., Hayes J. P. Designing fault-tolerant systems using automorphisms // J.

Parallel Distrib. Comp. – 1991. – Vol. 12, № 3. – P. 249–268.

Encyclopedia of Parallel Computing / ed. D. A. Padua. – New York : Springer. – Farrag A. A., Dawson R. J. Designing optimal fault-tolerant star networks // Networks. – 1989. – Vol. 19. – P. 707–716.

Gaudin T., Herz J. C., Rossi P. Solution du probleme no. 29 // Rev. Franc. Rech.

Operat. – 1964. – Vol. 8. – P. 214–218.

Graham N., Harary F., Livingstoun M. L., Stout Q.F. Subcube fault tolerance in hypercubes // Inform. Comput. – 1993. – Vol. 102. – P. 280–314.

Grey O. A., Aviienis A., Renels D. A. A fault-tolerant architecture for network storage systems // Proc. of the 14 th Intern. Symp. on Fault-Tolerant Computer Systems. – Silver Spring : IEEE, 1984. – P. 232–239.

Gropp H. Enumeration of regular graphs 100 years ago // Discrete Math. – 1992. – Vol. 101. – P. 73–85.

Harary F., Palmer E. M. On similar points of a graph // J. Math. Mech. – 1966. – Vol. 15. – P. 623–630.

Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. – 1993. – Vol. 23. – P. 135–142.

Harary F., Khurum M. One node fault tolerance for caterpillars and starlike trees // Internet J. Comput. Math. – 1995. – Vol. 56. – P. 135–143.

Harary F., Hayes J. P. Node fault tolerance in graphs // Networks. – 1996. – Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans.

Comput. – 1976. – Vol.C.-25, № 9. – P. 875–884.

Hayes J. P. Fault tolerance in computers and graphs // Proc. 1 st Est. Conf. Graphs and Appl. – Tartu, 1993. – P. 77–89.

Hayes J. P. Computer architecture and organization. – New York : McGraw-Hill, Herz J. C., Duby J. J., Vigue F. Recherche systematique des graphes hypohamiltoniens // Theory of Graphs: Intern. Symp. / ed. P. Rosenstiehl. – Paris : Gordon and Breach, 1967. – P. 153–160.

Holton D., Sheehan J. The Petersen graph. – Cambridge : Cambridge University Horowitz E., Alessandro Z. The binary trees as an interconnection network : applications multiprocessor systems and VLSI // IEEE Trans. Comput. – 1981. – Vol. 30, № 4. – P. 247–253.

Hsu L. H., Lin C. K. Graph Theory and Interconnection Networks. – New York :

CRC Press, 2009.

Huang W. T., Chuang Y. C., Tan J. J., Hsu L. H. Fault-Free Hamiltonian Cycle in Faulty Mbius Cubes // Computation and Systems. – 2000. – Vol. 4, № 2. – Hung C. N., Hsu L. H., Sung T. Y. Christmas tree : a versatile 1-fault-tolerant design for token rings // Inform. Process. Lett. – 1999. – Vol. 72. – P. 55–63.

Hung C. N., Hsu L. H., Sung T. Y. On the construction of combined k-fault-tolerant hamiltonian graphs // Networks. – 2001. – Vol. 37, № 3. – P. 165–170.

Knight J. C., Leveson N. G. An experimental evaluation of the assumption of independence in multiversion programming // IEEE Trans. Softw. Eng. – 1986. – Vol. 12. – P. 96–109.

Ku H. K., Hayes J. P. Optimally edge fault-tolerant trees // Networks. – 1996. – Vol. 27. – P. 203–214.

Kwan C. L., Toida S. An optimal 2-FT realization of symmetric hierarchical tree systems // Networks. – 1982. – Vol. 12. – P. 231–239.

Laprie J.-C. Dependable Computing and Fault Tolerance : Concepts and Terminology // Proc. 15th IEEE Intern. Symp. Fault-Tolerant Computing (FTCSNew York : ACM, 1985. – P. 2–11.

Lindgren W. F. An infinite class of hypohamiltonian graphs // American Math.

Monthly. – 1967. – Vol. 74. – P. 1087–1089.

Livingston M., Stout Q. Distributing resources in hypercube computers // Proc. 3 rd Cong. on Hypercube Concurrent Computers and Appl. – New York : ACM, 1988. – P. 222–231.

Morris J. Automorphism Groups of Circulant Graphs – a Survey // Graph Theory in Paris. – Paris : Birkhuser Basel, 2006. – P. 311–325.

Mukhopadhyaya K., Sinha B. P. Hamiltonian graphs with minimum number of edges for fault-tolerant topologies // Inform. Process. Lett. – 1992. – Paoli M., Wong W. W., Wong C. K. Minimum k-hamiltonian graphs // J. Graph Theory. – 1984. – Vol. 8, № 1. – P. 155–165.

Paoli M., Wong W. W., Wong C. K. Minimum k-hamiltonian graphs II // J. Graph Theory. – 1986. – Vol. 10, № 1. – P. 79–95.

Patterson D. A., Gibson G., Katz R. H. A case for redundant arrays of inexpensive disks (RAID) // Proc. of the 1988 ACM SIGMOD Intern. Conf. on Management of Data. – New York : ACM, 1988. – Vol. 17, № 3. – Radjavi H., Rosenthal P. Graphs with isomorphic subgraphs // London Math. Soc.

(2). – 1972. – Vol. 6. – P. 70–72.

Read R. C. Some enumeration problems in graph theory. Doctoral thesis. London, Robinson R. W., Wormald N. C. Almost all cubic graphs are Hamiltonian // Random Structures Algorithms. – 1992. – № 3. – P. 117–125.

Skiena S. Implementing Discrete Mathematics : Combinatorics and Graph Theory with Mathematica. – Reading, MA : Addison-Wesley, 1990.

Sloane N. J. A., Plouffe S. The Encyclopedia of Integer Sequences. – San Diego :

Academic Press, 1995.

Sousselier R. Probleme no. 29: Le cercle des irascibles // Rev. Franc. Rech. Operat. – 1963. – Vol. 7. – P. 405–406.

Srinivasan K. Y., Sood A. K. Analysis and design of a fault-tolerant tree architecture // Intern. J. Electronics. – 1990. – Vol. 68, № 6. – P. 901–913.

Stockmeyer P. A census of non-reconstructable digraphs : six related families // J.

Comb. Th. B. – 1981. – Vol. 31. – P. 232–239.

Svoboda A. From Mechanical Linkages to Electronic Computers : Recollections from Czechoslovakia // A History of Computing in the Twentieth Century / Metropolis N., Howlett J., Rota G.C. New York : Academic Press, 1989. – Sung T. Y., Ho T. Y., Chang C. P., Hsu L. H. Optimal k-fault-tolerance network for token rings // J. Inform. Science and Engineering. – 2000. – № 16. – Sung T. Y., Lin C. Y., Chuang Y. C., Hsu L. H. Fault tolerant token ring embedding in double loop networks // Inform. Process. Lett. – 1998. – Vol. 66. – P.

Sung T. Y., Wang J. J., Hsu L. H. A family of trivalent 1-Hamiltonian graphs with diameter O(log n) // J. Of Information Science and Engineering. – 2001. – Vol. 17. – P. 535–548.

Thomassen C. Hypohamiltonian and hypotraceable graphs // Disc. Math. – 1974. – Thomassen C. On hypohamiltonian graphs // Disc. Math. – 1974. – Vol. 10. – Thomassen C. Hypohamiltonian graphs and digraphs // Theory and Application of Graphs, Lect. Notes in Math. № 642. – Berlin : Springer, 1978. – Thomassen C. Planar cubic hypohamiltonian and hypotraceable graphs // J. Comb.

Th. B. – 1981. – Vol. 30. – P. 36–44.

Tsai C.-H., Li T.-K. Two construction schemes for cubic Hamiltonian 1-nodehamiltonian graphs // Mathematical and Computer Modelling. – 2007. – Vol. 48. – P. 656–661.

von Neumann J. Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components // Automata Studies, ser. Annals of Mathematics Studies. Princeton, NJ : Princeton University Press, 1956. – Vol. 34. – P.

Wang J. J., Hung C. N., Hsu L. H. Optimal 1-hamiltonian graphs // Inform. Process. Lett. – 1998. – Vol. 65, № 3. – P. 157–161.

Wang J. J., Hung C. N., Tan J. J. M., Hsu L. H., Sung T. Y. Construction schemes for fault-tolerant hamiltonian graphs // Networks. – 2000. – Vol. 35, № 3. – Wong W. W., Wong C. K. Minimum k-hamiltonian graphs // J. Graph Theory. – 1984. – Vol. 8. – P. 155–165.

Wormald N. C. Triangles in labeled cubic graphs // Comb. Math. Lect. Notes in Math. – 1978. – № 687. – P. 337–345.

Wormald N. C. Enumeration of labeled graphs II. Cubic graphs with a given connectivity // London Math. Soc. (2). – 1979. – № 20. – P. 1–7.

Wormald N. C. The number of labeled cubic graphs with no triangles // Congr.

Numer. – 1981. – Vol. 33. – P. 359–378.

Zhang L. Fault tolerant networks with small degree // IEEE Transactions on Computers. – 2002. – Vol. 51, № 5. – P. 553–560.

Авиженис А. Отказоустойчивость – свойство, обеспечивающее постоянную работоспособность цифровых систем // Тр. Ин-та инженеров по электротехнике и радиоэлектронике. – 1978. – Т. 66, № 10. – С. 5–25.

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М. : Мир, 1979.

Басакер Р., Саати Т. Конечные графы и сети. – М. : Наука, 1973.

Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем.– М. : Наука, 1997.

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – Долгов А. А. О семействах точных вершинных k-расширений графов при k > // Материалы Международного молодежного научного форума «Ломоносов-2010». – М. : МАКС Пресс, 2010. – С. 30–32.

Долгов А. А. Семейство точных 2-расширений турниров // Прикладная дискретная математика. – 2010. – № 9. – С. 96–99.

Кабанов М. А. Об отказоустойчивых реализациях графов // Теоретические задачи информатики и ее приложений. – Саратов : Изд-во Сарат. ун-та, 1997. – Вып.1. – С. 50–58.

Каравай М. Ф. Применение теории симметрии к анализу и синтезу отказоустойчивых систем // Автоматика и телемеханика. – 1996. – № 6. – С. 159–173.

Каравай М. Ф. Инвариантно-групповой подход к исследованию k-отказоустойчивых структур // Автоматика и телемеханика. – 2000. – № 1. – С. 144–156.

Каравай М. Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. I. Одно-отказоустойчивые структуры // Автоматика и телемеханика. – 2004. – № 12. – С. 159–177.

Каравай М. Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. II. Решетки и k-отказоустойчивость // Автоматика и телемеханика. – 2005. – Киреева А. В. Отказоустойчивость в функциональных графах // Упорядоченные множества и решетки. – Саратов : Изд-во Сарат. ун-та, 1995. – Вып. 11. – С. 32–38.

Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы : построение и анализ / под ред. И. В. Красикова. – 2-е изд. – М. : Вильямс, 2005.

Курносова С. Г. Т-неприводимые расширения 3-, 4-, 5- и 6-вершинных графов / Сарат. гос. ун-т. – Саратов, 2003. – Деп. в ВИНИТИ 21.06.2003, № 1203-В2003. – 18 с.

Курносова С. Г. Каталог Т-неприводимые расширения для деревьем с числом вершин не более 10 / Сарат. гос. ун-т. – Саратов, 2004. – Деп. в ВИНИТИ 30.06.2004, № 1126-В2004. – 16 с.

Курносова С. Г. Т-неприводимые расширения полных бинарных деревьев // Вестн. Томск. гос. ун-та. Приложение. – 2005. – № 14. – С. 158–160.

Курносова С. Г. Т-неприводимые расширения объединений полных графов // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. – 2005. – Т. 5, вып. 1. – С. 107–115.

Курносова С. Г. Построение Т-неприводимых расширений для класса полных бинарных деревьев // Вестн. молодых ученых «Ломоносов». – М. :

МАКС Пресс, 2006. – Вып. III. – С. 58–66.

Липский В. Комбинаторика для программистов.– М. : Мир, 1988.

Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии.– М. : Мир, 1998.

Николаев А. Б., Подлазов В. С. Отказоустойчивое расширение системных сетей многопроцессорных вычислительных систем // Автоматика и телемеханика. – 2008. – № 1. – С. 162–170.

Пападимитру Х., Стайглиц К. Комбинаторная оптимизация, алгоритмы и сложность. – М. : Мир, 1995.

Пархоменко П. П. Передача сообщений в неисправных гиперкубах с использованием исправных подкубов // Автоматика и телемеханика. – 2000. – Рейнгольд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. Теория и практика.– М. : Мир, 1980.

Салий В. Н. Доказательства с нулевым разглашением в задачах о расширениях графов // Вестн. Томск. гос. ун-та. Приложение. – 2003. – № 6. – Салий В. Н. Оптимальные реконструкции графов // Современные проблемы дифференциальной геометрии и общей алгебры. – Саратов : Изд-во Сарат. ун-та, 2008. – С. 59–65.

Теслер Г. С. Решение проблемы гарантоспособности компьютерных систем в аспекте базисов компьютерной науки // Математичні машини і системи. – 2008. – № 4. – С. 171–188.

Харари Ф. Теория графов. – 4-е изд. – М. : Едиториал УРСС, 2009.

Харченко В. С. Гарантоспособность и гарантоспособные системы : элементы методологии // Радіоелектронні і комп‘ютерні системи. – 2006. – № 5 – Харченко В. С. Парадигмы и принципы гарантоспособных вычислений : состояние и перспективы развития // Радіоелектронні і комп‘ютерні системи. – 2009. – № 2(36). – С. 91–100.

Холл М. Комбинаторика.– М. : Мир, 1970.

ПУБЛИКАЦИИ АВТОРА

Абросимов М. Б. Об отказоустойчивости систем, представленных графами // Проблемы теоретической кибернетики : тезисы докладов XII международной конф. – М. : Изд-во МГУ, 1999.– С. 4.

Абросимов М. Б. О неизоморфных оптимальных 1-отказоустойчивых реализациях некоторых графов // Теоретические проблемы информатики и ее приложений.– Саратов : Изд-во Сарат. ун-та, 2000. – Вып. 3. – С. 3–10.

Абросимов М. Б. Минимальные расширения графов // Новые информационные технологии в исследовании дискретных структур : докл. 3-й Всерос. конф. с международным участием. – Томск : Изд-во СО РАН, 2000.

в ВИНИТИ 06.09.2000, № 2352-В00. – 26 с.

Абросимов М.Б. Об изоморфизме в отказоустойчивых реализациях систем, представленных графами // Материалы Межд. конф. студентов и аспирантов по фунд. наукам «Ломоносов». Вып. 5. М. : МГУ, 2000, С. 245.

(РЖ МАТ 2004 №10 04.10 – 13В.304) Абросимов М. Б. Минимальные расширения циклов с числом вершин не более одиннадцати / Сарат. гос. ун-т.– Саратов, 2001. – Деп. в ВИНИТИ 14.08.2001, № 1869-В2001. – 17 с.

Абросимов М. Б. Точные расширения графов с числом вершин не более одиннадцати / Сарат. гос. ун-т. – Саратов, 2001. – Деп. в ВИНИТИ 14.08.2001, № 1870-В2001. – 15 с.

Абросимов М. Б. Минимальные расширения дополнений графов // Теоретические проблемы информатики и ее приложений. – Саратов : Изд-во Сарат. ун-та, 2001. – Вып. 4. – С. 11–19.

Абросимов М. Б. Минимальные расширения объединений некоторых графов // Теоретические проблемы информатики и ее приложений.– Саратов :

Изд-во Сарат. ун-та, 2001. – Вып. 4.– С. 3–11.

Абросимов М. Б. Точные k-расширения графов // Современные проблемы информатизации в технике и технологиях : Труды VI Международной открытой научной конференции, Воронеж: 2001, С. 57.

Абросимов М. Б. О минимальных расширениях графов, содержащих изолированные вершины // Вестн. Томск. гос. ун-та. Приложение. – 2002. – № 1(II). – С. 24–29.

Абросимов М. Б. О минимальных расширениях несвязных графов // тез. докл.

междунар. конф. Компьютерные науки и информационные технологии.

– Саратов : Изд-во Сарат. ун-та, 2002. – С.5–6.

Абросимов М. Б. Минимальные k-расширения предполных графов // Изв. вузов. Математика. – 2003. – № 6(493). – С. 3–11.

Абросимов М. Б. О неизоморфных минимальных реберных 1-расширениях циклов // Современные проблемы информатизации в технике и технологиях: Труды VIII Международной открытой научной конференции, Воронеж: 2003, С. 21- Абросимов М. Б. О неизоморфных минимальных реберных 1-расширениях графов // Теоретические проблемы информатики и ее приложений. – Саратов : Изд-во Сарат. ун-та, 2004. – Вып 6. – С. 3–9.

Абросимов М. Б. Минимальные реберные 1-расширения некоторых графов // Дискретный анализ и исследование операций : Материалы конференции. – Новосибирск : 2004, С. 101.

Абросимов М. Б. О симметрии и точных расширениях графов / Проблемы теоретической кибернетики. Тезисы докладов XIV Международной конференции (Пенза 23-28 мая 2005 г.) - М.: МГУ, 2005, С. 7.

Абросимов М. Б. Минимальные расширения транзитивных турниров // Вестн.

Томск. гос. ун-та. Приложение. – 2006. – № 17. – С. 187–190.

Абросимов М. Б. Некоторые вопросы о минимальных расширениях графов // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика.

– 2006. – Т. 6, вып. 1/2. – С. 86–91.

Абросимов М. Б. Минимальные расширения неориентированных звезд // Теоретические проблемы информатики и ее приложений. – Саратов : Издво Сарат. ун-та, 2006. – Вып 7. – С. 3–5.

Абросимов М. Б. Минимальные расширения некоторых турниров // Актуальные проблемы математики, механики, информатики: матер. Междунар.

науч.-метод. конф., посвященной 90-летию высшего математического образования на Урале (Пермь, 9-15 окт. 2006 г.). Пермь : ПГУ, 2006. – Салий В. Н., Абросимов М. Б., Курносова С. Г. Графовые модели отказоустойчивости дискретных систем // Высокие технологии, фундаментальные и прикладные исследования, образование: Сб. трудов Второй международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности». 07СПб, 2006. – С. 54-55.

Абросимов М. Б., Долгов А. А. Точные расширения некоторых турниров // Вестн. Томск. гос. ун-та. Приложение. – 2007. – № 23. – С. 211–216.

Абросимов М. Б. О реберных расширениях некоторых предполных графов // Компьютерные науки и информационные технологии : Тез. докл. Междунар. науч. конф. – Саратов: Изд-во Сарат. ун-та, 2007. – С. 5–6.

Абросимов М. Б., Гильман Е. А. Некоторые решения на основе SCADA- системы «КИРАС»// Автоматизация в промышленности. – 2007. – № 4. – Абросимов М. Б., Гильман Е. А., Кривоносов А. А. Инструментальные средства для моделирования ТП и разработки тренажерных комплексов // Автоматизация в промышленности. – 2007. – №8. – С. 43–45.

Абросимов М. Б., Долгов А. А. Семейства точных расширений турниров // Прикладная дискретная математика. – 2008. – № 1. – С. 101–107.

Абросимов М.Б. Минимальные расширения направленных звезд // Проблемы теоретической кибернетики. Тезисы докладов XV международной конференции (Казань, 2-7 июня 2008 г.). – Казань: Отечество, 2008. – С. 2.

Абросимов М. Б., Гильман Е. А. Мнемосхемные комплексы на основе SCADA-системы «КИРАС» // Автоматизация в промышленности. – Абросимов М.Б., Гильман Е.А. Новые возможности инструментальных средств УТК для разработки тренажерных комплексов // Автоматизация в промышленности. – 2008. – № 7. – С. 54-55.

Абросимов М. Б., Долгов А. А. Практические задания по графам. – Саратов :

Научная книга. – 2008.

Абросимов М. Б., Долгов А. А. О реконструируемости малых турниров // Изв.

Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. – 2009. – Т. 9, вып. 2. – С. 94–98.

Абросимов М. Б. О реберных расширениях некоторых предполных графов // Компьютерные науки и информационные технологии: Материалы Междунар. науч. конф. – Саратов: Изд-во Сарат. ун-та, 2009. – С. 3–5.

Абросимов М. Б. О вычислительной сложности расширений графов // Прикладная дискретная математика. Приложение. – 2009 №1. – С. 94–95.

Абросимов М. Б. Об NP-полноте задач о вершинных и реберных расширениях графов // Дискретная математика, алгебра и их приложения: Тез.

докл. Междунар. науч. конф. Минск, 19–22 октября 2009 г. – Мн.: Институт математики НАН Беларуси, 2009. – С. 72–74.

Абросимов М. Б., Долгов А. А. О бесконтурных точных расширениях// Изв.

Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. – 2010. – Т. 10, вып. 1. – С. 83–88.

Абросимов М. Б. Минимальные реберные расширения некоторых предполных графов // Прикладная дискретная математика. – 2010. – № 1. – С. 105–117.

Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. – 2010. – Т. 88, вып. 5. – С. 643–650.

Абросимов М. Б., Комаров Д. Д. Минимальные реберные расширения сверхстройных деревьев с малым числом вершин / Сарат. гос. ун-т. – Саратов, 2010. – Деп. в ВИНИТИ 18.10.2010 № 589-В2010. – 27 с.

Абросимов М. Б., Комаров Д. Д. Минимальные вершинные расширения сверхстройных деревьев с малым числом вершин / Сарат. гос. ун-т. – Саратов, 2010. – Деп. в ВИНИТИ 18.10.2010 № 590-В2010. – 38 с.

Абросимов М. Б. О минимальных реберных 1-расширениях направленных звезд // Российская конференция «Дискретная оптимизация и исследование операций»: Материалы конференции (Алтай, 27 июня – 3 июля 2010). – Новосибирск: Изд-во Ин-та математики, 2010. – C. 127.

Абросимов М. Б., Гильман Е. А., Кривоносов А. А., Ерхов А. В. О разработке и внедрении тренажера для установки дегидрирования изобутана // Автоматизация в промышленности. – 2010. – № 7. – С. 66–68.

Абросимов М. Б., Бондаренко П. П. Исследование минимальных вершинных и реберных 1-расширений цепей с вершинами двух типов // Свидетельство о государственной регистрации программы для ЭВМ № 2010616497, выданное Роспатентом. Зарегистрировано в Реестре программ для ЭВМ 30.09.2010.