Минимальные расширения графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА 1. НЕИЗОМОРФНЫЕ МИНИМАЛЬНЫЕ РАСШИРЕНИЯ ГРАФОВ.

§ 1. Основные понятия и вспомогательные утверждения.

§ 2. Наименьшие графы с неизоморфными минимальными расширениями.

§ 3. Минимальные расширения циклов.

3.1. Неизоморфные минимальные расширения циклов.

3.2. Негамильтоновы минимальные расширения циклов.

ГЛАВА 2. МИНИМАЛЬНЫЕ РАСШИРЕНИЯ ДОПОЛНЕНИЙ ГРАФОВ.

§ 1. Определения и постановка задачи.

§ 2. Свойство дополнительности k-расширения графа.

2.1. Дополнительность расширения.

2.2. Дополнительность ^-расширения.

§ 3.Точные к-расширения графов.

ГЛАВА 3. МИНИМАЛЬНЫЕ РАСШИРЕНИЯ СОЕДИНЕНИЙ ГРАФОВ.

§ 1. Основные определения и постановка задачи.

§ 2. Соединения с одновершинным графом.

2.1. Предполные графы.

2.2. Минимальные расширения.

2.3. Минимальные ^-расширения.

§ 3. Соединения графа и его минимального расширения.

ГЛАВА 4. МИНИМАЛЬНЫЕ РАСШИРЕНИЯ ОБЪЕДИНЕНИЙ ГРАФОВ.

§ 1. Основные определения и постановка задачи.

§ 2. Объединения графов с цепями.

2.1. Цепь и вполне несвязный граф.

2.2. Объединения цепей.

2.3. Сверхстройные деревья.

§ 3. Минимальные расширения объединений циклов.

§ 4. Объединения с вполне несвязными графами.

§ 5. Объединения графа и его минимального расширения.

В данной работе вводится в рассмотрение и исследуется конструкция минимального расширения графа, основанная на идеях формализации понятия отказоустойчивости технических систем, предложенных в 1976 году Хейзом [20].

Согласно Авиженису [3] можно выделить два подхода для повышения надежности реальных вычислительных систем: предотвращение ошибок и отказоустойчивость. Первое направление связано с уменьшением вероятности возникновения ошибки и состоит в разработке высоко-надежных компонент системы. Во втором - используется введение в систему избыточных структур для придания ей дополнительных свойств отказоустойчивости.

Впервые понятие отказоустойчивости было введено Авиженисом (см. [2], [48]) как обеспечение системы способностью противостоять ошибке и возможностью продолжать работу в присутствии этой ошибки. Выделяют следующие уровни отказоустойчивости:

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

2) амортизация отказов - система продолжает работать в присутствии ошибок с частичной деградацией функциональных возможностей.

В рамках первого направления в 1976 году Хейз предложил модель для исследования отказоустойчивости, основанную на графах.

Графом (далее: ориентированным графом) называется пара G = (F, а), где V— непустое множество, называемое множеством вершин, а а - отношение на множестве вершин V, называемое отношением смежности. Граф с симметричным и антирефлексивным отношением смежности называется неориентированным графом (везде далее просто графом). Если (u,v)ea, то говорят, что вершины и и v смежны и эти вершины соединены ребром (и, v). При этом (и, v) и (v, и) это одно и то же ребро, которое обозначают {и, v}. Граф, любые две вершины которого смежны, называется полным и обозначается Кщ.

Граф с пустым отношением смежности а называется вполне несвязным и обозначается О^.

Степенью вершины v в неориентированном графе G будем называть количество вершин в G, смежных с данной, и обозначать через d(v). Вектор, составленный из степеней вершин графа G в порядке их убывания, называется вектором степеней. Говорят, что граф является реализацией своего вектора степеней. Однородным или регулярным w-вершинным графом Rnp порядка р называют граф, в котором все степени вершин равны р.

Путем в графе G = (V, а) называется последовательность вершин и ребер вида v0,{v0,v1},v1,.,{vn1,vn},v„. При этом говорят, что v0 - начальная вершина пути, a v„ - конечная. Говорят также, что путь соединяет вершины vo и v„ и вершина vn достижима из v0. Путь, каждая вершина которого принадлежит не более чем двум его ребрам, считается простым. Если начальная вершина простого пути совпадает с конечной, путь называют циклом, в противном случае - цепью. Цикл или цепь, содержащие все вершины графа, называются гамильтоновыми. Граф, содержащий гамильтонов цикл, также называется гамильтоновым.

