On properties of minimal extensions of orgraphs.pdf Симметризацией орграфа "G = (V, а) называется неограф G = (V, (а U а- 1)\Д),то есть симметризация орграфа получается заменой дуг ребрами и удалением петель.В работе [1] удалось найти некоторые связи точных вершинных k-расширений ор-графов с точными вершинными k-расширениями неографов. Приведем некоторые изполученных результатов.Теорема 1. Пусть GG * - точное вершинное k-расширение орграфа "G. Тогда от-ношения смежности а и а* являются одновременно либо рефлексивными, либо анти-рефлексивными.Теорема 2. Пусть "G* -точное вершинное k-расширение орграфа "G. Тогда сим-метризация GG* является точным вершинным k-расширением симметризации "G.Теорема 3. Пусть "G -диграф с числом вершин больше 1, тогда его точное вер-шинное k-расширение, если оно есть, также будет диграфом.Теорема 4. Пусть GG* -точное вершинное k-расширение орграфа "G. Тогда до-полнение "G* является точным вершинным k-расширением дополнения "G.Обратным орграфом, или обращением орграфа "GG = (V, а) называется орграфH = (V,в), получающийся заменой ориентации всех дуг "G: в = а - 1 = {(u,v) ЕЕ V х V : (v,u) Е а}.Теорема 5. Пусть GG* - точное вершинное k-расширение орграфа GG. Тогда об-ращение GG* является точным вершинным k-расширением обращения GG .Точное вершинное k-расширение является частным случаем минимального вер-шинного k-расширения. При переходе к минимальным вершинным k-расширениям отточных вершинных k-расширений некоторые из полученных свойств сохранились. Уда-лось получить следующие результаты.Теорема 6. Пусть G * -минимальное вершинное k-расширение орграфа ". То-гда отношения смежности а и а* являются одновременно либо рефлексивными, либоантирефлексивными.Теорема 7. Пусть G * - минимальное вершинное k-расширение орграфа ". То-гда симметризация "G * является вершинным k-расширением симметризации GG.Теорема 8. Пусть G* -минимальное вершинное k-расширение орграфа ". То-гда обращение "G * является минимальным вершинным k-расширением обращения "G.Отдельный интерес представляет случай, когда минимальное вершинное k-расши-рение диграфа также является диграфом. Был проведен вычислительный экспериментпо построению минимальных вершинных k-расширений всех диграфов с числом вер-шин до 6. В работе рассматриваются полученные в ходе эксперимента результаты.

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