Точные расширения графов

В прикладной теории графов особое место занимают задачи нахождения графов, подграфы которых обладают определенными свойствами. Одной из самых известных таких задач является задача описания графов, каждый максимальный подграф которых содержит гамильтонов цикл. Данную задачу можно* обобщить и рассматривать графы, каждый максимальный подграф которых содержит в качестве своей части, заданный* граф. Графы такого вида оказались очень полезнымипри описаниии конструировании отказоустойчивых' систем.

В 1976 году Хейзом была предложена модель отказоустойчивости, основанная, на* графах [б]. Технической-системе Е сопоставляется граф С/(Е), вершины которого соответствуют элементам системы Е, ребра — связям между элементами. В общем случае элементы могут быть. разного типа, однако чаще всего на практике элементы системы оказываются однотипными. Говорят, что система Е* является к-отказоустойчивой реализацией системы ?, если отказ.

1(любых к элементов системы Е приводит к графу, в который можно вложить граф системы Е.

Предложенная Хейзом > модель может быть использована для исследования полной' отказоустойчивости системы, то есть возможности продолжения ее работы без потери-функциональных свойств при отказе одного или нескольких элементов [1]. В зависимости от интерпретации отказа-в данной модели рассматривают несколько видов отказоустойчивости. Вершинная отказоустойчивость предполагает в качестве отказа рассматривать отказ элемента [5, 6]. Реберная отказоустойчивость * рассматривает отказы" связей между элементами [4].

В «чистой» теории графов для.' формализации понятий отказоустойчивости системы используется абстрактная конструкция — расширение графа. Основным объектом исследования в данной работе является частный случай расширения графа — точное расширение.

Ориентированным графом {орграфом или просто графом) Ф называется пара (V, а), где V — конечное непустое множество (множество вершин), а, а — отношение в множестве V (отношение смежности). Неориентированным графом (неографом) называется орграф с антирефлексивным и симметричным отношением смежности. Элементы множества, а называются дугами для" орграфа и ребрами для неориентированного графа.' Орграф Э = (?V, а) называется направленным графом или диграфом, если его отношение, а антисимметрично, то есть нет встречных дуг за исключением, быть" может, петель. Полный' диграф? без петель называется турниром. У турнира' между любыми"-двумя различными вершинами существует в-точности одна дуга.

Неориентированный граф, любые две вершины которого смежны, называется яаяньш и обозначается Кп. Граф с пустым отношением смежности «называется вполне несвязным или нулъграфом и обозначается Оп.

Подграфом графа О = (V, а) называется пара (V, а*), где Гс Ки а' = (V х V) п а. Подграф графа- (7 называетсямаксимальным, если он получается (из О удалением одной вершиньь и всех связанных с нею ребер. Будем обозначать через (? — V максимальный подграф, получающийся из графа & удалением, вершины V. Список максимальных подграфов графа С7 называют его колодой.

Два графа = а{) и С?2 = (Уг, оь) называются изоморфными, если можно установить взаимно однозначное соответствие /: V] —> У2, сохраняющее отношение смежности: (и, у) е, а <=> (/[и), Ду)) <е ог2> для любых и, v е У. В этом случае пишут С^ = (?2.

Изоморфизм графа на себя называется" автоморфизмом. Тождественное отображение является автоморфизмом для любого графа. Множество автоморфизмов графа С? относительно операции суперпозиции автоморфизмов и их обращения как взаимно однозначных преобразований на множестве вершин <7 образуют группу АиІ^СТ).

Вложением графа О = (Уи0і) в граф — а2) называется такое инъективное отображение /: Кі —> У2, что для любых вершин м, у е У выполняется следующее условие: (и, v) є а :=> (Дм), Ду)) є а2.