Будем считать, что каждая вершина достижима из самой себя. Тогда отношение достижимости является отношением эквивалентности на множестве вершин графа. Классы этого отношения называются компонентами связности графа. Граф с универсальным отношением достижимости называется связным. Связный граф без циклов называется деревом.

Цепью Рп называется граф G = (V,a), где V= {vi, v2, ., v„}, и a= {(v/, v,-): \i-j\ = 1}, а циклом Cn - граф G = (V, а), где V- {vb v2, ., v„}, и «= (Оь vj)- \i~j\ = 1} U {(vb Vn), (v„,v,)}.

Подграфом графа G = (F, а) называется пара G = (V, а'), где F'cFh

V'xV')na. Подграф графа G называется максимальным, если он получается из G удалением одной вершины и всех связанных с нею ребер.

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

Вложением графа G\ = (V\, сс\) в граф G2 = (V2, ccj) называется такое взаимно однозначное отображение / : Vx -> V2, что для любых вершин и, v е V\ выполняется следующее условие: (и, v) е а\ (flu\AvУ) е ai

Два графа G\ = (Fb а{) и G2 — (V2, а2) называются изоморфными, если можно установить взаимно однозначное соответствие /: Vx —»V2, сохраняющее отношение смежности: (и, v) е й] « (fiu)->Av)) е а2, для любых и, v е V\. В этом случае пишут G\ = G2.

Граф, вершинам которого приписаны метки, называется помеченным. Непомеченным или абстрактным графом называется класс изоморфных графов.

Технической системе Z сопоставим помеченный граф G(Z), вершины которого соответствуют элементам системы S, ребра - связям между элементами, а метки указывают тип элементов. Под отказом элемента технической системы Z понимается удаление соответствующей ему вершины из графа системы G(Y) и всех связанных с ней ребер.

Говорят, что система I* является k-отказоустойчиеой реализацией системы Е, если отказ любых к элементов системы Е* приводит к графу, в который можно вложить граф системы Е с учетом меток вершин. Построение ^-отказоустойчивой реализации системы Z можно представить себе как введение в нее определенного числа новых элементов и связей. При этом предполагается, что в нормальном режиме работы избыточные элементы и связи маскируются, а в случае отказа происходит реконфигурация системы до исходной структуры. Следует заметить, что процесс реконфигурации в общем случае (с учетом частичной деградации функциональных возможностей системы) является достаточно сложной процедурой и составляет самостоятельную область исследования (см. например, [30], [11], [14], [58]).

Для нас далее представляет интерес оптимизация ^-отказоустойчивой реализации.

Пусть в системе £ встречается t различных типов элементов. Очевидно, что любая ее ^-отказоустойчивая реализация должна содержать не менее к дополнительных элементов каждого типа. Легко видеть, что такого числа дополнительных элементов достаточно для построения ^-отказоустойчивой реализации системы В самом деле, добавим к элементов каждого типа и соединим их все между собой и с элементами системы Тогда любой отказавший элемент можно будет заменить одним из добавленных элементов соответствующего типа. Далее построенную таким образом

-отказоустойчивую реализацию будем называть тривиальной.

-отказоустойчивая реализация X системы X, состоящей из t элементов различного типа, называется оптимальной, если система L отличается от системы Z на к элементов каждого из t типов системы X, и среди всех ^-отказоустойчивых реализаций с тем же числом элементов, система X* имеет наименьшее число ребер.

На практике элементы технических систем часто оказываются однотипными. Так, если рассматриваются многопроцессорные системы, то элементами являются процессоры; в распределенных вычислениях элементами могут являться компьютеры; в многоагентных интеллектуальных системах -интеллектуальные агенты. При исследовании отказоустойчивости в подобных системах метки элементов опускаются и в качестве графа системы рассматривается граф без меток. В этом случае оптимальная ^-отказоустойчивая реализация будет содержать в точности к дополнительных элементов.

Данный подход впервые был изложен Хейзом в работе [20]. Там же были предложены процедуры построения оптимальной ^-отказоустойчивой реализации для цепи, цикла и помеченного дерева. Позднее, Хейз совместно с Харари обобщили модель на случай отказов связей между элементами, предложив понятие реберной отказоустойчивости [17]. Модель отказоустойчивости, в которой рассматриваются только отказы элементов, было предложено называть вершинной отказоустойчивостью [19]. Последующее расширение модели связано с рассмотрением как отказов элементов, так и связей между ними. Подобная модель, называемая комбинированной отказоустойчивостью, рассматривается в работах [24], [25], [37], [26], [36] и [43].

А.В.Киреева рассматривала вершинную отказоустойчивость в ориентированных графах [54]. Ею описана вершинная оптимальная

1-отказоустойчивая реализация произвольного функционального графа. Санг и другие [37] использовали модель Хейза для нахождения вершинной и реберной оптимальной 1-отказоустойчивой реализации ориентированного цикла.

М.Ф.Каравай рассматривает вершинную отказоустойчивость с несколько иной интерпретацией отказа элементов [52], [53]: отказавший элемент исключается из модели, однако все его связи сохраняются, что приводит к новой системе, в которой каждая пара элементов, связанных с отказавшим, также будет связана.

На сегодняшний день не известно полиномиального алгоритма построения и 1 uw 1 оптимальной А:-отказоустоичивои реализации для произвольного графа. Считается, что задача относится к классу jVP-полных задач. В связи с этим последующее развитие исследований связано с описанием оптимальных ^-отказоустойчивых реализаций для наиболее интересных с точки зрения практического применения классов графов. Таковыми являются деревья и циклы.

Деревья. Задачу описания оптимальных ^-отказоустойчивых реализаций деревьев сформулировал Хейз [20]. Там же была предложена вершинная оптимальная 1-отказоустойчивая реализация для полного и-арного дерева с метками. Кван и Тойда [28] описали схему построения оптимальной

2-отказоустойчивой реализации для полного бинарного дерева с метками. Сложность задачи для общего случая привела к понятию почти оптимальной к-отказоустойчивой реализации [10]. Задача нахождения реберной оптимальной ^-отказоустойчивой реализации дерева исследуется в работе [27].

Для деревьев без меток следует отметить результат М.А.Кабанова, предложившего схему построения вершинной оптимальной 1-отказоустойчивой реализации для частного случая дерева - цепи колес [51].

Циклы. Задача нахождения оптимальных ^-отказоустойчивых реализаций циклов впервые была решена Хейзом в [20]. В работе [19] Харари и Хейз поставили задачу нахождения оптимальных ^-отказоустойчивых реализаций циклов, отличных от тех, что были предложены в [20]. Махопадха и Синха [31] указали первое такое семейство оптимальных 1-отказоустойчивых реализаций циклов. Ряд других семейств приводится в работах [24], [25], [26], [32], [36], [44], [42], [43]. Заметим, что только схемы построения, предложенные Хейзом, Махопадхой и Синхой, позволяют указать оптимальную 1-отказоустойчивую реализацию для цикла с любым числом вершин, в том числе и для цикла с четным числом вершин. В данной работе будет предложена еще одна схема построения оптимальной 1-отказоустойчивой реализации для цикла с любым числом вершин, отличная от схем Хейза и Махопадхи и Синхи.

Отдельно следует выделить исследования, связанные с нахождением оптимальной 1-отказоустойчивой реализации ориентированного цикла, в работе [37].

Особый интерес в рамках данного направления представляет описание негамильтоновых минимальных 1-расширений циклов. Эти исследования тесно связаны с поиском гипогамилътоновых графов, то есть негамильтоновых графов, каждый максимальный подграф которых является гамильтоновым.

Задача нахождения гипогамильтоновых графов была сформулирована в 1963 году Сусельером [35]. Год спустя Годин, Херц и Росси [13] показали, что наименьшим гипогамильтоновым графом является граф Петерсена. Позднее исчерпывающий компьютерный поиск показал, что не существует гипогамильтоновых графов с числом вершин 11, 12 [22], 14 [8] и 17 [1]. С другой стороны, были найдены гипогамильтоновы графы с числом вершин п = 10, 13, 15 и 16, а также для всех п > 18 (см. [5], [7], [9], [22], [23], [29], [38], [39]). Подробный обзор вопроса можно найти в книге Холтона и Шихана [23], последний результат - об отсутствии 17-вершинных гипогамильтоновых графов - содержится в работе Алдреда, Маккея и Вормальда [1].