Назовем іраф бд = (Уд, (вершинным) к-расширением графа О = (К, (X) — еслиграф Сг можно вложить, вкаждый подграф графа получающийся удалениемлюбых его к вершин и всех связанныхс. ними ребер. Заметимчто определение не теряет смысла и при? к = 0: Если? Е с V, то будем обозначать, через (7 — граф, получающийся из графа Є удалениемвсех вершинпринадлежащих Е, и связанных с ними ребер.

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

1) — граф О* является Аг-расширением графа О, то есть граф Сг вкладывается в-каждый подграф графа, б1*, получающийся удалением любых его к вершин;

2) У*^п + к-.: ' ' .

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

Частным случаем1 минимального расширения" графа является точное расширение. • Граф ів называется точным (вершинным) к-расширением графа бу если граф С? изоморфен каждому подграфу графа//, получающемуся путем удаления любых его А: вершин и всех связанных с ними дуг. При А: = 1 будем? говорить, просто о расширении графа., .

Понятие точного* расширения графа (точной! отказоустойчивой реализации) — было введеноХарари и. Хейзом вработе 1996 года- [5]. Следует обратить внимание на то, что подход к изучению точных расширенийкоторый используется в этой статье, отличается от подхода к изучению минимальных расширенийграфов. В случае минимального расширения обычно рассматривается интересный с практической точки зрения класс графов и описываются способы построения минимальных расширений для графов из заданного класса. Подход этот оправдан, поскольку минимальное расширение можно построить для любого заданного графа [5], а задача построения минимального расширения является вычислительно сложной [20].

Точное расширение графа интересно само по себе, как граф, в колоде которого содержатся только изоморфные максимальные подграфы. Харари и Хейзу удалось ответить на вопрос о том, какой вид имеют точные расширения неориентированных графов и предложить два семейства точных^{-расширений} неориентированных графов для любого к > 0. Это полные неориентированные графы Кп и вполне несвязные графы Оп. Однако стоит отметить, что графы с изоморфными подграфами вызывали интерес задолго до выхода статьи Харари и Хейза. Результаты, полученные Раджави и Розенталем в 1972 году [13], позволяют утверждать, что никакой граф кроме Оп и К&bdquoне может быть точным^{-расширением} неориентированного графа при к> 1.

При изучении минимальных расширений изучалось свойство дополнительности расширения: граф обладает этим свойством, если дополнение его минимального расширения является минимальным расширением дополнения самого' графа. В неориентированном случае, как удалосьпоказать М. Б. Абросимову, только граф обладающий свойством дополнительности расширения является точным расширением [19]. Точные расширения неориентированных графов также исследовались М. Ф. Караваем с точки зрения теории симметрии [23].

Как оказалось вершинно-симметрические графы* - единственные неориентированные графы, являющиеся точными* расширениями [5, 19]. Две вершины и и V графа С называются подобными, если существует автоморфизм /, такой что /{и) — V. Граф, все вершины которого подобны, называется вершинно-симметрическим (вершинно-транзитивным). В ориентированном случае вершинно-симметрические графы также являются точными расширениями.

Вершинно-симметрические графы уже довольно длительное время являются объектом изучения. Особое место среди них занимают, так называемые циркулянты или графы Кэли. Циркулянтом называется-^{-вершинный} граф О, такой, что, если его вершинам приписать меткиот 0 до п — 1, то из вершины I в вершину ] проходит дуга, тогда итолько тогда, когда, г- / (шос! п) е Д где это некоторое подмножество множества {О}. Известно, что для простого п все вершинно-симметрические' графы будут циркулянтами [11]. Однако в общему случае это не так. Минимальным" поколичеству вершин! неориентированным вершинно-симметрическим графом, не являющимся графом} Кэлиявляется- 10-вершинный граф Петерсена [11]- В ориентированном случае подобные графы* встречаются уже при числе вершин 8.

Еще одним интересным семейством точных расширений являются-транзитивные турниры. Транзитивный турнир— это" турнир с транзитивным отношением смежности. В (- отличие от вершинно-симметрических графов-гранзитивный турнир является асимметрическим, то есть у транзитивного турнира нет ни одной пары подобных вершин. Однако, то, что все максимальные подграфы транзитивного турнира изоморфны, говорит о том, что все его вершины в этом случае являются псевдо-подобными: Две вершины и и V графа О называются псевдо-подобными, если они не: подобны, однако, графы (7 — V и <7 — и изоморфны. Не существует ни одного неориентированного графа все вершины которого являются псевдо-подобными [9]. Транзитивный турнирэто единственный турнир, любая пара вершин которого псевдо-подобна [7].

Графы с псевдо-подобными вершинами представляют большой интерес, поскольку, считается, что они могут оказаться полезными для решения проблемы реконструируемости неориентированных графов — [9].

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

Работа состоит из введения, трех глав, содержащих 13 параграфов, библиографии, включающей 37 наименований, и двух приложений. Диссертация изложена на 80'страницах.

1. Avizienis A. The design of fault tolerant computers // AF1. S Conference Proceedings. 1967. P. 733−743.

2. Goldberg M. The group of the quadratic residue tournament // Canadian Mathematical Bulletin. 2001 № 17. P. 227−236.

3. Harary F., Palmer E.M. Graphical Enumeration // Academic Press. NY. 1973.

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

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

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

7. Jean M. Line-symmetric tournaments // Recent Progress in Combinatorics,. W.T.Tutte ed., Academic Press, New York. 1969. P. 265−271.

8. Kimble R.J., SchwenkA.J. and Stockmeyer P.K. Pseudosimilar vertices in a graph //J. Graph Theory. 1981. № 5. P. 171−181.9: Lauri J. Pseudosimilarity in graphs a survey // Ars Combin: 1997. № 46. P. 7795.

9. Lauri J. Constructing graphs with several pseudosimilar vertices or edges // Discrete Math. 2003. № 267. P. 197−211.

10. McKay B.D., Royle G.F. The transitive graphs with at most 26 vertices,// Ars Combinatoria. 1990. № 30: P. 161−176.

11. Morris J. Automorphism groups of circulant graphs: a survey // Graph Theory, Trends in Math. 2006. P. 311−325.

12. Radjavi-H., Rosenthal P. Graphs with isomorphic subgraphs // London Math. Soc. (2). 1972. Vol. 6. P. 70−72.

13. Stockmeyer P. A Census of non-reconstructable digraphs, I: six related families I I Journal of Combinatorial Theory B. 1981. V. 31. P. 232−239.

14. Turner J. Point-symmetric graphs with a prime number of points // J.Combin. Theory. 1967. № 3. P. 136−145.

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

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

17. Абросимов М. Б. Минимальные расширения транзитивных турниров // Вестник ТГУ. Приложение. 2006. № 17. С. 187−190.

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

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

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

21. Зыков A.A. Основы теории графов. М.: Наука, 1984.

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