Результаты, полученные при исследовании оптимальных Аг-отказоустойчивых реализаций графов, оказались тесно переплетены с результатами, полученными в рамках «чистой» теории графов. В рамках технической диагностики задача описания оптимальных ^-отказоустойчивых реализаций рассматривается для графов, являющихся моделями технических систем, что накладывает ограничение на класс графов, представляющих интерес для исследования. В данной работе конструкция вершинной оптимальной ^-отказоустойчивой реализации рассматривается как абстрактная конструкция над графами. Следующие определения вводят соответствующие понятия.

Назовем граф GR = (VR, aR) к-расширением графа G = (V, а), если граф G можно вложить в каждый подграф графа GR, получающийся удалением любых его к вершин и всех связанных с ними ребер. Определение не теряет смысла и при к = 0.

Граф Gt = (Vh at) называется тривиальным к-расширением графа G = ( V, а), если граф Gt получается из графа G добавлением к вершин, соединением их со всеми вершинами графа G и друг с другом, иначе говоря, граф Gt есть соединение графа G и полного графа Кк = (Fk, ак):

Gt = (Vt, at) = (Vv Vk, au ak\J Fx Vku Vkx V).

Очевидно, что тривиальное ^-расширение графа является и его

-расширением. £ ^

Граф G = (V, а ) называется вершинным минимальным к-расширением «-вершинного графа G = (V, а), если выполняются следующие условия:

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

2. G* содержит п+к вершин, то есть | V\ = | V\ + к;

3. а имеет минимальную мощность при выполнении условий 1) и 2).

Аналогично можно дать определения для реберного и еершинно-реберного (<комбинированного) минимального ^-расширения. В этой работе везде далее мы будем рассматривать только вершинные минимальные ^-расширения (далее просто минимальные к-расширения).

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

•{»т

Пусть G - некоторый граф, a G - его минимальное ^-расширение. Обозначим через (G)*k результат операции получения минимального ^-расширения графа G. Тогда если граф G имеет единственное минимальное ^-расширение, то (G)*k = G*k. В противном случае, результат операции получения минимального ^-расширения считается не определенным для графа G. Будем использовать для операции получения минимального 1-расширения обозначение (G)*.

Настоящая работа посвящена исследованию конструкции минимального ^-расширения и соответствующей операции. Основное внимание сосредоточено на исследовании связи введенной конструкции и алгебраических операций над графами: дополнения (глава 2), соединения (глава 3) и объединения (глава 4). Отдельное внимание уделяется случаям, когда граф имеет неизоморфные минимальные ^-расширения.

Работа состоит из введения, четырех глав, содержащих 14 параграфов, библиографии, включающей 71 наименование, и трех приложений. Диссертация изложена на 117 страницах.

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

2. Avizienis A. The design of fault tolerant computers // AFIPS Conference Proceedings. 1967. - P.733-743.

3. Avizienis A. Fault Tolerant and fault-intolerance: complementary approaches to reliable computing // Proc. Int. Conf. on Reliable Software in SigPlan Notices. -1975. -P.458-464.

4. 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.

5. Bondy J.A. Variations on the hamiltonian theme // Can. Math. Bull. 1972. -Vol.15, №1. -P.57-72.

6. Chou R.S., Hsu L.H. 1-edge fault-tolerant design for meshes // Parallel Process. Lett. 1994. - Vol.4, №4. - P.385-389.

7. Chvatal V. Fip-flops in hypohamiltonian graphs // Can. Math. Bull. 1973. -Vol.16, №1.-P.33-41.

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

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

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

11. Dutt S., Hayes J.P. Subcube allocation in hypercube computers // IEEE Trans. Comput. 1991. - Vol.40. - P.341-352.

12. Dutt S., Hayes J.P. Designing fault-tolerant systems using automorphisms // J. Parallel Distrib. Сотр. 1991. - Vol. 12., №3. - P.249-268.

13. Gaudin Т., Herz J.C., Rossi P. Solution du probleme no. 29 // Rev. Franc. Rech. Operat. 1964. - Vol.8. -P.214-218.

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

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

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

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

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

19. Harary F., Hayes J.P. Node fault tolerance in graphs // Networks. 1996. -Vol.27.-P.19-23.

20. Hayes J.P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. - Vol.C.-25, №9. - P.875-884.

21. Hayes J.P. Fault tolerance in computers and graphs // Proc. 1st Est. Conf. Graphs and Appl. Tartu Kaariku, May 12-19, 1991. - Tartu, 1993. - P.77-89.

22. Herz J.C., Duby J.J., Vigue F. Recherche systematique des graphes hypohamiltoniens // Proc. 1966 Internl. Symp. in Rome P.Rosethiel, ed., Dunod, Paris. 1967. P.153-160.

23. HoltonD., SheehanJ. The Petersen graph, Australian Mathematical Society Lecture Series, Number~7, Cambridge University Press, Cambridge, 1993.

24. Huang W.T., Chuang Y.C., Tan J.J., Hsu L.H. Fault-free hamiltonian cycle in faulty mobius cubes // Computacion у Sistems. 2000. - Vol.4, №2. -P.106-114.

25. HungC.N., HsuL.H., Sung T.Y. Christmas tree: a versatile 1-fault-tolerant design for token rings // Inform. Process. Lett. 1999. - Vol.72. P.55-63.

26. 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.

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

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

29. Lindgren W.F. An infinite class of hypohamiltonian graphs // American Math. Monthly. 1967. - Vol.74. -P.1087-1089.

30. Livingston M. Stout Q. Distributing resources in hypercube computers // Proc. 3rd Cong. on Hypercube Concurrent Computers and Appl. 1988. - P.222-231.

31. Mukhopadhyaya K., Sinha B.P. Hamiltonian graphs with minimum number of edges for fault-tolerant topologies // Inform. Process. Lett. 1992. - Vol.44. -P.95-99.

32. Paoli M., Wong W.W., Wong C.K., Minimum k-Hamiltonian graphs II // J. Graph Theory. 1986. -№10. -P.79-95.

33. ReadR.C. Some enumeration problems in graph theory. Doctoral thesis. London, 1958.

34. Robinson R.W., Wormald N.C. Almost all cubic graphs are Hamiltonian // Random Structures Algorithms. 1992. - № 3. - P. 117-125.

35. SousselierR. Probleme no. 29: Le cercle des irascibles // Rev. Franc. Rech. Operat. 1963. - Vol.7. - P.405-406.

36. 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. - P.381-390.

37. 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.201-207.

38. Thomassen С. Hypohamiltonian and hypotraceable graphs // Disc. Math. -1974.-Vol.9.-P.91-96.

39. Thomassen C. On hypohamiltonian graphs // Disc. Math. 1974. - Vol.10. -P.383-390.

40. Thomassen C. Hypohamiltonian graphs and digraphs // Theory and Application of Graphs, Lect. Notes in Math. 1978. - Vol.642. - P.557-571.

41. Thomassen C. Planar cubic hypohamiltonian and hypotraceable graphs // J. Comb. Th. B. 1981. - Vol.30. -P.36-44.

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

43. 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. -P.233-245.

44. Wong W.W., Wong C.K., Minimum k-hamiltonian graphs // J. Graph Theory. -1984.-Vol.8.-P.155-165.

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

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

47. Wormald N.C. The number of labeled cubic graphs with no triangles // Congr. Numer.- 1981.-Vol.33.-P.359-378.

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

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

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

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

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

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

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

55. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. М.: Наука, 1990.

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

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

58. Пархоменко П.П. Передача сообщений в неисправных гиперкубах с использованием исправных подкубов // Автоматика и телемеханика. -2000. №10. - С.171-182.

59. Рейнгольд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. Теория и практика-М.: Мир, 1980.

60. Харари Ф., Палмер Э. Перечисление графов М.: Мир, 1977.

61. Холл М. Комбинаторика-М.: Мир, 1970.Результаты диссертации опубликованы в следующих работах:

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

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

64. Абросимов М.Б. Минимальные расширения графов // Новые информационные технологии в исследовании дискретных структур. -Томск, 2000.- С.59-64.

65. Абросимов М.Б. Минимальные расширения 4-,5-,6- и 7-вершинных графов.- Саратов: СГУ, 2000.- 26с.; Деп. в ВИНИТИ 06.09.2000, №2352-В00.

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

67. Абросимов М.Б. Минимальные расширения некоторых деревьев // Управляющие и вычислительные системы. Новые технологии: Материалы межвузовской электронной научно-практической конференции. Вологда: ВоГТУ, 2001. - С.56-57.

68. Абросимов М.Б. Минимальные расширения циклов с числом вершин не более одиннадцати- Саратов: СГУ, 2001 17с.; Деп. в ВИНИТИ 14.08.2001, №1869-В2001.

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

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

71. Абросимов М.Б. Минимальные расширения объединений некоторых графов // Теоретические проблемы информатики и ее приложений.-Саратов: СГУ, 2001 Вып.4 -С.3-11.